Centre for Discrete and Applicable Mathematics 

CDAM Research Report, LSECDAM200415August 2004 
Jan van den Heuvel and Matthew Johnson
Abstract
The connectivity of a communications network can often be enhanced if the nodes are able, at some expense, to form links using an external network. In this paper, we consider the problem of how to obtain a prescribed level of connectivity with a minimum number of nodes connecting to the external network.
Let D = (V,A) be a digraph. A subset X of vertices in V may be chosen, the socalled external vertices. An internal path is a normal directed path in D; an external path is a pair of internal paths p_{1} = v_{1}...v_{s}, p_{2} = w_{1}...w_{t} in D such that v_{s} and w_{1} are external vertices (the idea is that v_{1} can contact w_{t} along this path using an external link from v_{s} to w_{1}). Then D is externallykarcstrong if for each pair of vertices u and v in V, there are k arcdisjoint paths (which may be internal or external) from u to v.
We present polynomial algorithms that, given a digraph D and positive integer k, will find a set of external vertices X of minimum size subject to the requirement that D must be externallykarcstrong.
We also consider two generalisations of the problem: first we suppose that the number of arcdisjoint paths required from u to v may differ for each choice of u and v, and secondly we suppose that each vertex has a cost and that we are required to find a minimum cost set of external vertices. We show that these two problems are NPhard.
Finally, we consider the analogue of this problem for vertexconnectivity in undirected graphs. A graph G with set of external vertices X is externallykconnected if there are k vertexdisjoint paths joining each pair of vertices in G. We present polynomial algorithms for finding a minimum size set of external vertices subject to the requirement that G must be externallykconnected for the cases k in {1,2,3}.
A PDF file (227 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSECDAM200415, together with your name and postal address to:
CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K. 

Phone: +44(0)207955 7732. Fax: +44(0)207955 6877. Email: info@maths.lse.ac.uk 
Introduction to the CDAM Research Report Series.  
CDAM Homepage. 
Last changed: Wed 9 Feb 2005
For comments go to:
http://www.maths.lse.ac.uk/webmaster.html