Approximation Algorithms for Finding Highly
Connected Subgraphs

Samir Khuller
Dept. of Computer Science
University of Maryland
College Park, MD 20742
samir@cs.umd.edu
(301) 405 6765

This chapter is dedicated to Prof. Richard Karp whose Turing Award Lecture \Combinatorics, Complexity and
Randomness" (Communicationsof the ACM, Feb 1986) inspired this author to start working in the eld of algorithms.
Contents
1 Introduction 2
1.1 Outline of Chapter : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3
2 Edge-Connectivity Problems 3
2.1 Weighted Edge-Connectivity : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3
2.2 Unweighted Edge-Connectivity : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4
2.2.1 2 Edge-Connectivity : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4
2.2.2  Edge-Connectivity : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 8
3 Vertex-Connectivity Problems 11
3.1 Weighted Vertex-Connectivity : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11
3.2 Unweighted Vertex-Connectivity : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12
3.2.1 2 Vertex-Connectivity : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12
4 Strong-Connectivity Problems 15
4.1 Polynomial Time Approximation Algorithms : : : : : : : : : : : : : : : : : : : : : : 16
4.2 Nearly Linear-Time Implementation : : : : : : : : : : : : : : : : : : : : : : : : : : : 19
5 Connectivity Augmentation 21
5.1 Increasing Edge Connectivity from 1 to 2 : : : : : : : : : : : : : : : : : : : : : : : : 22
5.2 Increasing Vertex Connectivity from 1 to 2 : : : : : : : : : : : : : : : : : : : : : : : 25
5.3 Increasing Connectivity to  : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 29
1
1 Introduction
Let a graph G = (V;E) denote the feasible links of a (proposed) communications network. An
edge e = (a;b) denotes the feasibility of adding a link between sites a and b. The weight of this
edge, w(e), represents the cost of constructing link e. A minimum spanning tree in G is the lowest
weight connected subgraph, i.e., the cheapest network that will allow the sites to communicate.
Such a network is highly susceptible to failures, since it cannot even survive a single link or site
failure. For more reliable communication, one desires spanning subgraphs of higher connectivity.
A network of edge-connectivity  continues to allow communication between functioning sites even
after as many as BnZr1 links have failed. A graph is said to be  edge-connected if the deletion
of any (BnZr1) edges leaves it connected. These denitions extend in a straightforward way to 
vertex-connectivity. The only requirement is that the graph should have at least +1 vertices, and
the deletion of any (BnZr1) vertices should leave it connected. Given a graph G with non-negative
edge weights, and an integer , we consider the problem of nding a minimum-weight -connected
spanning subgraph. We address the cases of edge connectivity, and vertex connectivity. For most
connectivity versions, the associated problems are NP-hard. In this case we would like to obtain
sub-optimal solutions in polynomial time. From now on we will refer to sites as vertices, and links
as edges.
In this chapter, we address only uniform connectivity problems. For results on non-uniform con-
nectivity requirements, see Chapter 4 by Goemans and Williamson. The non-uniform connectivity
problems are solved using the \primal-dual" method of linear programming; this usually results in
approximation factors that are not as good as the ones obtained here.
Edge connectivity augmentation problems were rst studied by Eswaran and Tarjan [9]. They
studied the problem of making a given graph 2-connected (both vertex and edge connectivities
were considered) and strongly connected with the addition of the least number of edges. They
showed that when all potential edges are feasible and have weight 1, the problem can be solved
optimally in polynomial time, and when the edges have arbitrary weights the problem is NP-
hard. Subsequently, a lot of work was done on the problem of \increasing" the connectivity of
a given graph; most of these papers deal with the unweighted case where an edge may be added
between any pair of vertices. This problem can be solved optimally in polynomial time, at least
for the edge-connectivity case. We will not survey this body of research in detail here since we
are primarily interested in approximation techniques for NP-hard problems. For more information
on such problems see recent papers by Frank [10], and Naor, Guseld and Martel [32]. For the
vertex-connectivity case, the problem appears to be signicantly harder and no polynomial time
algorithm is known for nding the optimal solution. In his doctoral thesis, Hsu [22] gives algorithms
for vertex connectivity for small connectivity values. These algorithms are quite complex. It must
be pointed out that the problem of constructing a graph with n vertices, and connectivity  with
the least number of edges was rst addressed by Harary [19].
The rst paper to address the issue of obtaining approximate solutions for the case when edges
have weights, is by Frederickson and JaJa [11]. They provide approximation algorithms forthe cases
of 2-connectivity (edge and vertex) as well as strong connectivity problems. Subsequently, their
algorithm was simplied by Khuller and Thurimella[26, 27]. The unweighted case was explored by
Khuller and Vishkin [28], and Garg, Santosh and Singla [16]. For any k, fast algorithms for nding
sparse certicates were given by Nagamochi and Ibaraki [33] and Cheriyan, Kao and Thurimella
[5]. The strong connectivity case is addressed by Khuller, Raghavachari and Young [24, 25]. When
parallel edges are allowed, Goemans and Bertsimas provide an approximation algorithm [17].
2
1.1 Outline of Chapter
The problems we deal with are divided broadly into four categories: edge connectivity, vertex
connectivity, strong connectivity and connectivity augmentation. In each case, we study both the
weighted and unweighted problems.
In Section 2 we discuss the edge-connectivity results. This section surveys known results for
both the weighted case as well as the f1=1g case (where each edge has weight either 1 or 1).
In other words, the feasibility network is treated as an undirected graph, and each possible link is
either feasible or infeasible. In this case we are interested in minimizing the total number of edges
in our solution. Section 3 discusses the results on vertex connectivity. In Section 4 we discuss the
problem of nding strongly connected spanning subgraphs in directed graphs. In Section 5 we study
the problem of increasing the edge-connectivity of a given graph having an arbitrary connectivity,
to being  edge-connected.
2 Edge-Connectivity Problems
We begin this section by describing the algorithm given by Khuller and Vishkin [28] for obtaining
an approximation factorof 2 when the edges have weights. In Subsection 2.2 we consider the special
case when the weights are either 1 or1; for this special case we can achieve approximation ratios
less than 2.
2.1 Weighted Edge-Connectivity
Given a graph G = (V;E) with weights on the edges and an integer , consider the problem of
nding a minimum weight spanning subgraph H = (V;E
H
) that is  edge-connected.
An algorithm that achieves an approximation factor of 3 for  = 2 follows by the work of
Frederickson and JaJa [11]. First nd a minimum spanning tree. Now consider the problem of
nding the least weight set of edges to add to the tree to obtain a 2 edge-connected subgraph. Not
surprisingly, this is NP-hard as well [11]. They give an algorithm with an approximation factor of
2 for the problem of augmenting connectivity, yielding an approximation factor of 3 for the least
weight 2 edge-connected spanning subgraph. (In Section 5 we describe a simplication of their
algorithm due to Khuller and Thurimella [26].)
We now brie
y review the method given by Khuller and Vishkin [28] that yields an approxima-
tion algorithm for undirected graphs. Take the undirected graph G, and replace each undirected
edge e = (u;v) by two directed edges (u;v) and (v;u) with each edge having weight w(e). Call
this graph G
D
. Now consider the following problem for directed graphs: given a directed graph
G
D
with weights on the edges, and a xed root r, how does one nd the minimum weight directed
subgraph H
D
that has  edge-disjoint paths from a xed root r to each vertex v? Gabow [13]
gives the fastest implementation of a weighted matroid intersection algorithm due to Edmonds [8]
to solve this problem optimally in O(n(m+ nlogn)logn) time. Run Gabow's algorithm on the
graph G
D
, with an arbitrary vertex r chosen as the root. If at least one of the directed edges (u;v)
or (v;u) is picked in H
D
, then we add (u;v) to E
H
.
Lemma 2.1 The graph H = (V;E
H
) is a  edge-connected spanning subgraph of G.
Proof. Suppose (for contradiction) that there is a BnZr1 edge cut in H. Assume that it separates
H into pieces C
1
and C
2
. Let r be in C
1
, now consider a vertex v in C
2
. It is clear that r cannot
have  edge-disjoint directed paths to v. Thus there is no cut set of size BnZr1.
3
Theorem 2.2 The total weight of E
H
is at most twice the weight of the optimal solution.
Proof. Consider an optimal solutionOPT(G) for the minimum weight  edge-connected subgraph
problem. Consider all the anti-parallel edges corresponding to edges inOPT(G). We get a directed
subgraph in G
D
of weight 2w(OPT(G)) (where w(OPT(G)) is the total weight of the edges in
OPT(G)). From r there are  edge-disjoint undirected paths to any vertex v; these also yield 
directed paths from r to v that are edge-disjoint. Thus this subgraph has the property of having
 directed edge-disjoint paths from r to any vertex v. The optimum solution found by Gabow's
algorithm is only cheaper.
2.2 Unweighted Edge-Connectivity
Given an undirected graph G with n vertices and m edges, we would like to nd a subgraph H that
is -edge connected and has as few edges as possible. For the general case, Nagamochi and Ibaraki
[33] showed how to nd a spanning subgraph with at most n edges (see also Thurimella's doctoral
thesis [37]) that has edge-connectivity  if and only if the original graph G has edge connectivity
. Since each vertex is required to have degree at least , we get
n
2
as a lower bound on any 
edge-connected spanning subgraph. Thus this yields an approximation algorithm with a ratio of
2. In this section we describe a simple algorithm given by Khuller and Vishkin [28] that nds a 2
edge-connected spanning subgraph by using Depth First Search. Moreover, it is shown that this
algorithm achieves an approximation ratio of 1:5. Combining this the ideas of [33, 34, 37] yields an
approximation ratio of 2BnZr
1

