Edge-Connectivity Augmentation Preserving Simplicity.
Given a simple graph G=(V,E), our goal is to find a smallest set F of new edges such that G=(V,E\cup F) is k-edge-connected and simple. Recently this problem was shown to be NP-complete. In this paper we prove that if  OPT_P^k$ is high enough---depending on k only---then OPT _S^k= OPT_P^k$ holds, where OPT_S^k$ (OPT_P^k$) is the size of an optimal solution of the augmentation problem with (without) the simplicity-preserving requirement, respectively. Furthermore, OPT_S^k- OPT _P^k\leq g(k) holds for a certain (quadratic) function of k. Based on these facts an algorithm is given which computes an optimal solution in time O(n4) for any fixed k. Some of these results are extended to the case of nonuniform demands as well.
Introduction
In the last decade several graph augmentation problems have been investigated. Especially
the connectivity augmentation problems attracted considerable attention due to the various
connections to the so-called network design problems which model the survivability
problems of (telephone or computer, etc) networks. In these problems a graph (or digraph)
G and a target connectivity number k are given and the goal is to find a smallest set F
of new edges which makes G k-edge-connected, that is, for which the augmented graph
k-edge-connected and jF j is as small as possible. (Sometimes the goal
is to increase vertex-connecivity of G. In this paper we consider only edge-connectivity
problems, unless stated otherwise.) Note, that the set F of new edges may contain parallel
edges and edges which are parallel to edges of G, as well.
The edge-connectivity augmentation problem - and a number of its extensions - can
be solved efficiently. Several polynomial algorithms have been developed, see [6], [17], [20]
Department of Mathematics and Computer Science, Odense University, Campusvej 55, DK-5230
Odense, Denmark. The second author was supported by the Danish Natural Science Research Council
grant no. 28808.
and also [2], [9], [16], just to mention some important results. (For a survey of this area
see [7].)
However, there are several versions of the connectivity augmentation problem which
remained open. Sometimes the goal is to increase the connectivity by maintaing certain
properties of the starting graph G. Depending on these properties, one obtains problems
of very different nature. For example, Kant and Bodlaender [13] consider the problem
where the goal is to increase vertex-connectivity and the planarity of G is to be preserved
(and they prove that this version is NP-complete). Hsu and Kao [10] want to maintain
bipartiteness while increasing a variant of vertex-connectivity of a graph (and they show
that this can be done in polynomial time). Recently, Gabow, Szigeti and the authors proved
in [1] that edge-connectivity can be optimally increased in polynomial time preserving
bipartiteness (or in general, l-partiteness).
In this paper we deal with another property to be preserved: the simplicity of G. As it
is mentioned in [7], "it is an important open problem to find algorithms that do not add
parallel edges". Partial results in this direction have been obtained by Frank and Chou [8],
Naor et al. [17], Taoka et al. [18], and Watanabe and Yamakado [19] - the details are given
below -, but the complexity of the general problem was still open. Very recently the second
author proved that the simplicity preserving k-edge-connectivity augmentation problem is
NP -complete, even if the starting graph is already 1)-edge-connected. However, we
shall prove that the problem becomes polynomially solvable if the target connectivity k is
fixed. We shall give an O(n 4 ) algorithm for this variant.
E) be an l-edge-connected simple graph such that jV j 1. The
simplicity preserving k-edge-connectivity augmentation problem is to find a smallest set F
of new edges which makes G k-edge-connected without creating parallel edges, that is,
must be a k-edge-connected simple graph and subject to this jF j must be
minimal. Such an F is called an optimal simple augmentation of G (with respect to k).
The very first paper which deals with a similar problem is due to Frank and Chou from
1970. In [8] they solve the simplicity preserving edge-connectivity augmentation problem
in the special case where the starting graph G has no edges - but the target connectivity
may be non-uniform, that is, the edge-connectivity requirements may be different between
different pairs of vertices. Besides the solution of this version - which is in fact a construction
problem rather than an augmentation problem - there are some recent results which
all deal with small target connectivity values k or solve some very special case for general
k.
Let us denote the size of a smallest k-edge-connected (k-edge-connected and simple)
augmentation of a graph G by OPT k
S (G), respectively). Obviously OPT k
S for any k and any graph G.
It can be checked easily, that the linear-time 2-edge-connectivity augmentation algorithm
of Eswaran and Tarjan [4] does not create parallel edges, thus solves the simplicity-
preserving version, too, for 2. It was proved in [19] that OPT k
P holds for
as well, by showing a polynomial algorithm which solves the 3-edge-connectivity
augmentation problem optimally without creating parallel edges.

Figure