.
2.2.1 2 Edge-Connectivity
In this section we present a linear time algorithm given by Khuller and Vishkin [28] to obtain a 2
edge-connected spanning subgraph from a given graph G. This algorithm obtains a solution that
is at most
3
2
times the optimal solution.
High-level Description of the Algorithm
We traverse G using depth-rst-search (DFS). A DFS rooted tree T is computed; T has at most
nBnZr1 edges, and all the non-tree edges are back edges (i.e., one of the endpoints of the edge is an
ancestor of the other in T). All edges of T are picked for E
H
. During the depth-rst search the
algorithm also picks a set of non-tree edges that will increase the edge connectivity by \covering"
all the edges in T (since each edge in T is a potential bridge). A back edge may be chosen just
before withdrawing from a vertex for the last time. Before withdrawing from a vertex v, we check
whether the edge (v;p(v)), joining v to its parent, is currently a bridge or not. If (v;p(v)) is still a
bridge, we cover it by adding to E
H
a back edge from a descendant of v to low[v], where low[v] is
the vertex with the smallest dfs-number that can be reached by following zero or more downgoing
tree edges from v, and a single back edge.
The Algorithm - a Detailed Description
In this section we give a detailed recursive description of the algorithm. The running time is
O(n+m), the algorithm is simple to implement and uses no complicated data structures.
Data Structures:
dfs[v]: A serial number given to a vertex the rst time it is visited during DFS. For simplicity, we
will assume that vertices are numbered by their dfs-number (i.e., v = dfs[v]).
4
state of a vertex: Each vertex is initially \unvisited". After the DFS traversal visits it for the rst
time, it becomes \discovered". When we nally exit from the vertex it becomes \nished". (This
is to be able to tell when we are looking at back edges from the upper end.)
low[v]: dened earlier.
low
H
[v]: This is dened to be the smallest numbered vertex that can be reached by following zero
or more downgoing tree edges from v, and a single back edge that belongs to E
H
.
savior[v]: This is dened to be the descendant end vertex of the back edge that goes to low[v].
Initialization Step: The initial call made is DFS(v;nil) where v is an arbitrary vertex. We
assume that G is a 2-edge connected graph (easy to verify this before running the algorithm).
Initially, all vertices are \unvisited".
Algorithm Find 2-EC Spanning Subgraph
Input: Graph G = (V;E).
Output: A subgraph H = (V;E
H
) that is 2-EC.
procedure DFS(v;u); (* u is the parent of v in DFS tree. *)
mark v discovered;
low[v] = v;
low
H
[v] = v;
savior[v] = v;
for each w2Adj[v] do
if w is unvisited then begin
E
H
= E
H
S
f(v;w)g; (* (v;w) is a tree edge *)
DFS(w;v);
low[v] = min(low[v], low[w]); If low[v] changes, set savior[v] = savior[w];
low
H
[v] = min(low
H
[v], low
H
[w]);
end
else if w is discovered then begin
if w6= u then (* (v;w) is a back edge *)
low[v] = min (low[v], w); If low[v] changes, set savior[v] = v;
(* else (v;w) is already a tree edge *)
(* else w is nished and is a descendant of v *)
end
mark v nished;
If low
H
[v] = v and u6= nil then begin
(* edge (u;v) is threatening to be a bridge *)
(* add the edge ( savior[v], low[v] ) to cover the bridge *)
E
H
= E
H
S
f( savior[v], low[v] )g;
low
H
[v] = low[v];
end
end DFS
It is quite easy to see that H has edge-connectivity 2, and that the algorithm runs in time
O(n+m).
The Approximation Analysis
Our analysis nds a partition of the vertices, called a tree-carving, which is used to prove a lower
bound on OPT, the number of edges in the optimal solution. The upper bound of
3
2
on the
5
approximation factor is established using this lower bound. After presenting the concept of a
tree-carving, we apply it to the approximation analysis.
Denition 1 A tree-carving of a graph is a partition of the vertex set V into subsets V
1
;V
2
;:::;V
k
with the following properties. Each subset constitutes a node of a tree BnZr. For every vertex v2V
j
,
all the neighbours of v in G belong either to V
j
itself, or to V
i
where V
i
is adjacent to V
j
in the tree
BnZr. The size of the tree-carving is k.
We will refer to the vertices of BnZr as nodes, and the edges of BnZr as arcs.
Theorem 2.3 (Tree-Carving Theorem)
If graph G = (V;E) has a tree-carving of size k, then a lower bound on the number of edges of any
2 edge-connected spanning subgraph in G is 2(kBnZr1).
It is interesting to note that the same simple proof implies that the smallest -connected sub-
graph of G must have at least (kBnZr1) edges.
Proof. There are kBnZr1 arcs in the tree BnZr. Each such arc e = (V
i
;V
j
) partitions the vertices in G
into two sets S
e
and VBnZrS
e
. (Deletion of arc e breaks BnZr into two trees BnZr
1
and BnZr
2
, where V
i
belongs
to BnZr
1
. S
e
is dened to be the union of the sets V
y
that belong to BnZr
1
.) In any 2 edge-connected
spanning subgraph we have: (1) at least two edges going from S
e
to V BnZrS
e
, and (2) both these
edges must have one endpoint in V
i
and another in V
j
; from the disjointness of V
i
's it follows that
for each arc e, there are two distinct edges in the subgraph. Since BnZr has kBnZr1 arcs, we get a lower
bound of 2(kBnZr1).
For an example of a tree-carving see Fig. 1.
Given T, the DFS spanning tree, we will be interested in the following partition of the vertices
of G, called the DFS-tree partition. Some recursive calls DFS(v;u) end by adding the back edge
(savior[v], low[v]) to E
H
, and some do not add any edge. For each call DFS(v;u) where a back edge
is added to E
H
, \remove" the tree edge (u;v) from T; the resulting connected components of T
(with some tree edges removed) provides the DFS-partition. Furthermore, T induces a rooted tree
structure BnZr on the sets in the DFS-tree partition. In fact, it is easy to modify the approximation
algorithm to nd the tree-carving as well; however this is not essential since it is only used for the
analysis of the algorithm.
Theorem 2.4 The DFS-tree partition yields a tree-carving of G.
Proof. Let (v
1
;v
2
) be any non tree edge in G. Suppose that v
1
is in set V
1
of the DFS-tree
partition and v
2
is in set V
2
. Let us assume that v
1
is an ancestor of v
2
. Clearly low[v
2
]v
1
. Thus
by the algorithm there can be at most one bridge between them. Hence, either V
1
= V
2
, or set V
1
is the parent set of set V
2
(in the rooted tree structure BnZr).
Corollary 2.5 Since the number of arcs in the tree-carving is exactly the same as the number of
back edges that are added to E
H
we conclude that OPT 2(kBnZr1), where kBnZr1 is the number of
added back edges.
Theorem 2.6 The algorithm outputs a solution of size no more than
3
2
OPT.
6
(b) Tree-Carving of size 5 for G
(a) G
1
2
3
4
5
6 7
8
9
1
2
3
4
5
6
7
8
9
V
1
V
2
V
3
V
4
V
5
V
5
V
4
V
3
V
2
V
1
(c) The tree BnZr
Figure 1: Example to show 2 edge-connectivity algorithm and a tree-carving.
7
Proof. The number of edges added by the algorithm to H is: (i) (nBnZr1), for the tree edges, plus
(ii) kBnZr1 back edges, where k is also the size of the tree-carving. Hence, the number of edges in
E
H
is nBnZr1+ kBnZr1. Let OPT be the number of edges in an optimal solution. A lower bound on
OPT is max(n;2(kBnZr1)), since n is the minimum number of edges in a 2-edge connected graph
with n vertices (each vertex should have degree at least 2), and 2(kBnZr1) follows from Corollary
2.5. Hence, the ratio of the algorithm's solution to OPT is

nBnZr1+ kBnZr1
max(n;2(kBnZr1))
:
If n2(kBnZr1), then clearly the ratio is < 3=2. If n2(kBnZr1), it is again easy to see that the ratio
is < 3=2.
2.2.2  Edge-Connectivity
We now describe a linear time algorithm given by Nagamochi and Ibaraki [33] that nds a -
connected spanning subgraph of a given graph G that has connectivity at least . The algorithm
nds a subgraph with at most (nBnZr1) edges; since every vertex has degree at least , we get a
lower bound of
n
2
for OPT. Hence this is a factor 2 approximation. We then use the previous DFS
based algorithm for 2 edge-connectivity to improve this ratio by
1

.
The main idea behind their algorithm is to repeatedly nd maximal spanning forests in the
graph, and to delete them. After  iterations of this method, we obtain  forests, which form a
 edge-connected spanning subgraph assuming that the input graph was  edge-connected. More
formally, we state the following lemma (also due to [37, 34]).
Lemma 2.7 For a graph G = (V;E) that has edge connectivity , let F
i
= (V;E
i
) be a maximal
spanning forest in GBnZrE
1
[:::[E
iBnZr1
, for i = 1:::; then G

= (V;E
1
[:::[E

) has edge
connectivity .
Proof. Assume(forcontradiction) thatG

containsacut C ofsize k < whoseremoval disconnects
the graph G

into G
0

and G
00

. Clearly, at least one forest, say F
j
, does not have any edges in C.
Since the original graph G was  edge-connected it must be the case that there is at least one edge
in G between the two components G
0

and G
00

. Hence in iteration j when we were picking F
j
we
would pick an edge connecting G
0

and G
00

.
It is easy to nd the set of forests by repeatedly scanning the graph  times [37, 34]. The
amazing fact about Nagamochi and Ibaraki's algorithm is that they can nd all the forests in a
single scan of the graph. During the search, for each edge e we compute the integer i satisfying
e 2 E
i
. In fact, the algorithm assigns each edge to the forest it would have ben assigned if we
repeatedly removed spanning forests until the graph was completely exhausted.
For each vertex v, we maintain the rank r(v), and r(v) = i if v has been reached by an edge of
the forest F
i
.
We now argue that the algorithm in Fig. 2 implements the algorithm that repeatedly nds
forests and deletes them. Formally, what is shown is that each F
i
= (V;E
i
) is a maximal spanning
forest in GBnZrE
1
[:::[E
iBnZr1
.
In Fig. 3 we illustrate the execution of the algorithm via a small example.
8
 Connectivity |
1 Label all nodes and edges as \unscanned"
2 r(v) = 0 for all v2V
3 while there exist \unscanned" nodes do
4 Choose an \unscanned" node x with the largest r
5 for each \unscanned" edge e = (x;y) do
6 if r(x) = r(y) then r(x) = r(x)+1
7 r(y) = r(y)+ 1
8 E
r(y)
= E
r(y)
[e
9 Mark e scanned
10 Mark x scanned
Figure 2: Nagamochi and Ibaraki's Algorithm to nd a  connected graph.
Proposition 2.8 For a vertex v let E(v) denote the edges incident to v. At the start of each
iteration of scanning an unscanned edge
E(v)\E
i
6=;for i = 1;:::;r(v)
E(v)\E
i
=;for i = r(v)+ 1;:::;:
Proposition 2.8 immediately implies that each subgraph F
i
is acyclic, since we add edge e =
(x;y) to E
i
only when r(y) rst becomes i, so there is no edge in E
i
incident on y when e is added.
Before we prove that each forest F
i
is maximal in GBnZrE
1
[:::[E
iBnZr1
, we give some denitions.
If an edge e = (u;v) with E(u)\E
i
= ; and E(v)\E
i
= ; is added to E
i
then the edge e is
called the root edge of E
i
. The vertex u is called the root vertex of E
i
if it is scanned before v.
(The reader should convince themselves that this edge is unique.) The key intuition is that once
we create a tree T in E
i
, before starting a new tree T
0
in E
i
, we will have scanned all the nodes in
T. This would guarantee that we do not process an edge between T and T
0
at some later point of
time (and erroneously put that edge in E
i+1
).
Lemma 2.9 When we add an edge e to E
i
there exists a path P
iBnZr1
E
iBnZr1
connecting u and v.
Proof. Suppose there is no path connecting u and v in E
iBnZr1
. Then there must be two trees T
u
and T
v
that contain u and v respectively (observe that the label of u and the label of v isiBnZr1).
Let u
0
and v
0
be the roots of these trees. Let the path from u
0
to u be P = [u
0
;u
1
;:::;u
k
= u].
W. l. o. g u
0
was scanned before v
0
. When u
0
was scanned r(u
0
) = iBnZr2 and r(v
0
)iBnZr2. After
scanning (u
0
;u
1
), r(u
1
) = iBnZr1 and is scanned before v
0
. In a similar manner we can argue that all
the nodes on P are scanned before v
0
including v (after we scan the node u). This is a contradiction
to the assumption that v
0
is the root of T
v
.
Lemma 2.10 If there is a path P
j
E
j
connectingu and v, then there are paths P
i
E
i
connecting
u and v, for all i < j.
Proof. For each edge in P
j
, by Lemma 2.9 we know that there is a path in E
jBnZr1
connecting the
endpoints of that edge. Taking the union of all the paths for each edge, gives us a path P
jBnZr1
from
u to v in E
jBnZr1
. Similarly, we can prove this for i = jBnZr2;:::;1 etc.
9
A
C
D
E
F
G
B
Edges in E
1
Edges in E
3
Edges in E
2
A B C D E F G
Table to show r(v) values
Initial 0 0 0 0 0 0 0
0 0 0
0
0
0
1 1 1 1
1
1
1
1
1
1 12 2 2
2 2 23 3
2
Scan A
Scan B
Scan C
Scan D 3 3 2 2
2 3 3 3 3 1
2 3 3 3 23
Scan E
Scan F
Scan G 1 2 3 3 3 3 2
Figure 3: Example to show the running of the Algorithm.
Theorem 2.11 Each graph F
i
= (V;E
i
) is a maximal spanning forest in GBnZrE
1
[:::[E
iBnZr1
.
Proof. We argued earlier that F
i
is acyclic. If it is not maximal in GBnZrE
1
[:::[E
iBnZr1
then there
is an edge e 2E
j
(with j > i) such that (V;E
i
[e) is a forest. By Lemma 2.9 we know that E
i
must contain a path P
i
from u to v. This would give a contradiction to the fact that (V;E
i
[e) is
a forest.
We now show how to nd a subgraph of edge connectivity  that is at most 2BnZr
1

times the
optimal. Find a 2 edge-connected graph by using the DFS based algorithm described earlier. Let
this graph be called H
2
. Now add BnZr2 forests to H
2
, by repeatedly removing the edges on each
forest (see Fig. 4).
 Connectivity |
1 Find H
2
a 2-edge connected subgraph using the DFS based algorithm.
2 for i = 3;:::;
3 Let T
i
be a spanning forest in GBnZrH
iBnZr1
.
4 Let H
i
= H
iBnZr1
[T
i
.
Figure 4: Algorithm to nd a  connected graph.
A simple proof that this yields a  edge-connected graph can be obtained in a manner similar
to the proof of Lemma 2.7. The proof is left as an exercise for the reader.
Now let us bound the total number of edges added by this procedure. The number of edges in
H
2
is (i) nBnZr1, for the tree edges plus (ii) kBnZr1 back edges, where k is the size of the tree-carving.
In Step 4, we add at most (BnZr2)n edges to make the graph  connected.
An obvious lower bound on the optimal solution is
n
2
(by a degree argument); and (kBnZr1)
10
using the tree-carving lower bound. Putting this together we get
(nBnZr1)+(kBnZr1)+ (BnZr2)n
maxf(kBnZr1);
n
2
g
Simplifying, we get the upper bound of (2BnZr
1

).
Remark: Recently, Khuller and Raghavachari [23] were able to obtain an algorithm with a per-
formance ratio of at most 1:85 for any . The key idea is to augment the connectivity by two in
each stage by adding 2 edge-connected subgraphs. The proof requires a subtle argument, and uses
the notion of tree-carvings.
Open Problem: It seems likely that one should be able to obtain algorithms for which the
performance ratio improves as  increases, at least for the unweighted case. However, we have
not been able to do this as yet. An increased understanding of higher connectivity seems essential
before this can be done.
3 Vertex-Connectivity Problems
3.1 Weighted Vertex-Connectivity
For the general problem no constant factor approximation algorithms are known. The best known
algorithm to nd a -connected subgraph for the weighted case is the algorithm due to Ravi and
Williamson [35] that achieves a factor of 2H(), where H() = 1 +
1
2
::: +
1

. For the case of
nding a 2 vertex-connected graph, an approximation algorithm achieving a factor of 3 was given
by Frederickson and JaJa, through solving the more general graph augmentation problem. It is
possible to obtain an approximation factor of 2+
1
n
by using a technique similar to the one used in
Subsection 2.1.
Frank and Tardos [12] extended Edmonds method [8] to show that the following problem can
be solved in polynomial time: Given a directed graph G
D
with weights on the edges, and a xed
root r. Find the cheapest directed subgraph H
D
that has  internally vertex-disjoint paths from a
xed root r to each vertex v.
Using this algorithm as a subroutine it is possible to obtain a factor 2 approximation for the
weighted case, when  = 2.
The idea is as follows: Create a new graph G
D
as follows: for each undirected edge e = (u;v)
in G create bi-directional edges (u;v) and (v;u) in G
D
, each of weight w(e). Let e
0
= (x;y) be the
lowest weight edge in G.
We create a new vertex r as the root and add directed edges (r;x)and (r;y)of weight 0. We now
run Frank and Tardos's algorithm to nd the minimum weight subgraph H
D
with  = 2. This will
provide two directed vertex-disjoint paths from r to each vertex v. Let E
H
be the subset of edges
in G such that one of its copies was chosen in H
D
. We claim that the graph H = (V;E
H
[fe
0
g) is
2-vertex connected (observe that r is not in H).
Proposition 3.1 For any vertex v in G, there are paths P(x;v) and P(y;v) in H that are internally
vertex disjoint.
Lemma 3.2 The graph H = (V;E
H
[fe
0
g) is 2 vertex-connected.
Proof. Suppose H contains a cut vertex a. Let the deletion of a from H[fe
0
gbreaks the graph
into components C
1
;:::;C
k
. Since x and y are adjacent they will be in a[C
i
(for some i). W. l. o. g
11
assume that x and y belong to a[C
1
. Consider a vertex v 2 C
2
. Clearly, there cannot be two
vertex disjoint paths from x and y to v.
Theorem 3.3 The total weight of E
H
[fe
0
gis at most (2+
1
n
) times the optimal solution.
Proof. Since every 2 vertex-connected graph contains at least n edges, the minimum weight
edge in G is at most
1
n
w(OPT(G)), where w(OPT(G)) is the weight of a minimum weight 2
vertex-connected spanning subgraph.
Now consider an optimal solutionOPT(G) for the problem. Consider all the anti-parallel edges
corresponding to edges in OPT(G). We get a directed subgraph in G
D
of weight 2w(OPT(G)).
From x and y there are 2 vertex-disjoint paths to any vertex v; these also yield 2 directed paths
from r to v that are also internally vertex-disjoint. Thus this subgraph has the property of having
2 directed vertex-disjoint paths from r to any vertex v. The optimum solution found by Frank and
Tardos's algorithm can therefore only have lower weight.
Remark: For the case when the edge weights satisfy triangle inequality, Khuller and Raghavachari
[23] present algorithms using similar techniques that achieve a performance ratio of 2+2
(BnZr1)
n
.
3.2 Unweighted Vertex-Connectivity
Given an undirected graph G with n vertices and m edges, we would like to nd a subgraph H that
is  vertex-connected and has as few edges as possible. In fact, Nagamochi and Ibaraki's algorithm
(described earlier) nds a spanning subgraph with at most n edges that has vertex-connectivity 
if and only if the original graph G has vertex connectivity . Since each vertex is required to have
degree at least , we get that
n
2
is a lower bound on any  edge-connected spanning subgraph.
This yields an approximation algorithm with a ratio of 2.
We now describe the algorithm due to Cheriyan and Thurimella [6]. The idea is to \peel"
away maximal spanning forests from G, and to repeat this procedure  times as was done for the
edge connectivity case. To obtain a  vertex-connected subgraph Cheriyan and Thurimella suggest
the use of a forest obtained by running Breadth First Search from an arbitrary vertex in each
connected component. Taking the union of these forests yields a  vertex-connected subgraph.
(A more ecient parallel implementation using a weaker notion of scan-rst search was given by
Cheriyan, Kao and Thurimella [5].) The proofs of the fact that this yields a  vertex-connected
subgraph is a little complicated. The reader is referred to the paper [6, 5].
3.2.1 2 Vertex-Connectivity
In this section we describe a simple method given by Khuller and Vishkin [28] that nds a 2 vertex-
connected spanning subgraph by using Depth First Search. Combined with the edge discarding
technique of Garg, Santosh and Singla [16] one obtains an approximation ratio of 1:5. Garg,
Santosh and Singla [16] simplied and improved the algorithm due to Khuller and Vishkin [28] to
yield an approximation factor of
3
2
. The algorithm is in two phases. The rst phase is similar to the
algorithm for the 2 edge-connectivity case described earlier. The second phase achieves two goals:
(i) an attempt is made to expunge tree edges and (ii) an attempt is made to modify the choice of
back edges so that it will help in expunging tree edges.
High-level Description of the Algorithm
The rst phase is as follows: In the graph G, do a depth-rst-search to compute a DFS spanning
tree T. The idea is to now pick a set of back edges that will increase the vertex connectivity of the
12
tree to two by \detouring" around each vertex of the tree T. During the Depth First Search all
the tree edges are added to E
H
, as well as some subset of back edges. The back edges are chosen
when the DFS traversal is visiting a vertex for the last time. When DFS retreats out of a vertex
v for the last time, we check if the vertex u (parent of v) is potentially a cut vertex or not. If yes,
we can cover it by adding to E
H
the highest going back edge from a descendant of v. (This will at
least prevent the separation of v from p(u) under the deletion of u.)
Before discussing the second phase, we dene the notion of carving of a graph, and point out
the key dierence between tree-carving and carving.
Denition 2 A carving of a graph is a partitioning of the vertex set V into a collection of subsets
V
1
;V
2
;:::;V
k
with the following properties. Each subset constitutes a node of a rooted tree BnZr. Each
non-leaf node V
j
of BnZr has a special grey vertex denoted by g(V
j
) that belongs to p(V
j
). For every
vertex v2V
i
, all the neighbours of v that are in ancestor sets of V
i
belong to either
1. V
i
, or
2. V
j
, where V
j
is the parent of V
i
in the tree BnZr, or
3. V
`
, where V
`
is the grandparent in the tree BnZr. In this case however, the neighbour of v can
only be g(p(V
i
)).
The neighbour of v is required to be either an ancestor of v or a descendant of v.
We will refer to the vertices of BnZr as nodes, and the edges of BnZr as arcs. The root vertex belongs
to a special set called the root-set. The key dierence between the carving and tree-carving is that
in the latter edges are only allowed to go to the parent node. In a carving, edges are allowed to go
to a single vertex in the grandparent node as well.
Given T, the DFS spanning tree, we will be interested in the following partition of the vertices
of G, called the DFS-tree partition. Some recursive calls DFS(v;u) end by adding the back edge
(savior[v], low[v]) to E
H
. For each such call DFS(v;u), \remove" the tree edge (u;v) from T; the
resulting connected components of T (with some tree edges removed) provides the DFS-partition.
Furthermore, T induces a rooted tree structure on the sets in the DFS-tree partition.
The proof of the following theorem is given in [28].
Theorem 3.4 The DFS-tree partition yields a carving of G.
In the second phase the carving is processed \top-down" (starting with the root set). At each
step a modication is made to the choice of the back edge (going upwards) from a carving set.
This method is able to delete some of the tree edges as it proceeds (a similar trick was used in [28]
but was not powerful enough to give an approximation factor of
3
2
). The deletion of tree edges is
justied by the following lemma [16].
Lemma 3.5 Let G
0
be a 2 vertex-connected graph; C is a simple cycle in G
0
, and e = (u;v) is a
chord in C. Then G
0
BnZrfegis also 2 vertex-connected.
The parent vertex of a carving-set S is the grey vertex of S. Each carving-set (except for the
root-set) has a unique parent vertex.
During the \top-down" phase, each time we process a carving-set we either discard a tree edge,
or nd a new vertex to add to an independent set. Suppose kBnZr1 back edges were added in the
13
u
q
w
x
v
S
0
S
Figure 5: Figure for Case 1.
rst phase (k is the number of sets in the carving). In the second phase, for each added back edge,
we either discard a tree edge (so the back edge does not cost us anything) or we add a new vertex
to the independent set. On termination, if we have p back edges remaining, we are able to nd an
independent set of size p. Clearly, 2p is a lower bound on the optimal solution since an independent
set trivially yields a carving of size p + 1 (by making each vertex of the independent set into a
carving set, and all the other vertices into a single carving set).
We shall now jump into the guts of the second phase. When processing a carving-set we decide
the back edges out of its child blocks. Consider a set S with the back edge out of S being (v;u)
with v2S. Consider the path in T from v to q = g(S), the parent vertex (or grey vertex) of set S.
Let w be the rst vertex (excluding v) along this path that has no tree edge (other than the edges
on the vBnZrq path) incident on it. If there is no such vertex then w is q.
If there is a back edge (x;w) with x2S
0
, a child of S in BnZr. Instead of picking the highest going
back edge from S
0
we pick the back edge (x;w). For all other child blocks we do not modify the
choice of back edges. Picking this back edge allows the deletion of the edge connecting w to its
child in T. There are two cases:
Case 1 w = p(v): observe that the edge (v;w) is a chord on the cycle uBnZrvBnZrBnZrxBnZrwBnZrBnZrqBnZrBnZru and
can be deleted (see Fig. 5).
Case 2 w6= p(v): let (r
0
;r) and (r;w) be the last two edges on the path in the DFS tree from v to
w. We now have two cases: the rst case is when x is a descendant of r
0
. By our assumption
on w, there must be a tree edge incident on vertex r other than the ones going to r
0
and
w. Assume that this tree edge goes to a child S
00
of S in BnZr. There must be a back edge
(x
0
;w
0
) where x
0
2S
00
and w
0
is on the path from w to q in the DFS tree. The edge (r;w) is
a chord on the cycle rBnZrBnZrxBnZrwBnZrBnZrw
0
BnZrx
0
BnZrBnZrr and can be deleted (see Fig. 6). The second
14
u
q
w
x
v
x
0
r
r
0
w
0
S
S
0
S
00
Figure 6: Figure for Case 2.
case is when x is not a descendant of r
0
. In this case the edge (r;w) is a chord on the cycle
wBnZrBnZrqBnZrBnZruBnZrvBnZrBnZrrBnZrBnZrxBnZrw and can be deleted.
We can use this tree edge to account for the back edge emanating from the set S, and this back
edge is thus paid for. We label the set S as \free".
If w has no back edges from any child block, we mark w and label the set S as \marked". The
root-set has no back edge emanating from it, and is marked \free". In addition each leaf of the
DFS tree forms a singleton set, and is marked and the set is labeled \marked". To argue that the
set of marked vertices form an independent set, observe that no two marked vertices belong to the
same set in the carving. Further, a marked vertex has no edge from any descendant set of the set
that contains it. Thus no two marked vertices can have an edge between them.
Upon termination, if we have p \marked" sets, we have nBnZr1+p edges in our solution, and the
lower bound on the optimal solution is max(n;2p). It is easy to see that this is at most
3
2
.
Open Problems: The main open problem is to obtain a constant factor approximation when the
edge weights do not satisfy the triangle inequality. Unlike the edge-connectivity case we do not
know how to obtain factors less than 2, even for the unweighted case.
4 Strong-Connectivity Problems
Most of the network design literature addresses the problem of nding subgraphs having certain
connectivities, in undirected graphs only. We now turn our attention to perhaps the simplest
corresponding problem in directed graphs. Given a strongly connected directed graph, nd a
minimum strongly connected spanning subgraph (SCSS). Not surprisingly, this problem is NP-
15
hard by a simple reduction from Hamilton Cycle in directed graphs. This problem was rst studied
by Frederickson and JaJa [11] for the weighted case, and a algorithm achieving an approximation
factor of 2 was obtained. (This is obtained by taking the union of a minimum weight in-branching
and a minimum weight out-branching, rooted at an arbitrary vertex.) For the unweighted case,
Khuller, Raghavachari and Young [24] obtained an approximation algorithm with a performance
ratio of about 1:64, which was improved to 1:61 [25]. The algorithms have a relatively high running
time, albeit polynomial. An almost linear time algorithm that achieves a ratio of 1:75 is also
described.
The MEG (minimum equivalent graph) problem is the following: \Given a directed graph, nd
a smallest subset of the edges that maintains all reachability relations between nodes." This prob-
lem is NP-hard; in fact, the heart of the MEG problem is the minimum SCSS (strongly connected
spanning subgraph) problem | the MEG problem restricted to strongly connected digraphs. The
MEG problem reduces in linear time [7] to a single acyclic problem given by the so-called \strong
component graph", together with one minimum SCSS problem for each strongcomponent (given by
the subgraph induced by that component). Furthermore, the reduction preserves approximation,
in the sense that c-approximate solutions to the subproblems yield a c-approximate solution to the
original problem. Hence an approximation algorithm for the SCSS problem implies an approxi-
mation algorithm for the MEG problem. Moyles and Thompson [31] observe this decomposition
and give exponential-time algorithms for the restricted problems. Hsu [21] gives a polynomial-time
algorithm for the acyclic MEG problem.
First we describe the basic algorithm that achieves a factor of 1:64 in polynomial time. The
algorithm and its analysis are based on the simple idea of contracting long cycles. After that we
will describe the nearly linear-time algorithm that achieves a ratio of 1:75. To learn about the
improvement to 1:61 the reader is referred to [25].
4.1 Polynomial Time Approximation Algorithms
Given a strongly connected graph, the basic algorithm nds as long a cycle as it can, contracts
the cycle, and recurses. The contracted graph remains strongly connected. When the graph nally
collapses into a single vertex, the algorithm returns the set of edges contracted during the course of
the algorithm as the desired SCSS. The algorithm achieves a performance guarantee of any constant
greater than 
2
=61:645 in polynomial time.
A natural improvement to the cycle-contraction algorithm is to modify the algorithm to solve
the problem optimally once the contracted graph has no cycles longer than a given length c.
For instance, for c = 3, this modication improves the performance guarantee to 
2
=6BnZr1=36
1:617. We use SCSS
c
to denote the minimum SCSS problem restricted to digraphs with no cycle
longer than c. The minimum SCSS
2
problem is trivial. The minimum SCSS
3
problem can be
solved in polynomial time, as shown by Khuller, Raghavachari and Young [25]. However, further
improvement in this direction is limited: we show that the minimum SCSS
5
problem is NP-hard.
Before describing the algorithm we discuss some basic notation used in the rest of the section.
To contract a pair of vertices u;v of a digraph is to replace u and v (and each occurrence of u or v
in any edge) by a single new vertex, and to delete any subsequent self-loops and multi-edges. Each
edge in the resulting graph is identied with the corresponding edge in the original graph or, in
the case of multi-edges, the single remaining edge is identied with any one of the corresponding
edges in the original graph. To contract an edge (u;v) is to contract the pair of vertices u and
v. To contract a set S of pairs of vertices in a graph G is to contract the pairs in S in arbitrary
16
order. The contracted graph is denoted by G=S. Contracting an edge is also analogously extended
to contracting a set of edges.
Let OPT(G) be the minimum size of any subset of the edges that strongly connects G. In
general, the term \cycle" refers only to simple cycles.
We begin by showing that if a graph has no long cycles, then the size of any SCSS is large.
Lemma 4.1 (Cycle Lemma) For any directed graph G with n vertices, if a longest cycle of G
has lengthC, then
OPT(G)
C
CBnZr1
(nBnZr1):
Proof. Starting with a minimum-size subset that strongly connects the graph, repeatedly contract
cycles in the subset until no cycles are left. Observe that the maximum cycle length does not
increase under contractions. Consequently, for each cycle contracted, the ratio of the number of
edges contracted to the decrease in the number of vertices is at least
C
CBnZr1
. Since the total decrease
in the number of vertices is nBnZr1, at least
C
CBnZr1
(nBnZr1) edges are contracted.
Note that the above lemma gives a lower bound which is existentially tight. For all values ofC,
there exist graphs for which the bound given by the lemma is equal toOPT(G). Also note thatC
has a trivial upper bound of n and, using this, we get a lower bound of n forOPT(G), which is
the known trivial lower bound.
Lemma 4.2 (Contraction Lemma) For any directed graph G and set of edges S,
OPT(G)OPT(G=S):
Proof. Any SCSS of G, contracted around S (treating the edges of S as pairs), is an SCSS of
G=S.
The algorithm is the following. Fix k to be any positive integer.
Contract-Cycles
k
(G) |
1 for i = k;kBnZr1;kBnZr2;:::;2
2 while the graph contains a cycle with at least i edges
3 Contract the edges on such a cycle.
4 return the contracted edges
We will show that the algorithm runs in polynomial time for any xed value of k. It is clear
that the edge set returned by the algorithm strongly connects the graph. The following theorem
establishes an upper bound on the number of edges returned by the algorithm.
Theorem 4.3 Contract-Cycles
k
(G) returns at most c
k

OPT(G) edges, where

2
6
c
k


2
6
+
1
(kBnZr1)k
:
Proof. Initially, let the graph have n vertices. Let n
i
vertices remain in the contracted graph after
contracting cycles with i or more edges (i = k;kBnZr1;:::;2).
How many edges are returned? In contracting cycles with at least k edges, at most
k
kBnZr1
(nBnZrn
k
)
edges are contributed to the solution. For i < k, in contracting cycles with i edges,
i
iBnZr1
(n
i+1
BnZrn
i
)
edges are contributed. The number of edges returned is thus at most
k
kBnZr1
(nBnZrn
k
)+
kBnZr1
X
i=2
i
iBnZr1
(n
i+1
BnZrn
i
)

1+
1
kBnZr1

n+
k
X
i=3
n
i
BnZr1
(iBnZr1)(iBnZr2)
:
17
Clearly OPT(G)n. For 2ik, when n
i
vertices remain, no cycle has more than iBnZr1
edges. By Lemmas 4.1 and 4.2, OPT(G) 
iBnZr1
iBnZr2
(n
i
BnZr1). Thus the number of edges returned,
divided byOPT(G), is at most

1+
1
kBnZr1

n
OPT(G)
+
k
X
i=3
n
i
BnZr1
(iBnZr1)(iBnZr2)
OPT(G)

(1+
1
kBnZr1
)n
n
+
k
X
i=3
n
i
BnZr1
(iBnZr1)(iBnZr2)
iBnZr1
iBnZr2
(n
i
BnZr1)
=
1
kBnZr1
+
kBnZr1
X
i=1
1
i
2
= c
k
:
Using the identity (from [30, p.75])
P
1
i=1
1
i
2
=

2
6
, we get

2
6
 c
k
=

2
6
+
1
kBnZr1
BnZr
1
X
i=k
1
i
2


2
6
+
1
kBnZr1
BnZr
1
X
i=k
1
i(i+1)
=

2
6
+
1
kBnZr1
BnZr
1
k
=

2
6
+
1
(kBnZr1)k
:
If desired, standard techniques can yield more accurate estimates of c
k
, e.g., c
k
=

2
6
+
1
2k
2
+
O

1
k
3

: If the graph initially has no cycle longer than ` (`k), then the analysis can be generalized
to show a performance guarantee of
k
BnZr1
BnZr`
BnZr1
1BnZrk
BnZr1
+
P
kBnZr1
i=1
1=i
2
. For instance, in a graph with no cycle
longer than 5, the analysis bounds the performance guarantee (when k = 5) by 1:424.
Table 1 gives lower and upper bounds on the performance guarantee of the algorithm for small
values of k and in the limit as k!1. The lower bounds are shown in [24].
k Upper Bound Lower Bound
3 1.750 1.750
4 1.694 1.666
5 1.674 1.625
1 1.645 1.500
Table 1: Bounds on the performance guarantee.
For any xed k, Contract-Cycles
k
can be implemented in polynomial time using exhaustive
search to nd long cycles. For instance, if a cycle of size at least k exists, one can be found in
polynomial time as follows. For each simple path P of kBnZr1 edges, check whether a path from the
head of P to the tail exists after P's internal vertices are removed from the graph. If k is even,
there are at most m
k=2
such paths; if k is odd, the number is at most nm
(kBnZr1)=2
. It takes O(m)
time to decide if there is a path from the head of P to the tail of P. For the rst iteration of the
for loop, we may have O(n) iterations of the while loop. Since the rst iteration is the most time
consuming, the algorithm can be implemented in O(nm
1+k=2
) time for even k and O(n
2
m
(k+1)=2
)
time for odd k.
18
4.2 Nearly Linear-Time Implementation
We now describe a practical, near linear-time implementation of Contract-Cycles
3
. The perfor-
mance guarantee achieved is c
3
= 1:75. Contract-Cycles
3
consists of two phases: (1) repeatedly
nding and contracting cycles of three or more edges (called long cycles), until no such cycles exist,
and then (2) contracting the remaining 2-cycles.
High-level description of the algorithm
To perform Phase (1), the algorithm does a depth-rst search (DFS) of the graph from an arbitrary
root. During the search, the algorithm identies edges for contraction by adding them to a set S.
At any point in the search, G
0
denotes the subgraph of edges and vertices traversed so far. The
rule for adding edges to S is as follows: when a new edge is traversed, if the new edge creates a
long cycle in G
0
=S, the algorithm adds the edges of the cycle to S. The algorithm thus maintains
that G
0
=S has no long cycles. When the DFS nishes, G
0
=S has only 2-cycles. The edges on these
2-cycles, together with S, are the desired SCSS.
Because G
0
=S has no long cycles and the fact that the original graph is strongly connected,
G
0
=S maintains a simple structure:
Lemma 4.4 After the addition of any edge to G
0
and the possible contraction of a cycle by adding
it to S: (i) The graph G
0
=S consists of an outward branching and some of its reverse edges. (ii) The
only reverse edges that might not be present are those on the \active" path: from the super-vertex
containing the root to the super-vertex in G
0
=S containing the current vertex of the DFS.
Proof. Clearly the invariant is initially true. We show that each given step of the algorithm
maintains the invariant. In each case, if u and w denote vertices in the graph, then let U and W
denote the vertices in G
0
=S containing u and w, respectively.
When the DFS traverses an edge (u;w) to visit a new vertex w:
Vertex w and edge (u;w) are added to G
0
. Vertex w becomes the current vertex. In G
0
=S, the
outward branching is extended to the new vertex W by the addition of edge (U;W). No other edge
is added, and no cycle is created. Thus, part (i) of the invariant is maintained. The super-vertex
containing the current vertex is now W, and the new \active path" contains the old \active path".
Thus, part (ii) of the invariant is also maintained.
When the DFS traverses an edge (u;w) and w is already visited:
If U = W or the edge (U;W)already exists in G
0
=S, then no cycle is created, G
0
=S is unchanged,
and the invariant is clearly maintained. Otherwise, the edge (u;w) is added to G
0
and a cycle with
the simple structure illustrated in Fig. 7 is created in G
0
=S. The cycle consists of the edge (U;W),
followed by the (possibly empty) path of reverse edges from W to the lowest-common-ancestor
(lca) of U and W, followed by the (possibly empty) path of branching edges from lca(U;W) to U.
Addition of (U;W) to G
0
=S and contraction of this cycle (in case it is a long cycle) maintains part
(i) of the invariant. If the \active path" is changed, it is only because part of it is contracted, so
part (ii) of the invariant is maintained.
When the DFS nishes visiting a vertex w:
No edge is added and no cycle is contracted, so part (i) is clearly maintained. Let u be the new
current vertex, i.e., w's parent in the DFS tree. If U = W, then part (ii) is clearly maintained.
Otherwise, consider the set D of descendants of w in the DFS tree. Since the original graph is
strongly connected, some edge (x;y) in the original graph goes from the set D to its complement
VBnZrD. All vertices in D have been visited, so (x;y) is in G
0
. By part (i) of the invariant, the vertex
19
active
active
root
inactive
W
active
U
inactive
inactive
inactive
Figure 7: Contracted graph G
0
=S.
in G
0
=S containing x must be W, while the vertex in G
0
=S containing y must be U. Otherwise the
edge corresponding to (x;y) in G
0
=S would create a long cycle.
The algorithm maintains the contracted graph G
0
=S using a union-nd data structure [36]
to represent the vertices in the standard way and using three data structures to maintain the
branching, the reverse edges discovered so far, and the \active path". When a cycle arises in G
0
=S,
it must be of the form described in the proof of Lemma 4.4 and illustrated in Fig. 7. Using these
data structures, the algorithm discovers it and, if it is long, contracts it in a number of union-nd
operations proportional to the length of the cycle. This yields an O(m(m;n))-time algorithm.
The vertices of G
0
=S are represented in union-nd sets as follows:
Make-Set(v): Adds the setfvgcorresponding to the new vertex of G
0
=S.
Find(v): Returns the set in G
0
=S that contains vertex v.
Union(u;v): Joins into a single set the two sets corresponding to the vertices in G
0
=S containing
G
0
's vertices u and v.
The data structures representing the branching, reverse edges, and the active paths, respectively
are:
from-root[W]: For each branching edge (U;W) in G
0
=S, from-root[W] = (u;w) for some (u;w)2
(UW)\E.
to-root[U]: For each reverse edge (U;W) in G
0
=S, to-root[U] = (u;w) for some (u;w) 2 (U 
W)\E.
to-active[U]: For each vertex U on the \active path" in G
0
=S, to-active[U] = (u;w)where (u;w)2
(UW)\E and W is the child of U for which the recursive DFS call is currently executing,
unless no recursive DFS is executing, in which case to-active[U] = current.
For all other vertices, to-active[U] = nil.
20
Contract-Cycles
3
(G = (V;E)) |
Pseudo-code.
1 S fg
2 Choose r2V.
3 DFS(r)
4 Add 2-cycles remaining in G
0
=S to S.
5 return S
DFS(u) |
1 to-active[Find(u)] current
2 for each vertex w adjacent to u | traverse edge (u;w) |
3 if (w is not yet visited) | new vertex |
4 Make-Set(w)
5 to-active[Find(u)] from-root[Find(w)] (u;w)
6 DFS(w)
7 to-active[Find(u)] current
8 else | edge creates cycle in G
0
=S |
9 if (Find(u)6= Find(w)) | cycle length at least 2 |
10 (x;y) from-root[Find(u)]
11 if (Find(x) = Find(w)) | length two cycle through parent, UBnZrWBnZrU |
12 to-root[Find(u)] (u;w) | record edge to parent |
13 else
14 (x;y) from-root[Find(w)]
15 if (Find(x)6= Find(u)) | not a forward edge to child; length of cycle3 |
16 Contract-Cycle(w)
17 S S[f(u;w)g
18 to-active[Find(u)] nil
Figure 8: Practical implementation of Contract-Cycles
3
.
Pseudo-code for the algorithm is given in Figures 8 and 9.
By the preceding discussion, the algorithm implements Contract-Cycles
3
. It is straightfor-
ward to show that it runs in O(m(m;n)) time. Hence, we have the following theorem.
Theorem 4.5 There is an O(m(m;n))-time approximation algorithm for the minimum SCSS
problem achieving a performance guarantee of 1:75 on an m-edge, n-vertex graph.
Here (m;n) is the inverse-Ackermann function associated with the union-nd data structure [36].
Open Problems: The main open problem is to obtain a performance ratio better than 2 for the
weighted strong connectivity problem.
5 Connectivity Augmentation
Let G = (V;E) be a graph with a non-negative weight function w on the edges. Let G
0
= (V;E
0
)
be a subgraph of G. The goal is to add a minimum weight set of edges Aug, to G
0
, such that the
resulting graph is -connected for a given . We are permitted to only add edges from the graph
G. For  > 1, the problem is NP-hard. For  = 2, an approximation algorithm that achieved a
21
Contract-Cycle(w) |
1 while (to-active[Find(w)]6= current) do
2 if (to-active[Find(w)] = nil) then | Go up towards l. c. a. along reverse edges. |
3 (c;p) to-root[Find(w)]
4 a to-active[Find(p)]
5 else | Go down from l. c. a. along active path. |
6 (p;c) to-active[Find(w)]
7 a to-active[Find(c)]
| Contract parent p and child c. |
8 f  from-root[Find(p)]
9 t to-root[Find(p)]
10 Union(p;c)
11 to-active[Find(w)] a
12 from-root[Find(w)] f
13 to-root[Find(w)] t
Figure 9: Subroutine Contract-Cycle.
factor of 2 was given by Frederickson and JaJa [11] when G
0
is a connected graph. (If G
0
is not
connected initially, we may add a minimum spanning tree to connect its connected components.)
Here we present a simplication of the algorithm developed by Khuller and Thurimella [27]. We
describe algorithms for both the edge and vertex connectivity problems. We also show that an
approximation factor of 2 can be achieved in polynomial time for any . This is done by an
extension of the algorithm described in Subsection 2.1.
We rst describe some notation used in this section. The 2 vertex-connected components of a
graph are also referred to as blocks. For a vertex v in a rooted tree BnZr, let the components formed
by the deletion of v be called C
1
(v);C
2
(v);:::;C
d(v)
(v), where d(v) is the degree of v in BnZr. If v
is not the root, we will assume that C
1
(v) is the component that contains the root, and the other
components correspond to subtrees rooted at the children of vertex v. In a rooted tree, for a vertex
u we denote its parent by p(u).
Notation: we refer to an undirected edge between two vertices x and y as (x;y). On the other
hand, a directed edge from x to y is denoted by x!y.
5.1 Increasing Edge Connectivity from 1 to 2
Notice that we only need toshow how to increase the edge connectivity of a tree due to the following
observation. If we are given G
0
with nontrivial 2 edge-connected components, then we can shrink
the vertex sets of these components into single vertices, resulting in a tree whose edges are the
bridges of G
0
. The edges to be retained from Feasible are the minimum weight edges that connect
vertices in dierent 2 edge-connected components of G
0
. (Observe that the edges of Feasible that
connect vertices ofthe same 2 edge-connected component are of no use in augmenting G
0
. Similarly,
among the edges that connect two distinct 2 edge-connected components only the minimum weight
edge is of interest.)
From G
0
, we will construct a directed graph G
D
and nd a minimum weight branching from a
vertex r. (If there is no branching that spans all the vertices, we can show that there is no way to
22
increase the connectivity of the network.) Using a minimum weight branching of G
D
, we can nd
a set of edges of GBnZrG
0
whose addition will increase the connectivity of G
0
. We can also show
that the total weight of the edges added by this technique is no more than twice the weight of an
optimal augmentation.
The algorithm is as follows:
(1) (Construct G
D
= (V;E
D
))
(a) Pick an arbitrary leaf r and root the tree G
0
at r by directing all the edges towards the
root. Denote the resulting tree by BnZr.
(b) Add to E
D
the directed tree edges of BnZr and set their weight to zero.
(c) Consider the edges that belong to G = (V;E) but do not belong to G
0
(edges in EBnZrE
0
).
For each such edge (u;v), if (u;v) is a back edge (i.e., it connects a vertex to one of its
ancestors), we add one directed edge to E
D
(shown below); otherwise, we add two directed
edges to E
D
. (We will refer to these directed edges as images of (u;v), and we say these
directed edges are generated by (u;v).)
Suppose that the edge e with weight w(e), joins vertices u and v belonging to the tree BnZr.
There are two cases depending on the relative locations of u and v in the tree BnZr (see Fig 10).
(i) If u is an ancestor of v (the converse is symmetric): then add an edge u!v in G
D
with
weight w(e).
(ii) If neither u nor v is an ancestor of the other: let t = l:c:a(u;v) (least common ancestor
in the rooted tree BnZr). Add edges t!u and t!v in G
D
, each with weight w(e).
(2) Find a minimum weight branching in G
D
rooted at r. For each directed edge e that is
picked as part of the branching, and that does not belong to the directed tree BnZr, add the
corresponding edge in EBnZrE
0
that generated e. The set of edges added is Aug.
Observe that all edges of G
D
BnZrBnZr are such that they connect a vertex to one of its descendants in
BnZr.
Lemma 5.1 If G is 2 edge-connected, then the directed graph G
D
is strongly connected.
Proof. Clearly, all the vertices of G
D
can reach the root r using edges from the tree BnZr. Further,
let us assume that G
D
is not strongly connected. Of all the vertices that cannot be reached from
the root, let u be the vertex that is closest to the root in BnZr. Clearly, the entire subtree rooted at u
must consist of unreachable vertices. Since the image of the edge (u;p(u)) in G is not a bridge in
G, there must be another edge (v;s) in G going from a vertex v that is in the subtree rooted at u,
to vertex s that is not in this subtree.
Such an edge would have generated a directed edge from a vertex w to v in G
D
where w is an
ancestor of v (specically the least-common-ancestor of v and s). Since w is a proper ancestor of
u, it is reachable from r in G
D
. Therefore v is reachable from r, and hence u as well. Thus we
obtain a contradiction.
Lemma 5.2 If G is 2 edge-connected, then the edge connectivity of the graph G
0
together with the
edges in Aug is at least 2.
23
u
v
v
u
(b)(a)
t
r
r
Figure 10: Construction of G
D
.
Proof. Assume G is 2 edge-connected. Then by the previous lemma, we can nd a minimum
weight branching in G
D
. Next, assume that despite the addition of the edges in Aug to G
0
, the
resulting graph has bridges. All such bridges are the tree edges in BnZr. Let (u;p(u)) be one such edge
of BnZr that is closest to the root (it does not have to be unique). Since vertices in the subtree rooted
at u, are reached from r in the branching it must be the case that there is a directed edge w!v,
from a vertex w (ancestor of u) to v in the minimum weight branching. Such an edge would have
been generated by an edge connecting v to a vertex not in the subtree rooted at u. This edge would
belong to Aug and hence the edge (u;p(u)) is not a bridge.
Lemma 5.3 The weight of Aug is less than twice the optimal augmentation.
Proof. We prove the lemma by exhibiting a branching whose weight is at most twice the weight
of the optimal augmentation. Consider the minimum weight set of edges Aug

that would increase
the connectivity from 1 to 2. Consider all the directed edges that are \generated" by edges that
belong to Aug

. These directed edges together with the tree edges yield a strongly connected graph
with total weight on the edges at most 2C

(each edge of weight w generated at most two directed
edges, each of weight w). Hence the branching that we nd has total weight at most 2C

.
Theorem 5.4 There is an approximation algorithm to nd an augmentation to increase the edge
connectivity of a connected graph to 2 with weight less than twice the optimal augmentation that
runs in O(m+ nlogn) time.
Proof. The correctness of the algorithm follows from Lemma 2 and Lemma 3. Since the bridge-
connected components can be found in O(m+n) time [3] and a minimum weight branching can be
found in O(m+nlogn) time [14]. Since the least common ancestors for the m pairs can be found
in O(m+n) time by using the algorithm of Harel and Tarjan [20], the theorem follows.
24
f4g
f3g
f7gf8g
| cut vertex
| block vertex
fg
(b)
5
b
1
b
2
b
3
b
4
b
5
f1;2g
fg
f5;6g
f9;10g
B
5
B
4
B
3
B
2
B
1
10
9
8
7
6
4
3
2
1
(a)
Figure 11: Construction of block cut vertex tree BnZr.
5.2 Increasing Vertex Connectivity from 1 to 2
We can assume w.l.o.g. that G
0
is a connected graph just as in the case of edge connectivity. Our
overall strategy is similar to the one used in the previous section. That is, we rst obtain a tree
structure BnZr of the blocks of G
0
, construct a weighted, directed graph G
D
using BnZr and G. Then nd
a minimum weight branching in G
D
which will indicate the edges of EBnZrE
0
that are to be added
to increase the connectivity of G
0
. We remark that BnZr, in the case of vertex connectivity, is quite
dierent from that of the previous section.
We rst describe an algorithm to construct the block cut tree.
(1) Let a
1
;a
2
;:::and B
1
;B
2
;:::be the articulation points and blocks of G
0
= (V;E
0
), respectively.
The vertex set V(BnZr) is a union of V
a
and V
b
where V
a
= fa
1
;a
2
;:::gand V
b
= fb
i
j B
i
is a
block of G
0
g. Associated with each vertex in V(BnZr), is a set. For a
i
2 V
a
, X
i
= fa
i
g. For
b
i
2V
b
, Y
i
=fv
j
jv
j
2V and v
j
is not a cut vertex in G
0
g.
(2) The edge set E(BnZr) consists of edges (a
i
;b
j
) where a
i
is an articulation point that belongs to
block B
j
.
Fig. 11 illustrates the above construction via an example.
Observation: In the block cut tree BnZr, each edge is between a vertex in V
a
and a vertex in V
b
.
Observation: Consider the sets associated with the vertices of BnZr. Each vertex of G
0
belongs to
exactly one such set.
In the rest of the section, for a vertex u of V, the vertex of BnZr that corresponds to u is u if u is
an articulation point, and b
i
otherwise where B
i
is the unique block containing u. In the following,
25
by superimposing an edge (x;y)2G on BnZr, we mean adding an edge between a;b2V(BnZr) where the
associated sets X and Y contain x and y respectively.
The algorithm is as follows:
(1) Superimpose all the edges of EBnZrE
0
on BnZr. Discard all the self-loops. Among the multiple
edges retain the cheapest edge, discarding the rest.
(2) (Construct G
D
= (V;E
D
))
(a) Pick an arbitrary leaf of BnZr to be the root r, and direct all the edges of BnZr towards r.
Continue to denote the resulting tree by BnZr.
(b) Add to E
D
the directed tree edges of BnZr and set their weight to zero.
(c) Consider the superimposed edges of EBnZrE
0
on BnZr. Let (u;v) be one such superimposed
edge. If (u;v) is a back edge (i.e. it connects a vertex to one of its ancestors), we add one
directed edge to E
D
(shown below); otherwise, we add four directed edges to E
D
. (We will
refer to these directed edges as images of (u;v), and we say these directed edges are generated
by (u;v).)
Suppose that the edge e with weight w(e), joins vertices u and v belonging to the tree BnZr.
There are two cases depending on the relative locations of u and v in the tree BnZr (see Fig. 12).
(i) If u is an ancestor of v (the other case is symmetric): then add an edge u! v in G
D
with weight w(e).
(ii) If neither u nor v is an ancestor of the other: let t = l:c:a(u;v) (least common ancestor
in the rooted tree BnZr). Add edges t!u and t!v in G
D
, each with weight w(e). Also
add edges u!v and v!u, each with weight w(e).
(d)Modify E
D
as follows. Forevery u2V
a
, if there is anoutgoing edge fromu toadescendant
v, then replace that edge with u
v
!v where where u
v
is the child of u on the tree path from
u to v.
(3) Find a minimum weight branching in G
D
rooted at r. For each directed edge e that is picked
as part of the branching, and does not belong to the directed tree BnZr, add the corresponding
edge in EBnZrE
0
that generated e. The set of edges added is Aug.
In the directed graph G
D
there are no outgoing edges from a cut vertex to any of its descendants
in BnZr.
Observation: Consider the components formed on the deletion of a vertex u2V
a
from BnZr. The
edges of G when superimposed on BnZrBnZru connect all these components.
Lemma 5.5 If G is 2 vertex-connected, then the directed graph G
D
is strongly connected.
Proof. Clearly all the vertices of G
D
can reach the root r using edges of the tree BnZr. Let us assume
that G
D
is not strongly connected. Of all the vertices that cannot be reached from the root, let
u be a vertex that is closest to the root in BnZr. Clearly, the entire subtree rooted at u must consist
of unreachable vertices and every proper ancestor of u is reachable from r. The proof is a little
involved and we break it into cases.
26
edges of E BnZrE
0
(a) Rooted tree BnZr and (c) G
D
after step 2(d)(b) G
D
after step 2(c)
r
r
r
Figure 12: Construction of G
D
in the case of vertex connectivity.
Case 1: u2V
a
.
Since u is not a cut vertex in G, there must be at least one edge connecting a vertex in C
1
(u)
to some vertex in C
i
(u) by the Observation. Let this edge be (v;s) where s 2 C
1
(u) and
v2C
i
(u). Now there are two subcases to consider:
(a) s is an ancestor of v.
(i) s2V
a
.
Corresponding to edge (s;v) we added an edge in G
D
, from the child s
v
of s (on the
path from s to v) to v. Since s
v
is a block vertex, it is distinct from u. Clearly s
v
is an ancestor of u, and hence reachable from r. Thus v is reachable from r and so
is u, yielding a contradiction.
(ii) s2V
b
.
We add an edge in G
D
from s to v. Since s is reachable from r (because it is an
ancestor of u), so is v and hence u, yielding a contradiction.
(b) s is not an ancestor of v. Let t = l:c:a(s;v).
(i) t2V
a
.
Corresponding to edge (s;v) we added an edge in G
D
, from the child t
v
of t (on the
path from t to v) to v. Since t
v
2V
b
, it is distinct from u. It is reachable from r
and hence v is reachable from
r, and so is u, yielding a contradiction.
(ii) t2V
b
.
Clearly t is an ancestor of u, hence reachable from r. We added an edge in G
D
from
27
t to v, hence v is reachable and u as well, yielding a contradiction.
Case 2: u2V
b
.
Consider the cut vertex p(u). Notice that p(u) 6= r since r 2 V
b
. Let the roots of the
subtrees C
1
(p(u));C
2
(p(u));:::C
k
(p(u)) be r
1
(= r);r
2
;:::r
k
, where k is the degree of p(u).
Assume that C
2
(p(u)) refers to the component containing u (hence r
2
= u). Partition the
components into two groups as follows. The rst group contains all the components whose
roots are reachable from r, and the second group contains the rest. (Notice that both the
groups are non-empty.) Since G is biconnected there must exist an edge (s;v)where s belongs
to a vertex in C
i
(p(u)) and v belongs to a vertex in C
j
(p(u)), such that C
i
(p(u)) and C
j
(p(u))
belong to the rst and second groups respectively.
(a) s is an ancestor of v.
(i) s2V
a
.
We added an edge from the child s
v
of s to v in G
D
. Since s
v
is a block vertex, it is
distinct from p(u) and reachable from r. Hence v is reachable from r, and so is r
j
giving a contradiction.
(ii) s2V
b
.
We added an edge in G
D
from s to v. Since s is an ancestor of p(u) it is reachable
from r. Hence v is reachable from r, and so is r
j
, giving a contradiction.
(b) s is not an ancestor of v. Let t = l:c:a(s;v).
(i) t6= p(u).
There is an edge in G
D
from either t or t
v
, to v. Since both t and t
v
are reachable
from r, so is v and hence r
j
, giving a contradiction.
(ii) t = p(u).
Note that r
i
is reachable from r. Because of edge (s;v) we generate the following
edges in G
D
: r
i
!s;r
j
!v;s!v;v!s. Hence v is reachable from r, and so is
r
j
, yielding a contradiction.
Lemma 5.6 If G is 2 vertex-connected, then the vertex connectivity of the graph G
0
together with
the edges in Aug is at least 2.
Proof. Assume that despite the addition of the edges in Aug to G
0
, the resulting graph has a
cut vertex u. We will now show that u is destroyed as a cut vertex in the tree BnZr, and hence in
G
0
. Consider the components C
1
(u);:::;C
d(u)
(u) in BnZr. Partition the components into two groups
as follows. The rst group contains all the components that get connected to C
1
(u) (by an edge
or a path) when the edges of Aug are superimposed on BnZr. The second group contains the rest.
Notice that both the groups are non-empty. Since G
D
is strongly connected all the vertices are
reachable from the root in the minimum weight branching. Since there are no outgoing edges from
u to its descendants by the previous observation, there must be an edge s ! v in the branching
that satises the following. This edge has the property that s2C
i
(u) and v2C
j
(u), where C
i
(u)
and C
j
(u) belong to the rst and second groups respectively. The edge that generated s ! v in
Aug would connect C
i
(u) to C
j
(u) in G
0
+ Aug, yielding a contradiction.
Lemma 5.7 The weight of Aug is less than twice the optimal augmentation.
28
Proof. We prove the lemma by exhibiting a branching whose weight is at most twice the weight
of the optimal augmentation. Consider the minimum weight set of edges Aug

that would increase
the connectivity from 1 to 2. Consider all the directed edges that are \generated" by edges that
belong to Aug

.
These directed edges together with the tree edges yield a strongly connected graph with total
weight on the edges at most 4C

(each edge of weight w
i
generated at most four directed edges,
each of weight w
i
). Now pick a minimum weight branching in this graph. Notice that for each
cross edge (u;v) (when neither u nor v is an ancestor of the other) even though we generate four
directed edges in G
D
, no minimum weight branching will use more than two of these four edges.
(Otherwise, it will not be a valid branching.) Hence the branching that we nd has total weight at
most 2C

.
Theorem 5.8 There is an approximation algorithm to nd an augmentation to increase the vertex
connectivity of a connected graph to 2 with weight less than twice the optimal augmentation that
runs in O(m+ nlogn) time.
Proof. Thecorrectnessofthealgorithm followsfromLemma 5andLemma6. Since thebiconnected
components can be found in O(m + n) time [3] and a minimum weight branching can be found
in O(m + nlogn) time [14]. Since the least common ancestors for the m pairs can be found in
O(m+n) time by using the algorithm of Harel and Tarjan [20], the theorem follows.
5.3 Increasing Connectivity to 
We argue that it is possible to obtain an approximation factor of 2 for increasing the edge con-
nectivity of a graph to any . The algorithm takes as input an undirected graph G
0
(V;E
0
) on n
vertices and a set Feasible of m weighted edges on V, and nds a subset Aug of edges which when
added to G
0
make it -edge connected. The weight of Aug, is no more than twice the weight of
the least weight subset of edges of Feasible that increases the connectivity. We also observe that
the problem is NP-hard (for any ) by extending the proof that was given by [11] for incrementing
1-connected graphs to 2-connected optimally.
Consider a directed graph G with weights on the edges, and a xed root r. How does one nd
the minimum weight directed subgraph H
D
that has -edge disjoint paths from a xed root r to
each vertex v ? Gabow [13] gives the fastest implementation of a weighted matroid intersection
algorithm to solve this problem in O(n(m+nlogn)logn) time.
To solve our problem (approximation algorithm), in the undirected graph G
0
replace each
undirected edge (u;v) by two directed edges u!v and v!u with each edge having weight 0. For
each edge in the set Feasible(u;v) we replace it by two directed edges u!v and v!u with weight
w(u;v) (the weight of the undirected edge). Call this graph G
D
. Now run Gabow's algorithm on
the graph G
D
, asking for -edge disjoint paths from each vertex to the root. If the directed edge
u!v is picked in H
D
and w(u;v) > 0 (we can assume all edges of set Feasible have weight > 0
else we can always include it in Aug) we add (u;v) to Feasible. (This is a generalization of the
scheme for the case when E
0
is empty.)
Open Problems: The main open problem is to obtain factors better than 2 for the unweighted
augmentation problem. Even simple greedy algorithms appear to have a performance ratio of 1:5.
Acknowledgements: I am grateful to Dorit Hochbaum and Balaji Raghavachari for useful com-
ments. Support by NSF grant CCR-9307462 is gratefully acknowledged.
29
References
[1] A. Agrawal, P. Klein and R. Ravi, When trees collide: An approximation algorithm for
the generalized Steiner problem on networks, Proc. 23rd ACM Symposium on Theory of
Computing, pp. 134{144, (1991).
[2] A. V. Aho, M. R. Garey and J. D. Ullman, The transitive reduction of a directed graph,
SIAM Journal on Computing, 1 (2), pp. 131{137, (1972).
[3] A. V. Aho, J. E.Hopcroft and J. D.Ullman, The design and analysis of computer algorithms,
Addison-Wesley, (1974).
[4] S. Arnborg, J. Lagergren and D. Seese, Easy problems for tree-decomposable graphs, Journal
of Algorithms, 12 (2), pp. 308{340, (1991).
[5] J. Cheriyan, M. Y. Kao and R. Thurimella, Algorithms for parallel k-vertex connectivity and
sparse certicates, SIAM Journal on Computing, 22 (1), pp. 157{174, (1993).
[6] J. Cheriyan and R. Thurimella, Algorithms for parallel k-vertex connectivity and sparse
certicates, Proc. 23rd Annual Symposium on Theory of Computing, pp. 391{401, (1991).
[7] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to algorithms, The MIT Press,
(1989).
[8] J. Edmonds, Matroid intersection, Annals of Discrete Mathematics, 4, pp. 185{204, (1979).
[9] K. P. Eswaran and R. E. Tarjan, Augmentation problems, SIAM Journal on Computing, 5
(4), pp. 653{665, (1976).
[10] A. Frank, Augmenting graphs to meet edge-connectivity requirements, SIAM Journal on Dis-
crete Mathematics, 5(1), pp. 25{53, (1992).
[11] G. N. Frederickson and J. JaJa, Approximation algorithms for several graph augmentation
problems, SIAM Journal on Computing, 10 (2), pp. 270{283, (1981).
[12] A. Frank and E. Tardos, An application of submodular 
ows, Linear Algebra and its Appli-
cations, 114/115, pp. 320{348, (1989).
[13] H. N. Gabow, A matroid approach to nding edge connectivity and packing arborescences,
Proc. 23rd Annual Symposium on Theory of Computing, pp. 112{122, (1991).
[14] H. N. Gabow, Z. Galil, T. Spencer and R. E. Tarjan, Ecient algorithms for nding min-
imum spanning trees in undirected and directed graphs, Combinatorica, 6 (2), pp. 109{122,
(1986).
[15] M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of
NP-completeness, Freeman, San Francisco, (1979).
[16] N. Garg, V. Santosh and A. Singla, Improved approximation algorithms for biconnected
subgraphs via better lower bounding techniques, Proc. 4th Annual ACM-SIAM Symposium
on Discrete Algorithms, pp. 103{111, (1993).
30
[17] M. Goemans and D. Bertsimas, Survivable Networks, Linear Programming Relaxations and
the Parsimonious Property, Mathematical Programming, 60, pp. 145{166, (1993).
[18] M. Goemans and D. Williamson, A general approximation technique for constrained forest
problems, Proc. 3rd Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 307{316,(1992).
[19] F. Harary, The maximum connectivity of a graph, Proc. Nat. Acad. Sci., 48, pp. 1142{1146,
(1962).
[20] D. Harel and R. E. Tarjan, Fast algorithms for nding nearest common ancestors, SIAM
Journal on Computing, 13(2), pp. 338{355, (1984).
[21] H. T. Hsu, An algorithm for nding a minimal equivalent graph of a digraph, Journal of the
ACM, 22 (1), pp. 11{16, (1975).
[22] T. S. Hsu, Graph Augmentation and Related Problems: Theory and Practice, Ph. D thesis,
Dept. of Computer Science, University of Texas, Austin, TX (1993).
[23] S. Khuller and B. Raghavachari, Improved Approximation Algorithms for Uniform Connec-
tivity Problems, manuscript (1994).
[24] S. Khuller, B. Raghavachari and N. Young, Approximating the minimum equivalent digraph,
Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 177{186, (1994). To
appear in SIAM Journal on Computing.
[25] S. Khuller, B. Raghavachari and N. Young, On strongly connected digraphs with bounded
cycle length, UMIACS-TR-94-10/CS-TR-3212, (1994).
[26] S. Khuller and R. Thurimella. Approximation algorithms for graph augmentation, Proc. 19th
International Colloquium on Automata, Languages and Programming Conference, pp. 330{
341, (1992).
[27] S. Khuller and R. Thurimella. Approximation algorithms for graph augmentation, Journal
of Algorithms, 14 (2), pp. 214{225, (1993).
[28] S. Khuller and U. Vishkin, Biconnectivity approximations and graph carvings, Journal of the
ACM, 41 (2) pp. 214{235, (1994).
[29] P. N. Klein and R. Ravi, When cycles collapse: A general approximation technique for
constrained two-connectivity problems, Proc. 3rd Integer Programming and Combinatorial
Optimization Conference, pp. 39{56, (1993).
[30] D. E. Knuth, Fundamental Algorithms, Addison-Wesley, Menlo Park, CA, (1973).
[31] D. M. Moyles and G. L. Thompson, An algorithm for nding the minimum equivalent graph
of a digraph, Journal of the ACM, 16 (3), pp. 455{460, (1969).
[32] D. Naor, D. Guseld and C. Martel, A fast algorithm for optimally increasing the edge-
connectivity,Proc.31stIEEE Symposium onFoundations ofComputer Science, pp. 698{707,
(1990).
31
[33] H. Nagamochi and T. Ibaraki, Linear time algorithms for nding sparse k-connected span-
ning subgraph of a k-connected graph, Algorithmica, 7 (5/6), pp. 583{596, (1992).
[34] T. Nishizeki and S. Poljak, Highly connected factors with a small number of edges, to appear
in Discrete Applied Mathematics.
[35] R. Ravi and D. Williamson, An approximation algorithm for minimum-cost vertex-
connectivity problems, to appear in Proc. 6th Annual ACM-SIAM Symposium on Discrete
Algorithms, (1995).
[36] R. E. Tarjan, Data structures and network algorithms, Society for Industrial and Applied
Mathematics, (1983).
[37] R. Thurimella, Techniques for the design of parallel graph algorithms, Ph. D thesis, Dept. of
Computer Science, University of Texas, Austin, TX (1989).
32