1: OPT 4
2.
This is not the case in general. As it was observed already in [18], OPT k
may hold if k - 4, see Figure 1. On the other hand, it was also shown in [18] that
moreover, in these special cases we
have In [17] it was observed that OPT k
and the minimum degree in G is at least k.
Besides the construction of a polynomial algorithm for any fixed k our goal in this
paper is to show that there exist functions f; N such that if OPT k
then OPT k
P (G), and OPT k
graph G. These
results are presented in Section 3. Specializing our proofs to the case where l
we give simpler proofs for (extensions of) some results of [18] in Section 4. In Section 5 we
indicate how our main results can be extended to the case where local edge-connectivity
demands must be satisfied.
2 Terminology and some basic results
In this section we first introduce the basic notation and definitions and then list those
theorems and algorithms (mostly from Frank's paper [6]) which we shall use in our proofs.
We shall assume that the reader is familiar with the results of [6].
E) be an undirected graph. For two disjoint subsets X and Y of V the
number denotes the number of edges between X and Y and we define the degree
of a subset X as d(X) := set consisting of a single vertex v is simply
denoted by v. Thus d(v) stands for the degree of v. The degree-function of a graph G 0
will be denoted by d 0 . An edge connecting the vertices x and y will be denoted by xy.
Sometimes xy will refer to an arbitrary copy of the parallel edges between x and y but
this will not cause any confusion. Adding or deleting an edge e from a graph G is often
denoted by G e, respectively. Adding (or deleting) a set Y of vertices to a
set X of vertices is denoted by X respectively). For a set F of edges
denotes the set of endvertices of edges of F . The subgraph of G induced by a subset X of
vertices is denoted by G[X]. Let \Delta(G) denote the maximum degree of the graph G. For
a vertex v we use N(v) to denote the set of vertices adjacent to v. A subpartition of V
is a collection of pairwise disjoint subsets of V .
The operation splitting off a pair vs; st of edges (v 6= t) from a vertex s means that
we replace the edges vs; st by a new edge vt. A complete splitting from a vertex s (with
even degree) is a sequence of d(s)=2 splittings of pairs of edges incident to s. A graph
E) is k-edge-connected if
The edge-connectivity of G is the largest integer k for which G is k-edge-connected.
The local edge-connectivity -(u; v) between two vertices u; v is the maximum number
of pairwise edge-disjoint paths.
We recall the following well-known equalities.
Proposition 2.1 Let E) be a graph and X;Y ' V . Then
s; E) be a graph with a special vertex s such that (1:1) holds, that is,
the edge-connectivity of G within V is at least k. We say that a pair of edges vs; st is
an admissible pair if after splitting off vs and st condition (1:1) still holds. Otherwise
vs; st form a non-admissible pair. It is easy to see that vs and st are non-admissible if
and only if there exists a set v; t 2 X ae V such that d(X) - k + 1. Such a set is called
dangerous.
The following result of Lov'asz [14, Problem 6.53.] - Theorem 2.2(a) below - is an
important tool in [6]. Here we formulate a kind of extension, as well - part (b) of Theorem
2.2 -, which will be used in some of our arguments. The proof follows easily from the proof
of part (a) given in [6, pp.35-36].
Theorem 2.2 Suppose that (1:1) holds in E) and d(s) ? 0 is even. Then
(a) [14] for every edge st there exists an edge su such that the pair st; su is admissible.
(b) for every edge st the number of edges which are non-admissible with st is at most k +1.
Proof: We prove part (b). Following Frank's proof of part (a) we observe that for
every edge sv for which st and sv is a non-admissible pair the vertex v is either contained
in a unique maximal dangerous set M containing t, or contained in one of two maximal
dangerous sets X;Y whose intersection contains t. Since the edge sv contributes to the

Figure

2: This graph G shows that the Successive Augmentation Property does not hold.
G. The edge is the unique optimal augmentation
with respect to
degree of M (or to the degree of X or Y ), we obtain that in the former case there are at
most k edges which are non-admissible with respect to st, and in the latter case, using
(1:2a) we get
which implies d(X 2, from which d(s; (X
Most of the results in this paper are based on Frank's algorithm from [6] which solves
the augmentation problem without simplicity requirement and uses the splitting operation
as the main tool. Note, that this algorithm does not find all the intermediate optimal augmentations
but only an optimal k-edge-connected augmentation. The
other previously mentioned algorithms either use a one-by-one augmentation approach-
like [2], [17], [20] - or are based on Frank's algorithm [9], [16].
We say that the Successive Augmentation Property holds for a certain augmentation
problem if for any increasing sequence of target-connectivities there exists an
increasing sequence F 1 ae ::: ae F k of solutions such that F i is optimal with respect to k i .
For example this property holds for the edge-connectivity augmentation problem of graphs
and digraphs (with uniform demands), see [3], [20]. Since the Successive Augmentation
Property does not hold for simple augmentations (see Figure 2), using Frank's algorithm
seems to be promising for attacking the general case.
We describe now Frank's algorithm [6] which gives an optimal solution for any given
(not necessarily simple) graph E) and target connectivity k, provided that there
is no simplicity-preserving requirement.
Frank's algorithm
(PHASE 1) Add a new vertex s to V and a set F of new edges between s and some vertices
of V such that
(1:1) holds in G
F is minimal (wrt. inclusion) subject to (2:1) and (2:2): (2:3)
(Remark: It is easy to see that such an F exists. It was shown in [6] that
)there exists a subpartition of V such that jF
is odd in G 0 , add a new parallel edge between s and v for some
with d 0 (s; v) - 1.
(Remark: In Frank's original algorithm the extra edge which makes d 0 (v) even can be
added between s and any v 2 V . However, this small modification in Phase 2 will be
essential in our algorithm.)
admissible pairs of edges incident to s in arbitrary order, maintaining
(1:1). When s becomes isolated, delete s.
(Remark: In the third phase every edge can be split off by Theorem 1.2.a. The resulting
graph is an optimal k-edge-connected augmentation of G since after the second phase
3 Simplicity preserving augmentation with uniform
demands
Our idea is to modify the third phase of Frank's algorithm by introducing some additional
rules which will determine the order of splittings. In certain cases not every admissible pair
will be allowed to be chosen. As we shall see this will make it possible to avoid the creation
of parallel edges and hence to maintain simplicity provided that d 0 (s) is high enough at
the beginning of the third phase. Clearly, if we preserve simplicity during phase 3, the
resulting augmenting set will be optimal for the simplicity-preserving version, too.
If one wants to maintain simplicity while using Frank's algorithm, only those admissible
pairs st; su may be split off for which t and u are not adjacent in the original graph and for
which there is no new edge between t and u (that is, the pair st; su has not been chosen yet
for another edge st and another su). We call such an admissible pair legal. We say that a
complete splitting from s is feasible if the resulting graph is simple and k-edge-connected.
E) be the starting graph and let k - 2 be the target-connectivity.
Theorem 3.1 Let G be a graph at the end of the second phase of Frank's
algorithm and suppose that
holds. Then there exists a feasible complete splitting from s.
Proof: Let S denote the set of neighbours of s. We claim that in the subgraph
induced by S each vertex has at most k neighbours. To see this let us consider
an edge st 2 F . Since F is obtained from a minimal set -
F satisfying (2:1 \Gamma 2:3) by adding
at most one edge e parallel to an edge of -
F , there exists a set X ae V for which t 2 X and
Each edge between t and some vertex in S \Gamma X contributes to the degree of
X, and each neighbour y of t in S " X contributes to the degree of X by at least one by
the existence of the edge sy. Thus
Condition (2:2) implies that jSj - 3k 3 . Since \Delta(H ) - k, there exists - see the easy
exercise [14, Problem 8.1] - a subset T ae S with jT which is
independent in H.
Our proof of the existence of a feasible complete splitting will follow from the analysis of
the following algorithm which is a modified version of the third phase of Frank's algorithm.
The goal is to split off only legal pairs until s becomes isolated.
After each splitting step we update S and H as follows. If we split off a pair st; su
then first the edge tu will be added to H. Then, if the edge st (or su) was the last copy
of the edges between s and t (between s and u, respectively) then we delete t (u) from S
and from H, as well. Thus the current graph H before the next split means the graph of
"forbidden edges" updated this way. Clearly, if we can always find a pair which is legal in
the current H, we obtain a feasible complete splitting.
The algorithm has four parts, executed in the following order.
(1) Split off legal pairs of edges st; su of the form t 2 T and u there are no
parallel edges between s and any vertex of T . (But keep one copy of each edge st, t 2 T .)
(2) Split off legal pairs of edges sv; su of the form v; u long as possible.
(3) Split off all the edges su with u with an edge st, t 2 T , for which st; su is a
legal pair.
off the remaining edges st; su (of the form t;
Let us prove why this algorithm terminates with a complete feasible splitting. First
observe that the proof of Theorem 2.2 (b) combined with the proof of (2:5) above implies
the following statement.
3.2 Let st be an edge and let
2 W be a subset of vertices of the current H such
that t. Then st; su is a legal pair for some
3.2 and the inequality
implies that we can always find legal pairs to split off following the rule of part (1), which
shows that part (1) can be executed.
By Claim 3.2 we obtain that at the end of phase (2) the size of the current
is at most k + 1. Thus in phase (3) at most k(k must be split off for which
are sufficient to maintain feasibility by Claim 3.2. Since
phase (3) can also be executed.
Then the current H, induced by T , is an independent set and after an arbitrary splitting
H always remains independent, since in phase (1) we deleted the parallel edges between s
and vertices of T . Thus in phase (4) we are allowed to split off admissible pairs in arbitrary
order, which will yield a (feasible) complete splitting by Theorem 2.2 (a). \Pi.
Thus we obtain the following corollary, showing that there exists a function f(k) such
that there exists an optimal solution for the k-edge-connectivity augmentation problem
without the simplicity-requirement which preserves simplicity provided that the optimum
value is at least f(k).
Theorem 3.3 If OPT k
If k is small, it is possible to sharpen the previous rough bound on f(k). Using a more
precise analysis we can even obtain the sharp value in the special case
found already in [18], using a different approach). These details are given in Section 3.
Theorem 3.4 OPT k
any starting graph G and any target
connectivity k.
since for any jV j there exist
k-edge-connected simple graphs which are (almost) k-regular. Obviously
E(H) contains a set of edges which makes G k-edge-connected preserving simplicity. Thus
we may assume that jV (G)j - 4k \Gamma 3.
The proof is based on a version of Frank's algorithm. In the last phase certain edges
will not be split off in pairs but will be replaced by one or two new edges using an other
operation. The first two phases are the same. At the beginning of phase 3 we have a set
F of new edges incident to s for which OPT k
holds. In phase 3 first let us
split off legal pairs as long as possible. By Claim 3.2 the number of neighbours of s is at
most no more legal pairs can be found. At this point there is at most one edge
of F which can be deleted without violating (1:1). If there is such an edge, let us delete it.
In the rest of the procedure instead of splitting off pairs of edges we try to replace every
edge incident to s by one or two edges on V , maintaining (1:1) and preserving simplicity.
be an edge in the current G 0 . The criticality of e - with respect to (1:1) -
implies that there exist sets x
us call such a set x-tight in the former case and s-tight in the latter case.
In G 0 there is a unique minimal x-tight set X and there is a unique minimal
set Y , with respect to a fixed edge st. Furthermore, (1:1) holds in G
for any edge e
Proof: Let X be a minimal x-tight set and X 0 be an x-tight set which does not contain
X. In this case by (1:1) and (1:2b) we obtain
a contradiction. This proves that X is unique. The uniqueness of Y can be proved similarly.
be two vertices and e be an edge and suppose that (1:1)
does not hold in G violates (1:1), then W is
x-tight in G 0 and y 0 2 W must also hold. From this it follows that is an s-tight
set in G 0 , which does not contain Y , a contradiction, which proves the claim. \Pi.
Clearly, if X or Y \Gamma s has size at least k, there exist two vertices
such that x 0 and y 0 are non-adjacent in G 0 . Then replacing sx by e maintains (1:1)
and preserves simplicity. Suppose that X and Y \Gamma s have size at most k \Gamma 1. There are at
most are adjacent to x or to some vertex in Y \Gamma s, since
each such vertex contributes to the degree of X or Y \Gamma s. Since we assumed jV
there exists a vertex w which is not adjacent to x and to some vertex y of
replacing e by xw and wy preserves simplicity and it is easy to see that it
maintains (1:1), as well.
Thus substituting the remaining at most k(k incident to s in G 0 by at most
edges we obtain a solution with size at most jF
The graph K   , defined as the disjoint union of two complete graphs K k+1 and K k=2 ,
connected by k=2 independent edges, show that the biggest possible gap between OPT k
and OPT k
P is indeed a quadratic function of k. (It is easy to check that OPT k
Hence the difference in question is k 2
Also note that following the algorithmic part of the proof of the previous theorem one
obtains a 4-approximation algorithm (that is, an algorithm which gives a solution of size at
most 4OPT k
S (G)) for the simplicity-preserving k-edge-connectivity augmentation problem,
provided that k ! n=4. (Its running time is polynomial even if k is not fixed.)
The idea of our algorithm for the augmentation problem with the simplicity requirement
is the following. If OPT k
P is large enough, we can simply follow the algorithmic proof of
Theorem 3.1 which gives a solution with size OPT k
creating parallel edges, thus it
is obviously an optimal simple augmentation. If OPT k
P is small, a trivial way of finding an
optimal solution is to check every possible augmenting set with size less than OPT k
However, although the number of such sets is a polynomial function of n for fixed k, the
exponent still depends on k. To avoid this, we prove that when we check all the possible
augmenting sets we may restrict the set T of possible end-vertices of augmenting edges to
a set of size h(k) for an appropriate function h of k, and that such a T can be fixed in
advance in constant time for any fixed k.
A set X ae V is deficient in E) (with respect to the target-connectivity
k. A set S ' V is a covering of the deficient sets if for every deficient
set X.
It follows from the correctness of Frank's algorithm - and also from Claim 3.5 - that for
every covering S ' V there exists an optimal solution F with V for the problem
without simplicity requirement. This implies that if the optimum value is m, we can easily
find a set S of vertices in G - the covering S, formed by the end-vertices of the new edges
at the end of Phase 1 of Frank's algorithm will do - with size at most 2m, such that there
exists an optimal solution F with V Although in the simplicity-preserving version
a covering S does not have this property in general - consider the graph on Figure 1 -,
we can find a relatively small subset T in this case, too, such that there exists an optimal
solution F S with V
To see this, let G be the starting graph and let S be a covering of the deficient sets
of G. For each vertex y of G let us fix a set L(y) ' N(y) of vertices such that
minfjN(y)j; 2kg. For each vertex t 2 S we define a subset -
M t of vertices of V as follows.
The vertex t itself belongs to -
t if and only if d(t) - 2k \Gamma 1. A vertex x
to -
only if there exists an xt-path P of length at most k for which d(v) -
for every
(v [ L(v)). (It is not hard to see
that We claim that
is a set with
the required property. Note, that S ' T holds and jT j - jSjh(k). (The existence of such a
set with size at most jSjh 0 (k) follows immediately from our previous results. However, to
construct an efficient algorithm, we need to find such a set in advance, without knowing
an optimal solution.)
Theorem 3.6 There exists an optimal simplicity-preserving solution F with V
Proof: Let us choose an optimal simplicity-preserving solution F with jV
as small as possible. If this number is zero, we are done. If not, there exists an edge
for which at least one of its end-vertices is not in T . Without loss of generality
assume that
. If we subdivide e by a new vertex s and then apply Claim 3.5, we
observe that in G [ F \Gamma e we have precisely two (disjoint) minimal deficient sets A; B, for
which a 2 A and b 2 B and for any edge e
is k-edge-connected. Thus it is enough to prove that there exists a vertex
is not adjacent to a in G[F . To prove that such a vertex t exists, it is sufficient to see that
since dG[F replacing e by e 0 would
yield an optimal simple augmenting set F 0 with jV contradicting
the choice of F .)
First let us prove that S " C 6= ; for every component C of the subgraph G[B].
Since B is deficient in G [ e, it is deficient in G as well. Thus, since S covers the
deficient sets, component C of G[B], the set C is not
deficient in G. Thus, since each edge between C and contributes to d(B), we obtain
Now let t 2 S be vertex in the component of G[B] which contains b and let P be (the
set of vertices of) a tb-path in G[B]. Let b 0 be the vertex of P closest to t on P which is
not included in -
M t and let P 0 denote the subpath of P with end-vertices t and b 0 . Then
k, we are done, since jT " Bj - k follows. Assume
now that jP or by the definition of -
M t and
b 0 there exists a z 2
M t with d(z) - 2k. In the former case we let z = t. Then we
obtain that at least k vertices from L(z) belong to B, otherwise dG
a contradiction. Hence
The proofs of the previous three theorems lead to an algorithm whose running time is
O(n 4 ), provided that the target-connectivity k is fixed. Let us scetch the algorithm and
estimate the running time.
The input graph is E). First we add a new vertex s and construct a set F of
new edges - and compute OPT k
of Frank's algorithm. This
can be done in time O(n 2 ) by applying the method of Nagamochi and Ibaraki, see [16]. If
we proceed as described in Case II below. Otherwise we are in Case
I, where OPT S (G) - Theorem 3.4. In this case we identify a
set of vertices as we did before Theorem 3.6. From the algorithmic point of view,
this can be done by computing a restricted BFS-tree from each vertex of S. (The set S,
which consists of the neighbours of s, has size at most 3k 4 in this case.) Thus the number
of steps we need to find T depends on k only. The last phase of Case I is just a series of
k-edge-connectivity tests. We check for each possible set of new edges F 0 of size at most
(and with V simple and k-edge-connected and choose
the smallest good augmentation. Clearly, the number of possibilities is a function of k, and
by Theorem 3.6 we find at least one good augmenting set. The number of steps in one of
these tests in O(n 2 ) [16].
Now let us analyze Case II. By Theorem 3.3 OPT k
holds. First we
identify set T of vertices which is independent in G[S] and has size k 2 1. This can
be done by a greedy search in linear time. Then we follow the four parts of the algorithmic
proof of Theorem 3.1: first split off pairs of edges incident to s between T and . For
this we use the so-called s-based connectivity algorithm from [16] as a subroutine to test
whether a pair is legal or not. One of these tests requires time O(n(m log n)) and the
total number of tests in this first part depends on k only. In the second part we split off
pairs whose end-vertices are in S \Gamma T as long as possible. This requires at most k(k
s-based connectivity tests. (There are at most k edges from each vertex v 2 S to s and by
3.2 after at most k +2 tests we can find a legal pair for each sv, if there is any.) The
remaining two parts consist of some further s-based conectivity test: we split off all pairs
and then within T . These calculations imply the following theorem.
Theorem 3.7 The simplicity-preserving k-edge-connectivity augmentation problem can be
solved in O(n 4 fixed k. \Pi.
4 Augmenting from 3 to 4
In this section we give a full solution for the special case when G is 3-edge-connected and
we want to make it 4-edge-connected. As we remarked, is the smallest target value
where OPT P and OPT S may be different. Our goal is to find the exact values of the
functions f and g in this case. The proof implies an algorithm which does not use a series
of 4-edge-connectivity tests like in Case I of the algorithm of the general case. The main
result of this section, Theorem 4.7, was already obtained by Taoka et al. in [18] - where
most of the proofs are omitted - using a different approach which does not seem to work
for arbitrary values of the target connectivity. We included this section to show how our
method provides a fairly easy complete proof of this result.
set X of vertices in a graph G with edge-connectivity k is called critical if
holds. The following easy lemma is left to the reader.
Lemma 4.1 Let G be simple and 1)-edge-connected but not k-edge-connected. Then
every minimal critical set has size one or at least k. \Pi.
Lemma 4.1 shows that if X and Y are two disjoint critical sets, then there exist two
vertices which are non-adjacent, unless both X and Y are singletons. This
suggests that if the goal is to increase the connectivity by one, without creating new parallel
edges, only those minimal critical sets have an important role which are singletons. The
following lemma will make it possible to assume that every minimal critical is a singleton.
Lemma 4.2 Let E) be a simple graph which is 1)-edge-connected but not
k-edge-connected. There exists a 1)-edge-connected simple graph G   such that
(1) Every minimal critical set in G   is a singleton, i.e. has size one.
Proof: First note that for a minimal critical set X and for a critical set Y either
holds by Proposition 2.1. This implies that the minimal critical sets
of G are pairwise disjoint. Suppose that G contains a minimal critical set which is not a
singleton. Let X those minimal critical sets of G which are not singletons.
By Lemma 4.1, each X i has size at least k. Form a new graph G   from G by adding a new
vertex x i and joining it by edges to different vertices of X i for each
We claim that G   , which is easily seen to be 1)-connected, has the properties (1)-(3)
above. Every critical set in G contains a minimal critical set and we have added a new
vertex x i for each of the original non-singleton minimal critical sets and the new x i is
itself critical in G   . Hence it follows that the minimal critical sets in G   are precisely the
original singleton critical sets plus the vertices x This proves (1) and implies that
during the first two phases of Frank's algorithm the same number of new edges are added
to G and to G   , which gives (2). Now let us consider an optimal simple k-edge-connected
augmentation F of G. Let us form a set F   of new edges from F by replacing every edge
connecting two sets X i and X j by x i x j and every edge e which enters
some
y. It is easy to see that the graph G
simple and k-edge-connected. This gives OPT k
(G).
To prove the other inequality first observe that it follows from the fact that each X i
has size at least k that if u is an edge in an optimal simple augmentation
F   of G   , then in G there is at least one vertex in X i which is non-adjacent to u. Similarly,
is an edge in F   , then we can find vertices so that uv is not
an edge in G. Now define the following set of new edges F to be added to G: let F
contain all those edges of F   which connect vertices of V . Furthermore, for each edge of
contain an edge from u to a non-neighbour of u in
for each edge of type x contain an edge uv such that uv 62 E and
We claim that G is k-edge-connected which will imply
that OPT k
(By the construction, F does not contain edges parallel to
edges of E. It is easy to see that F itself does not contain parallel edges, but to prove the
inequality it is enough to observe that deleting one copy of two parallel edges in F does
not destroy k-edge-connectivity.) Suppose not and let W be a set whose degree in G 00 is
1. Then W is critical in G as well and if W " U 6= ; for some minimal critical set U
(in none of the edges in F leave W we obtain that in G   the set
obtained by adding to W each of the vertices x i for which X i ' W has degree
a contradiction. This proves (3). \Pi.
In the next four lemmas we consider a graph G obtained by applying
the first and the second phase of Frank's algorithm starting from a simple graph E)
on at least five vertices so that G is 3-edge-connected (but not 4-edge-connected) and
The goal is to find OPT 4
S (G) and an optimal augmenting set. By Lemma 4.2, we can assume
that all the neighbours of s in G 0 have degree 3 in G (i.e. they form singleton critical sets).
that a set ; 6= X ae V is critical in
4. A set X will be called dangerous if d holds. Note that since
G is already 3-edge-connected every dangerous set X has d 0 (s; X) - 2. This fact is used
several times in the sequel.
Lemma 4.3 The following holds for every x 2 S.
(1) If dH (x) - 2, then for every non-neighbour u of x in H, the pair sx; su is legal for
splitting.
(2) There is at most one maximal dangerous set among those which contain x and at
least one other neighbour of s. In particular there is at most one non-neighbour y of
x in H for which the pair sx; sy is not legal for splitting.
(3) Either dH or sx is in at most two pairs sx; su and sx; sv which are not legal
for splitting.
Type I Type II Type III

Figure

3: The exceptional cases when d 3. For each of the three types,
every non-empty subset of L has degree at least 4.
Proof: Suppose that dH (x) - 2 and that X is a dangerous set containing x and some
E(H). Then in G the set X \Gamma x has degree at most 2 contradicting
the fact that G is 3-edge-connected. This proves (1). To prove (2) suppose that x is
contained in two maximal dangerous sets A and B. Then it follows from Proposition 2.1
that in G
5:
It is not difficult to check by a parity argument that all these equalities cannot hold at the
same time. This contradiction shows that x is contained in at most one maximal dangerous
set. Finally, observe that (3) follows easily from (1) and (2). \Pi.
Lemma 4.4 If d 0 2, then there exists a feasible complete splitting of
s, unless G 0 is of type I,II or III in Figure 3.
Proof: If then every admissible complete splitting of s will involve adding the
edges uv and uw, where and u is the vertex with two edges from s. Hence,
by Theorem 2.2 a feasible complete splitting exists if and only if dH and this is
easily seen to be the case if and only if G 0 is not of type I,II or III in Figure 3.
Thus we can assume below that 4. By Theorem 2.2, we may assume that
jE(H)j - 1. Suppose first that dH (v) - 1 for each v 2 H and let uv 2 E(H). Let w; z be
the remaining vertices in S. It follows from Lemma 4.3 (2) that at least one of the pairs
su; sw and su; sz is legal for splitting and since the remaining pair of vertices in H are not
adjacent this leads to a feasible complete splitting of s.
Now we may assume that H contains the edges uv; uw. Let z be the fourth vertex of
S. It follows from Lemma 4.3 that the pair su; sz is legal for splitting and hence, since v
and w are not adjacent, there is a feasible complete splitting of s. \Pi.
Lemma 4.5 If d 0 4, then there exists a legal splitting unless d 0
G 0 is of type II in Figure 3.
Proof: If d 0 easily from Lemma 4.3 that there exists a legal
splitting. Hence we may assume that d 0 Suppose first that It follows
from Lemma 4.3 that if there is no legal splitting, then some x 2 S has degree 3 in H.
Let u; v; w be the remaining vertices of S. Since G is 3-edge-connected and has at least
five vertices, we may assume w.l.o.g. that u and v are not adjacent. If either u or v is
adjacent to w, then su; sv is legal, by Lemma 4.3 (1). Hence we can assume that H is a
star with center x. By Lemma 4.3 (2), at least one of the pairs su; sv, or su; sw will be a
legal splitting.
first note that if x is the vertex with two edges from s, then
there is no dangerous set containing x and some other neighbour of s. Hence, it follows
that if there is no legal splitting involving x, then xy; xz 2 E(H). In this case G + s is of
type II in Figure 3. \Pi.
Lemma 4.6 If d 0 can be made 4-edge-connected preserving simplicity
by adding at most two edges.
Proof: If the two remaining neighbours u; v of s are non-adjacent then uv makes G
4-edge-connected, thus we can assume that uv 2 E. By our assumption d 0
holds. If G contains a vertex a that is not adjacent to any of u; v, then by adding the
edges ua; av we get a new graph that is simple and 4-edge-connected. If no such vertex
exists then jV must hold. Now it is easy to see that adding any
pair of edges joining u to a non-neighbour of u and v to a non-neighbour of v will make
the graph 4-edge-connected. \Pi.
Theorem 4.7 [18] For every 3-edge-connected graph G on at least five vertices the following
holds
(ii) If OPT 4
Proof: Let G be the graph returned by phase 2 of Frank's algorithm.
Note that if we are able to perform a sequence of legal splittings with the effect of adding a
set of edges F 0 to G while preserving simplicity, then it follows from Theorem 2.2 and the
fact that at the end of phase 2 of Frank's algorithm OPT 4
that the following
holds:
and
Hence, if we can show that OPT 4
will follow that OPT 4
(G)). We will use this observation several times below.
We first prove (i). By Lemma 4.2 we may assume that all minimal critical sets of G
are singletons. By Lemma 4.6 we may also assume d 0 4. Now we use Lemma 4.5
to perform legal splittings until we have d 0 in the current G 0 . If at this point we
have must hold and by Lemma 4.4 either there exists a feasible
complete splitting, or G 0 is of type I,II or III in Figure 3. It is not difficult to see that in
the latter case have OPT 4
So from this and the observation above we
get that if
(G).
Hence we may assume that now it follows from Lemma 4.5 that we can
still find one more legal splitting at this point. Then applying Lemma 4.6 we obtain
that OPT 4
are sufficient. Thus in all of the cases we get that OPT 4
This proves (i).
To prove (ii) suppose that OPT 4
and that G 6= K 3;3 (for which we clearly have
1). By Lemma 4.5 and our remark at the beginning of the
proof, it follows that it is sufficient to prove that if OPT 4
As above we let G be the graph returned by phase two of Frank's
algorithm. By Lemma 4.2 we may assume that all minimal critical sets of G are singletons
and by the remark above we can assume that d 0 6, the graph G
is 3-regular and 3-connected, thus - since we excluded K 3;3 - it is the prism (that is, the
complement of a cycle of length six), for which the desired equality trivially holds. Suppose
that there are at least 7 vertices in V . Since G is 3-edge-connected and each neighbour
of s has degree 3 in G, it follows that jE(H)j - 7 and if
must be at least 4 edges from S to
Case 1: shall argue that we can always find a legal splitting with the
property that after making this splitting at most two edges remain in the new graph H.
By Lemma 4.4 this implies that there exists a feasible complete splitting of s and hence
(G).
If has two vertices u; v of degree 3 and, by Lemma 4.3, there is
a legal splitting for the edge su (recpectively, sv) with every edge sw where w is a non-
neighbour of u (respectively, v). Hence we may assume that u and v are adjacent, because
otherwise we can eliminate six edges by performing one legal splitting. Since G is 3-edge-
connected, u and v cannot have two common neighbours x; y since then the degree of the
set would be at most two in G. If u and v have no common neighbours
then it is easy to check that there is a legal splitting (involving one of the edges su; sv)
such that at most two edges remain in H afterwards, because su (sv) can be split off with
the edge from s to each of the two neighbours of v (u). So we can assume that u and v
have precisely one neighbour x in common. Now it is easy to check, using Lemma 4.3 that
we can always find a legal splitting that eliminates at least five edges from H.
If either each of the vertices in H have degree 2 and it follows from
Lemma 4.3 (1) that the desired legal splitting exists, or there is a vertex u of degree 3 in
H. Since G is 3-edge-connected, we cannot have all 6 edges of H inside the graph induced
by u and its neighbours and hence, again, by Lemma 4.3, the desired legal splitting exists.
If has a vertex of degree 2, then it is
easy to see that we can find a legal splitting eliminating all but two edges in H.
Finally, if each vertex has degree 1 in H, then every legal splitting has
the desired property.
Case 2: follows that at the end of phase 2 of Frank's algorithm
we have two parallel edges between s and some vertex v 2 S. Let wg.
Since we started from a 3-edge-connected graph G, the vertices fx; (all of which,
by our assumption, have degree 3 in G) do not induce a K 4 . Hence it follows from Lemma
4.3 that there is a legal splitting for s which involves two vertices in the set fx;
say w.l.o.g. z; w. Now the remaining neighbours of s, fv; x; yg induce a graph with at
most 2 edges, since G 0 is 4-edge-connected and each of the vertices in S has degree 3 in G.
Now, by Lemma 4.4, either there is a feasible complete splitting of s in the actual G 0 , or
G 0 is of type I, II, or III in Figure 3 in which case we argued above in the proof of (i) that
Hence, by the remark at the beginning of the proof we
have shown that OPT 4
(G). \Pi.
It can be verified - by analyzing the algorithm of [17], say - that any simple graph G has
an optimal simple 3-edge-connected augmentation G 0 for which OPT 4
This, and the results of this section show that
We conjecture that if the starting graph is already 1)-edge-connected, the function
in Theorem 3.3 can be replaced by a linear function of k. Perhaps would do.
5 Non-uniform demands
The augmentation problem without the simplicity-preserving requirement is solvable in
polynomial time even if the target connectivity is not uniform but is given by a symmetric
on pairs of vertices of the starting graph E). (And the
goal is to find a smallest set F of new edges such that in G the local edge-connectivity
-(u; v) is at least r(u; v) for any pair (u; v) of vertices.) This more general
version was also solved by Frank in [6].
For every subset X of V let us define
g. (For simplicity, to avoid the so-called marginal
components [6], we assume that r(u; v) - 2 for each pair u; v 2 V .) By Menger's theorem
the extended graph (or the augmented graph) satisfies the requirements if and only if
holds. Like in the uniform-demand case, Frank used the same splitting-off idea in his proof.
In fact, the algorithm he gave is identical to the algorithm of the uniform case except that
after adding k parallel edges between a new vertex s and each vetex of V , during the
deletion part in phase 1 one must maintain (5:1) instead of (1:1) and during the splitting
off in phase 3 the local edge-connectivities must be preserved everywhere between pairs of
vertices in V . (For more details we refer to [6].) The corresponding phase 3 can be done
by the following theorem, which is due to Mader.
We say that two edges st and su form an admissible pair in E) if after
splitting off st and su the local edge-connectivities remain the same between vertices of V .
(Note, that splitting off never increases the local edge-connectivity.)
Theorem 5.1 [15] Let s; E) be a connected undirected graph with d(s) 6= 3 for
which there is no cut-edge incident to s. Then there is an admissible pair st; su of edges.
In this section our goal is to prove the counterparts of Theorems 3.1, 3.3 and 3.4 by
showing that in the case of the simplicity-preserving version of the non-uniform augmentation
problem there exist similar functions f 0 (k) and g 0 (k) like f(k) and g(k) in the uniform
case and the problem is solvable in polynomial time if k is fixed.
We shall use a similar approach we used for the uniform case. In fact, the crucial part of
the generalization is to prove that a similar statement (Lemma 5.4 below), corresponding
to Theorem 2.2(b) holds in this case, too. This will ensure that the number of edges which
are non-admissible with respect to some fixed edge st can be bounded by a function of
k. However, to prove this we must modify the concept of admissibility and also phase
3 of Frank's algorithm (in the non-uniform case). The reason is that although the goal
is to satisfy (5:1) only, the solution given by Frank's algorithm will guarantee more, it
will maintain the local edge-connectivities of the extended graph constructed in phase 2.
On the other hand, by this extra property of the solution it is easy to see that certain
optimal augmentations can not be obtained by Frank's algorithm. For example, let G
be the disjoint union of two stars K 1;m and let r(u; for each pair u; v of vertices.
Then the optimal solution must be a set of m independent edges between the two stars -
although any set of m independent edges on the leaves would be a good augmenting set
provided that there are at least two edges connecting the two stars.
Moreover, in the simplicity-preserving version sometimes the minimum number of new
edges to be added to satisfy the requirements after the first two phases of Frank's algorithm
- given by the local edge-connectivities in G more than the optimum value with
respect to the original demands given by the function r. For example, the first two phases
of Frank's algorithm applied to the graph on Figure 4 add the edges sx; sy; sv; sz. Then,
although there exists a proper augmenting set of size two (xy and vz), there is no legal
splitting in phase 3, since - 0 (a; must also be maintained.
a
y
z

Figure

4: r(x;
If one wants to preserve simplicity, as well, in phase 3 it is better to work with the
following less restrictive definition of admissibility.
s; E) be a graph for which (5:1) holds, where the function R is defined
by the non-uniform requirements, as before. Then we say that two edges st and su form
an R-admissible pair (or an admissible pair, if R is clear from the context) if splitting
off st and su does not violate (5:1). A set ; 6= X ae V is tight if holds. If
we say that X is dangerous. Let s(X) := R(X). It is easy to
see that st; su is an admissible pair if and only if there is no dangerous set X with t; u 2 X.
Now we list some results we shall use from [5] and [6].
Proposition 5.2 [6] For every pair X;Y ' V at least one of the following inequalities
holds:
It is easy to check that the proofs of [5, Claims 4.2, 3.2, 4.3] work the same way if we use
our definition of admissibility. Thus we can obtain three similar statements. The first one
gives that if X is a dangerous set (with respect to some edge st), then d(s; X)
To state the lemma corresponding to [5, Claim 3.2] we need one more definition. (The third
claim we get will be mentioned in the proof below.) The contraction of a subset X of
vertices in a graph E) means that we delete X and replace it by a new vertex
vX and then add dG (v; X) new parallel edges between each . The
resulting graph is denoted by G=X. After the contraction of some subset X, we define the
new requirement function r 0 in G=X as expected: r 0 (v
X. The corresponding function R 0 on the subsets of
defined by r 0 .
Lemma 5.3 Let T be a tight set. A pair st; su of edges is R-admissible in G if the
corresponding pair of edges is R 0 -admissible in G=T . \Pi.
Now we are ready to prove the lemma we need.
Lemma 5.4 Suppose that s; E) is 2-edge-connected. Then for every edge st the
number of edges su for which the pair st; su is non-admissible is at most 2k
Proof: Let S denote the set of neighbours of s and let W ae S denote those neighbours
u for which st and su form a non-admissible pair. By one of our previous remarks this
means that there exists a family F of dangerous sets, each containing t, which covers every
vertex of W . Let us fix such a family for which jF j is minimal and subject to this
is maximal. We shall prove that jF j - holds. (Note, that by [5, Claim 4.3], two
dangerous sets cannot cover the whole S.)
First we claim that every dangerous set induces a connected subgraph. To see this
assume that X is dangerous and has two components X 1 and X 2 , such that - without loss
of generality - R(X) is attained on a pair u
by 2-edge-connectivity, a
contradiction.
Let us consider a tigh set M 1 and a dangerous set M 2 , both containing t. For these two
sets (5:2b) cannot hold since otherwise by Proposition 2.1
a contradiction. (We used that by the existence of
the edge st.) Thus (5:2a) must hold by Proposition 5.2, which implies that s(M
From this it follows that if M 2 is also tight, then
are both tight (note, that M 1 [M 2 6= V ). Another consequence is that if M 2 2 F ,
then must hold, otherwise 2 - would follow by the
choice of F . These observations imply that if there exists a tight set which contains t then
there exists a unique maximal tight set M containing t. Moreover, if such a tight set M
exists, then M is a subset of every member of F and d(s; M) - holds.
By Lemma 5.3 the contraction of a tight set does not decrease the number of edges
which are non-admissible with respect to st. Thus in the rest of the proof we shall assume
that every tight set is a singleton.
We say that a pair X;Y of members of F is an a-pair if (5:2a) holds for X and Y .
Otherwise the pair is a b-pair. If X;Y 2 F is an a-pair, we get
since by the choice of F . This shows that their intersection must be
tight. Therefore must hold for each a-pair X;Y .
Suppose now that X;Y is a b-pair and Y; Z is an a-pair. We claim that then X;Z must
be a b-pair. For suppose X;Z is an a-pair. Then is disjoint from (X [ Y
Furthermore, there is precisely one edge - the edge st - from X " Y to
by the inequality
From this it follows that there is no edge between M and Z \Gamma M , hence Z is not connected,
contradicting the fact that every dangerous set induces a connected graph.
Hence F can be partitioned into subfamilies F 1 ; :::; F r such that X;Y is a b-pair if and
only if X and Y are in different subfamilies. Suppose that one of these subfamilies F i has
size at least k. Since each member in this subfamily is connected and (X \GammaM )"(Y \GammaM
for different members X;Y 2 F i , M has at least k different neighbours in V . Since M is
connected to s, as well, k - contradiction. Thus each
subfamily in the partition has size at most k \Gamma 1. This implies that if jF
there must be three sets X;Y;Z 2 F such that they are pairwise b-pairs. Since for a b-pair
X;Y the sets are both tight, and hence singletons, the minimality of
F , implies that there exists a set N such that holds. Using
(5:2b) this gives that the only edge that leaves N in G is st, a contradiction.
Hence we obtain jF 2. Since d(s; for each X 2 F and d(s; t) - k, the
number of edges which are non-admissible with respect to st is at most k(2k \Gamma
From Lemma 5.4, following the proof ideas of Theorems 3.1, 3.3 and 3.4 one can obtain
the corresponding results for the non-uniform version, that is, the existence of the functions
below. The details, which are similar, are omitted, but some remarks must
be added. First of all, we modify Frank's non-uniform algorithm in such a way that - except
the last part, where only a small number of edges are present - in phase 3 we split off edges
which form admissible pairs in the sense we defined. This is necessary, since otherwise
Lemma 5.4 is not valid (see the example of two stars at the beginning of this section).
Furthermore, the points where we need more involved arguments are the extension of Claim
3.5 and the existence of simple graphs with maximum degree
satisfying the non-uniform demands. (In the latter case a result from [8] can be referred
to.) Also note that our assumption r - 2 implies that the 2-edge-connectivity condition
in Lemma 5.4 is fulfilled.
Theorem 5.5 Let be a graph at the end of the second phase of Frank's
(non-uniform) algorithm such that
holds. Then there exists a feasible complete splitting from s, where feasibility is meant with
respect to (5:1). \Pi.
Theorem 5.6 If OPT k
holds. \Pi.
Theorem 5.7 OPT k
any starting graph G and non-uniform
demands with v)g. \Pi.
So far we have no proof for a counterpart of Theorem 3.6. This would improve the
efficiency of the algorithm like Theorem 3.6 did in the uniform case.
6 Remarks
In this last section some remarks are made related to possible extensions of the simplicity-
preserving edge-connectivity augmentation problem.
The "subset-problem", where the goal is to find a simplicity-preserving augmentation
which makes a subset X ae V k-edge-connected was mentioned as the next open problem
to be studied (at least for [18]. Observe, that this is a special case of the non-uniform
demand version. (On the other hand, the subset-problem can be solved by just
slightly modifying our proofs of the uniform case, as well.)
For the directed version of our problem a similar function f(k) - like in Theorem 3.1 -
does not exist. In [12] a family G k
i of digraphs was shown for any k with i - OPT k
Our arguments do not apply for the vertex-cost version of the simplicity-preserving
augmentation problem. (Without the simplicity requirement it can be solved by Frank's
algorithm, see [6].) This is the consequence of the small modification we made in phase
2 of the algorithm. (Consider a star K 1;m , where m is odd, 2, and the weights are
uniformly 2 except the center v of the star, whose weight is 1.)
Some of the above results are valid in the more general case when the starting graph G
is not simple, but the augmenting set F must not contain parallel edges and edges which
are parallel to edges of G. These details are omitted.
Finally we remark that the version where the augmenting set F must not contain
parallel edges, but a new edge may be parallel to an edge of the starting graph, remains
open.



--R


Parallel and fast sequential algorithms for undirected edge augmentation
Successive edge-connectivity augmentation problems
Computing 5
On a theorem of Mader
Augmenting Graphs to Meet Edge-Connectivity Requirements
Connectivity augmentation problems in network design
Connectivity considerations in the design of survivable net- works
Applications of a poset representation for edge-connectivity and graph rigidity
Optimal augmentation for bipartite componentwise biconnectivity in linear time

Augmenting directed graphs preserving simplicity
Planar graph augmentation problems

A Reduction Method for Edge-Connectivity in Graphs

A Fast Algorithm for Optimally Increasing the Edge-Connectivity
Simplicity preserving augmentation of the edge-connectivity of a graph
A linear time algorithm for smallest augmentation to 3-edge-connect a graph
Journal of Computer and System Sciences 35
--TR

--CTR
Hiroshi Nagamochi , Toshihide Ibaraki, Graph connectivity and its augmentation: applications of MA orderings, Discrete Applied Mathematics, v.123 n.1-3, p.447-472, 15 November 2002
edge-connectivity augmentation of graphs;network design;combinatorial optimization;connectivity