Linear-time approximation schemes for planar minimum three-edge
connected and three-vertex connected spanning subgraphs

arXiv:1701.08315v1 [] 28 Jan 2017

Baigong Zheng
Oregon State University
zhengb@eecs.oregonstate.edu

Abstract
We present the first polynomial-time approximation schemes, i.e., (1 + )-approximation
algorithm for any constant  > 0, for the minimum three-edge connected spanning subgraph
problem and the minimum three-vertex connected spanning subgraph problem in undirected
planar graphs. Both the approximation schemes run in linear time.

This material is based upon work supported by the National Science Foundation under Grant No. CCF1252833.

1

Introduction

Given an undirected unweighted graph G, the minimum k-edge connected spanning subgraph problem (k-ECSS) asks for a spanning subgraph of G that is k-edge connected (remains connected
after removing any k − 1 edges) and has a minimum number of edges. The minimum k-vertex
connected spanning subgraph problem (k-VCSS) asks for a k-vertex connected (remains connected
after removing any k − 1 vertices) spanning subgraph of G with minimum number of edges. These
are fundamental problems in network design and have been well studied. When k = 1, the solution is simply a spanning tree for both problems. For k ≥ 2, the two problems both become
NP-hard [7, 12], so people put much effort into achieving polynomial-time approximation algorithms. Cheriyan and Thurimella [7] give algorithms with approximation ratios of 1 + 1/k for
k-VCSS and 1 + 2/(k + 1) for k-ECSS for simple graphs. Gabow and Gallagher [11] improve the
approximation ratio for k-ECSS to 1 + 1/(2k) + O(1/k 2 ) for simple graphs when k ≥ 7, and they
give a (1 + 21/(11k))-approximation algorithm for k-ECSS in multigraphs. Some researchers have
studied these two problems for the small connectivities k, especially k = 2 and k = 3, and obtained
better approximations. The best approximation ratio for 2-ECSS in general graphs is 5/4 of Jothi,
Raghavachari, and Varadarajan [17], while for 2-VCSS in general graphs, the best ratio is 9/7 of
Gubbala and Raghavachari [14]. Gubbala and Raghavachari [15] also give a 4/3-approximation
algorithm for 3-ECSS in general graphs.
A polynomial-time approximation scheme (PTAS) is an algorithm that, given an instance and
a positive number , finds a (1 + )-approximation for the problem and runs in polynomial time
for fixed . Neither k-ECSS nor k-VCSS have a PTAS even in graphs of bounded degree for k = 2
unless P = NP [10]. However, this hardness of approximation does not hold for special classes
of graphs and small values of k. For example, Czumaj et al. [8] show that there are PTASes for
both of 2-ECSS and 2-VCSS in planar graphs. Both problems are NP-hard in planar graphs (by
a reduction from Hamiltonian cycle). Later, Berger and Grigni improved the PTAS for 2-ECSS to
run in linear time [3].
Following their PTASes for 2-ECSS and 2-VCSS, Czumaj et al. [8] ask the following: can we
extend the PTAS for 2-ECSS to a PTAS for 3-ECSS in planar graphs? A PTAS for 3-VCSS in planar
graphs is additionally listed as an open problem in the Handbook of Approximation Algorithms and
Metaheuristics (Section 51.8.1) [13]. In this paper we answer these questions affirmatively by giving
the first PTASes for both 3-ECSS and 3-VCSS in planar graphs. Our main results are the following
theorems.
Theorem 1. For 3-ECSS, there is an algorithm that, for any  > 0 and any undirected planar
graph G, finds a (1 + )-approximate solution in linear time.
Theorem 2. For 3-VCSS, there is an algorithm that, for any  > 0 and any undirected planar
graph G, finds a (1 + )-approximate solution in linear time.
In the following, we assume there are no self-loops in the input graph for both of 3-ECSS and
3-VCSS. For 3-ECSS, we allow parallel edges in G, but at most 3 parallel edges between any pair
of vertices are useful in a minimal solution. For 3-VCSS, parallel edges are unnecessary, so we
assume the input graph is simple. Since three-vertex connectivity (triconnectivity) and three-edge
connectivity can be verified in linear time [21, 24], we assume the input graph G contains a feasible
solution. W.l.o.g. we also assume  < 1.

1

1.1

The approach

Our PTASes follow the general framework for planar PTASes that grew out of the PTAS for
TSP [18], and has been applied to obtain PTASes for other problems in planar graphs, including
minimum-weight 2-edge-connected subgraph [3], Steiner tree [4, 6], Steiner forest [2] and relaxed
minimum-weight subset two-edge connected subgraph [5]. The framework consists of the following
four steps.
Spanner Step. Find a subgraph G0 that contains a (1 + )-approximation and whose total weight
is bounded by a constant times of the weight of an optimal solution. Such a graph is usually
called a spanner since it often approximates the distance between vertices.
Slicing Step. Find a set of subgraphs, called slices, in G0 such that any two of them are face
disjoint and share only a set of edges with small weight and each of the subgraphs has
bounded branchwidth.
Dynamic-Programming Step. Find the optimal solution in each slice using dynamic programming. Since the branchwidth of each subgraph is bounded, the dynamic programming runs
in polynomial time.
Combining Step. Combine the solutions of all subgraphs obtained by dynamic programming and
some shared edges from Slicing step to give the final approximate solution.
For most applications of the PTAS framework, the challenging step is to illustrate the existence
of a spanner subgraph. However, for 3-ECSS and 3-VCSS, we could simply obtain a spanner from
the input graph G by deleting additional parallel edges since by planarity there are at most O(n)
edges in G and the size of an optimal solution is at least n, where n = |V (G)|. So, different
from those previous applications, the real challenge for our problems is to illustrate the slicing step
and the combining step. For the slicing step, we want to identify a set of slices that have two
properties: (1) three-edge-connectivity for 3-ECSS or triconnectivity for 3-VCSS, and (2) bounded
branchwidth. With these two properties, we can solve 3-ECSS or 3-VCSS on each slice efficiently.
For the combining step, we need to show that we can obtain a nearly optimal solution from the
optimal solutions of all slices found in slicing step and the shared edges of slices, that means the
solution should satisfy the connectivity requirement and its size is at most 1 +  times of the size
of an optimal solution for the original input graph.
To identify slices, we generalize a decomposition used by Baker [1]. Before sketching our method,
we briefly mention the difficulty in applying previous techniques. The PTAS for TSP [18] identifies
slices in a spanner G0 by doing a breadth-first search in its planar dual to decompose the edge set
into some levels, and any two adjacent slices could only share all edges of the same level, which form
a set of edge-disjoint simple cycles. This is enough to achieve simple connectivity or biconnectivity
between vertices of different slices. But our problems need stronger connectivity for which one cycle
is not enough. For example, we may need a non-trivial subgraph outside of slice H to maintain the
triconnectivity between two vertices in slice H. See Figure 1 (a).
For 3-ECSS, we construct a graph called 3EC slice. We contract each component of the spanner
that is not in the current 3EC slice. Since contraction can only increase edge-connectivity, this will
give us the 3EC slices that are three-edge connected (Lemma 14 in Section 3). However, if we
directly apply this contraction method in the slicing step of the PTAS for TSP, the branchwidth
of the 3EC slice may not be bounded. This is because there may be many edges that are not in
2

Figure 1: (a) The bold cycle encloses a slice H. To maintain the triconnectivity between two
vertices u and v in H, we need the dashed path outside of H. (b) The bold cycle encloses a 3EC
slice H. The dashed edges divide the outer face of H into distinct regions, which may contain
contracted nodes. (c) The bold cycle encloses a 3EC slice H. The dashed path P between w1 and
w2 will be contracted to obtain a node x. A solution for 3-ECSS on H may contain x but not
the dashed edge between u and v. Then the union S of feasible solutions on all 3EC slices is not
feasible if it does not contain path P .
the slice but have both endpoints in the slice, and such edges may divide the faces of the slice into
distinct regions, each of which may contain a contracted node. See Figure 1 (b). To avoid this
problem, we apply the contractions in the decomposition used by Baker [1], which define a slice
based on the levels of vertices instead of edges. We can prove that each 3EC slice has bounded
branchwidth in this decomposition (Lemma 12 in Section 2).
Although each 3EC slice is three-edge connected, the union S of their feasible solutions may not
be three-edge connected. Consider the following situation. In a solution for a slice, a contracted
node x is contained in all vertex-cuts for a pair of vertices u and v. But in S, the subgraph induced
by the vertex set X corresponding to x may not be connected. Therefore, u and v may not satisfy
the connectivity requirement in S. See Figure 1 (c).
In their paper, Czumaj et al. [8] proposed a structure called bicycle. A bicycle consists of two
nested cycles, and all in-between faces visible from one of the two cycles. This can be used to
maintain the three-edge-connectivity between those connecting endpoints in cycles. This motivates
our idea: we want to combine this structure with Baker’s shifting technique so that two adjacent
slices shared a subgraph similar to a bicycle. In this way, we could maintain the strong connectivity
between adjacent slices by including all edges in this shared subgraph, whose size could be bounded
by the shifting technique. Specifically, we define a structure called double layer for each level i based
on our decomposition, which intuitively contains all the edges incident to vertices of level i and
all edges between vertices of level i + 1. Then we define a 3EC slice based on a maximal circuit
such that any pair of 3EC slices can only share edges in the double layer between them. In this
way, we can obtain a feasible solution for 3-ECSS by combining the optimal solutions for all the
slices and all the shared double layers (Lemma 16 in Section 3). By applying shifting technique on
double layers, we can prove that the total size of the shared double layers is a small fraction of the
size of an optimal solution. So we could add those shared double layers into our solution without
increasing its size by much, and this gives us a nearly optimal solution.
For 3-VCSS, we construct a 3VC slice based on a simple cycle instead of a circuit. The construction is similar to that of 3EC slices. However, contraction does not maintain vertex connectivity.
3

Figure 2: The three horizontal lines in the right figure show the three levels in the left figure. In
this example, V0 = {a, b, c, d, e}, V1 = {f, g, h, i, j} and V2 = {k, l, m, n}.
So we need to prove each 3VC slice is triconnected (Lemma 20 in Section 4). Then similar to
3-ECSS, we also need to prove that the union of the optimal solutions of all 3VC slices and all
shared double layers form a feasible solution (Lemma 22 in Section 4).
For dynamic-programming step, we need to solve a minimum-weight 3-ECSS problem in each
3EC slice and a minimum-weight 3-VCSS problem in each 3VC slice. This is because we need to
carefully assign weights to edges in a slice so that we can bound the size of our solution. We provide
a dynamic program for the minimum-weight 3-ECSS problem in graphs of bounded branchwidth in
Section 5, which is similar to that in the works of Czumaj and Lingas [9, 10]. A dynamic program
for minimum-weight 3-VCSS can be obtained in a similar way. Then we have the following theorem.
Theorem 3. Minimum-weight 3-ECSS problem and minimum-weight 3-VCSS problem both can be
solved on a graph G of bounded branchwidth in O(|E(G)|) time.

2

Preliminaries

Let G be an undirected planar graph with vertex set V (G) and edge set E(G). We denote by G[S]
the subgraph of G induced by S where S is a vertex subset or an edge subset. We simplify |E(G)|
to |G|. We assume we are given an embedding of G in the plane. We denote by ∂(G) the subgraph
induced by the edges on the outer boundary of G in this embedding. A circuit is a closed walk that
may contain repeated vertices but not repeated edges. A simple cycle is a circuit that contains no
repetition of vertices, other than the repetition of the starting and ending vertex. A simple cycle
bounds a finite region in the plane that is a topological disk. We say a simple cycle encloses a
vertex, an edge or a subgraph if the vertex, edge or subgraph is embedded in the topological disk
bounded by the cycle. We say a circuit encloses a vertex, edge or subgraph if the vertex, edge or
subgraph is enclosed by a simple cycle in the circuit.
The level of a vertex of G is defined as follows [1]: a vertex has level 0 if it is on the infinite face
of G; a vertex has level i if it is on the infinite face after deleting all the vertices of levels less than
i. Let Vi be the set of vertices of level i. Let Ei be the edge set of G in which each edge has both
endpoints in level i. Let Ei,i+1 be the edge set of G where each edge has one endpoint in level i and
one endpoint in level i + 1. See Figure 2 as an example. Then we have the following observations.
Observation 1. For any level i ≥ 0, the boundary of any non-trivial two-edge connected component
in G[∪j≥i Vj ] is a maximal circuit in ∂(G[Vi ]).
4

Figure 3: The horizontal lines represent edge set in the same level and slashes and counter slashes
represent the edge set between two adjacent levels. Left: there are three double layers: Di , Di+1
and Di+2 represented by the shaded regions. Right: Gi contains all edges in this figure, but Hi ,
represented by shaded region, does not contain Ef (i)−1 .
Observation 2. For any level i ≥ 0, the boundary of any non-trivial biconnected component in
G[∪j≥i Vj ] is a simple cycle in ∂(G[Vi ]).
For any i ≥ 0, we define the ith double layer
Di = Ei−1,i ∪ Ei ∪ Ei,i+1 ∪ Ei+1
as the set of edges in G[Vi−1 ∪ Vi ∪ Vi+1 ] \ Ei−1 . See Figure 3
Let k be a constant that depends on . For j = 0, 1, . . . , k − 1, let Rj = ∪i mod k=j Di . Let
P
t = argminj |Rj | and R = Rt . Since k−1
j=0 |Rj | ≤ 2|G|, we have the following upper bound for the
size of R.
|R| ≤ 2/k · |G|

(1)

Let f (i) = ik − k + t for integer i ≥ 0. If ik − k + t < 0 for any i, we let f (i) = 0. Let
Gi = G[∪f (i)−1≤j≤f (i+1)+1 Vj ] be the subgraph of G induced by vertices in level [f (i)−1, f (i+1)+1]
and Hi = Gi \Ef (i)−1 be a subgraph of Gi . See Figure 3. Note that Hi contains exactly the edges of
double layers Df (i) through Df (i+1) . Therefore, so long as k ≥ 2, we have Hi ∩ Hi+1 = Df (i+1) ⊆ R,
and Hi ∩ Hj = ∅ for any j 6= i and |i − j| ≥ 2. So for any j 6= i we have
(Hi \ R) ∩ (Hj \ R) = ∅.

(2)

For each i ≥ 0 and each maximal circuit Ca in ∂(G[Vf (i) ]), we construct a graph Hia , called a 3EC
slice, from G as follows. (See Figure 4.) Let U be the subset of vertices of Hi \ (Vf (i)−1 ∪ Vf (i+1)+1 )
that are enclosed by Ca . We contract each connected component of G \ U into a node. After all the
contractions, we delete self-loops and additional parallel edges if there are more than three parallel
edges between any pair of vertices. The resulting graph is the 3EC slice Hia . We call these contracted
vertices nodes to distinguish them from the original vertices of G. We call a contracted node inner
if it is obtained by contracting a component that is enclosed by Ca ; otherwise it is outer. Note that
5

Figure 4: Example for the construction of Hia . Left: a component of Gi . The bold cycles represent
maximal circuits in ∂(G[Vf (i) ]). Right: an example of Hia . The nodes represent the contracted
nodes. The cycles inside of Ca must belong to Ef (i+1) .
a 3EC slice is still planar, and two 3EC slices only share edges in a double layer: the common edges
b
of two 3EC slices Hia and Hi+1
must be in the set Ef (i+1)−1,f (i+1) ∪ Ef (i+1) ∪ Ef (i+1),f (i+1)+1 , while
a
the common edges of Hi and Hic must be in the set Ef (i) . In the similar way, we can construct a
simple graph Hia , called 3VC slice, for each i ≥ 0 and each simple cycle Ca in ∂(G[Vf (i) ]).
Remark There can be a 3EC slice Hia containing only two vertices in Vf (i) . Then the slice must
contain at least two parallel edges between the two vertices in Vf (i) . But any 3EC slice Hia cannot
contain only one vertex in Vf (i) since we define 3EC slice based on a maximal circuit and we assume
there is no self-loop in G. Similarly, any 3VC slice Hia contains at least three vertices in Vf (i) .
Lemma 4. If G is two-edge connected (biconnected), then each 3EC (3VC) slice obtained from G
has at most one outer node.
Proof. We first prove the following claims, and then by these claims we prove the lemma.
Claim 5. For any l ≥ 0, subgraph G[∪0≤j≤l Vj ] is connected.
Proof. We prove by induction on l that subgraph G[∪0≤j≤l Vj ] is connected for any l ≥ 0. The
base case is l = 0. Since V0 is the set of vertices on the boundary of G, and since G is connected,
subgraph G[V0 ] is connected. Assume subgraph G[∪0≤j≤l Vj ] is connected for l ≥ 0. Then we claim
subgraph G[∪0≤j≤l+1 Vj ] is connected. This is because for each connected component X of G[Vl+1 ],
there exists at least one edge between X and G[Vl ], otherwise graph G cannot be connected. Since
subgraph G[∪0≤j≤l Vj ] is connected, we have G[∪0≤j≤l+1 Vj ] is connected.
Claim 6. If G is two-edge connected, then for any two distinct maximal circuits Ca and Cb in
∂(G[Vl ]), there is a path between Cb and G[Vl−1 ] that is vertex disjoint from Ca .
Proof. Note that Ca and Cb are vertex-disjoint, otherwise Ca is not maximal. We argue that there
cannot be two edge-disjoint paths between Ca and Cb in G[Vl ]. If there are such two edge-disjoint
paths, say P1 and P2 , then Ca cannot be a maximal circuit in ∂(G[Vl ]): if P1 and P2 have the
same endpoint in Ca , then Ca is not maximal; otherwise there is some edge of Ca that cannot be
6

in ∂(G[Vl ]). So we know that any vertex in Ca and any vertex in Cb cannot be two-edge connected
in G[Vl ]. Since G is two-edge connected and since G[Vl−1 ] must be outside of Ca and Cb , vertices
in Ca and those in Cb must be connected through G[Vl−1 ]. Therefore, there exists a path from Cb
to G[Vl−1 ] that does not contain any vertex in Ca .
Similarly, we can obtain the following claim.
Claim 7. If G is biconnected, then for any two distinct simple cycles Ca and Cb in ∂(G[Vl ]), there
is a path between Cb and G[Vl−1 ] that is vertex disjoint from Ca .
Now we prove the lemma. Let H be a 3EC slice based on some maximal circuit Ca in ∂(G[Vl ])
for some l ≥ 0. Let W = ∪0≤j<l Vj be the set of all vertices of G that have levels less than l, and
Q be a two-edge connected component in G[Vl ] disjoint from H. Then the boundary of Q is a
maximal circuit C in ∂(G[Vl ]). Note that Q could be trivial and then C is also trivial. Since G is
connected, each simple cycle must enclose a connected subgraph of G. So circuit C must enclose
a connected subgraph of G. By Claim 6, there is a path between C and G[Vl−1 ] disjoint from Ca .
Since G[∪0≤j<l Vj ] is connected by Claim 5, the set of vertices that are not enclosed by Ca induces
a connected subgraph of G, giving the lemma for H. For 3VC slice, we can obtain the lemma in
the same way by Claim 5 and Claim 7.
Using this lemma, we show how to construct all the 3EC slices in linear time. First we compute the levels of all vertices in linear time by using an appropriate representation of the planar
embedding such as that used by Lipton and Tarjan [20]. We construct all 3EC slices Hia from Gi
in O(|V (Gi )|) time. We first contract all the edges between vertices of level f (i + 1) + 1. Next,
we identify all two-edge connected components in G[Vf (i) ], which can be done in linear time by
finding all the edge cuts by the result of Tarjan [26]. Each such component contains a maximal
circuit in ∂(G[Vf (i) ]). Based on these two-edge connected components of G[Vf (i) ], we could identify
V (Hia ) \ {ria } for all 3EC slices Hia in O(|V (Gi )|) time, where ria is the outer contracted node for
Hia . This is because the inner contracted nodes of a 3EC slice Hia is the same as those contracted in
Gi if they are enclosed by Ca . Then for each 3EC slice Hia we add the outer node ria , and for each
vertex u ∈ V (Ca ) we add an edge between ria and u if there is an edge between u and some vertex
v that is not enclosed by Ca . To add those edges, we only need to travel
Pall the edges of subgraph
Gi [Vf (i)−1 ∪Vf (i) ]. Since all these steps run in O(|V (Gi )| time, and since i≥0 |V (Gi )| = O(|V (G)|),
we can obtain the following lemma.
Lemma 8. All 3EC slices can be constructed in O(|V (G)|) time.
Since we can compute all the biconnected components in G[Vf (i) ] in linear time based on depthfirst search by the result of Hopcroft and Tarjan [16], we can obtain a similar lemma for 3VC sllices
in a similar way.
Lemma 9. All 3VC slices can be constructed in O(|V (G)|) time.
We review the definition of branchwidth given by Seymour and Thomas [25]. A branch decomposition of a graph G is a hierarchical clustering of its edge set. We represent this hierarchy by a
binary tree, called the decomposition tree, where the leaves are in bijection with the edges of the
original graph. If we delete an edge α of this decomposition tree, the edge set of the original graph
is partitioned into two parts Eα and E(G) \ Eα according to the leaves of the two subtrees. The
set of vertices in common between the two subgraphs induced by Eα and E(G) \ Eα is called the
7

separator corresponding to α in the decomposition. The width of the decomposition is the maximum size of the separator in that decomposition, and the branchwidth of G is the minimum width
of any branch decomposition of G. We borrow the following lemmas from Klein and Mozes [19],
which are helpful in bounding the branchwidth of our graphs.
Lemma 10. (Lemma 14.5.1 [19]) Deleting or contracting edges does not increase the branchwidth
of a graph.
Lemma 11. (Lemma 14.6.1 [19] rewritten) There is a linear-time algorithm that, given a planar
embedded graph G, returns a branch-decomposition whose width is at most twice of the depth of a
rooted spanning tree of G.
Lemma 12. If G is two-edge connected (biconnected), the branchwidth of any 3EC (3VC) slice is
O(k).
Proof. We prove this lemma for 3EC slices when G is two-edge connected; by the same proof we
can obtain the lemma for 3VC slices when G is biconnected. Let Hia be a 3EC slice. By Lemma 4,
there is at most one outer contracted node r for Hia . Let the level of r be f (i) − 1, and the level of
all inner contracted nodes be f (i + 1) + 1. Now we add edges to ensure that every vertex of level
l has a neighbor of level l − 1 for each f (i) ≤ l ≤ f (i) + 1, while maintaining planarity. Call the
resulting graph Kia . Then the branchwidth of Hia is no more than that of Kia by Lemma 10. Now
we can find a breadth-first-tree of Kia rooted at r that has depth at most k + 3. By Lemma 11, the
branchwidth of Kia is O(k) and that of Hia is at most O(k).

3

PTAS for 3-ECSS

In this section, we prove Theorem 1. W.l.o.g. we assume G has at most three parallel edges between
any pair of vertices. Then G is our spanner. Let OPT(G) be an optimal solution for G. Since each
vertex in OPT(G) has degree at least three, we have
2|OPT(G)| ≥ 3|V (G)|.

(3)

If G is simple, then by planarity the number of edges is at most three times of the number of
vertices. Since there are at most three parallel edges between any pair of vertices, we have
|G| ≤ 9|V (G)|.

(4)

Combining (3) and (4), we have |G| ≤ 6|OPT(G)|.
In this section, we only consider 3EC slices. So when we say slice, we mean 3EC slice in this
section. We construct all the slices from G. By (1), we have the following
|R| ≤ 2/k · |G| ≤ 12/k · |OPT(G)|.

(5)

We borrow the following lemma from Nagamochi and Ibaraki [22].
Lemma 13. (Lemma 4.1 (2) [22] rewritten) Let G be a k-edge connected graph with more than 2
vertices. Then after contracting any edge in G, the resulting graph is still k-edge connected.
Recall that our slices are obtained from G by contractions and deletions of self-loops. By the
above lemma, we have the following lemma.
8

Figure 5: The bold cycle encloses Yia . The dashed edge is in G but not in OPT(G). Its two
endpoints will be identified, since the dashed edge will be contracted to obtain Hia but it will not
be contracted when contracting connected components of OPT(G) \ Yia .
Lemma 14. If G is three-edge connected, then any slice is three-edge connected.
Since we can include all the edges in shared double layers, they are “free” to us. So we would
like to include those edges as many as possible in the solution for each slice. This can be achieved
by defining an edge-weight function w for each slice Hia : assign weight 0 to edges in Df (i) ∪ Df (i+1)
and weight 1 to other edges. By Lemma 14, any slice is three-edge connected. We solve the
minimum-weight 3-ECSS problem on Hia in linear time by Theorem 3. Let Sol(Hia ) be a feasible
solution for the minimum-weight 3-ECSS problem on Hia . Then it is also a feasible solution for
3-ECSS on Hia . Let OPTw (Hia ) be an optimal solution for the minimum-weight 3-ECSS problem
on Hia . Then we have the following observation.
Observation 3. The weight of any solution Sol(Hia ) is the same as the number of its common
edges with Hia \ R, that is
w(Sol(Hia )) = |Sol(Hia ) ∩ (Hia \ R)|.
Let Ci be the set of all maximal circuits in ∂(G[Vf (i) ]). Then we have the following lemmas.
S
Lemma 15. For any i ≥ 0, let Si = Ca ∈Ci OPTw (Hia ). Then we can bound the number of edges
in Si by the following inequality
|Si | ≤ |OPT(G) ∩ (Hi \ R)| + |Df (i) | + |Df (i+1) |.
Proof. We show that OPT(G) ∩ Hia is a feasible solution for the minimum-weight 3-ECSS problem
on Hia , and then we bound the size of Si . Let Yia be the set of vertices of Hia that are not
contracted nodes. We first contract connected components of OPT(G) \ Yia just as constructing
Hia from G. Then we need to identify any two contracted nodes, if their corresponding components
in OPT(G) are in the same connected component in G \ Yia . See Figure 5. Finally, we delete all
the self-loops and extra parallel edges if there are more than three parallel edges between any two
vertices. The resulting graph is a subgraph of OPT(G) ∩ Hia and spans V (Hia ). Since identifying
two nodes maintains edge-connectivity, and since contractions also maintain edge-connectivity by
Lemma 13, the resulting graph is three-edge connected. So OPT(G) ∩ Hia is a feasible solution
for minimum-weighted 3-ECSS problem on Hia . Then by the optimality of OPTw (Hia ), we have
w(OPTw (Hia )) ≤ w(OPT(G) ∩ Hia ). And by Observation 3, we have
|OPTw (Hia ) ∩ (Hia \ R)| ≤ |(OPT(G) ∩ Hia ) ∩ (Hia \ R)| = |OPT(G) ∩ (Hia \ R)|.
9

(6)

Figure 6: (a) A slice Hia : the bold cycle is a maximal circuit Ca in Ci and the nodes represent all
the contracted nodes. (b) The graph Mia obtained from Hia by uncontracting inner nodes of Hia .
(c) The subtree T (Hia ).
Note that for any slice Hia , we have E(Hia ) ⊆ E(Hi ) and (Hia ∩R) ⊆ (Hi ∩R) ⊆ (Df (i) ∪Df (i+1) ).
Since for distinct (vertex-disjoint) maximal circuits Ca and Cb in Ci , subgraphs Hia \ R and Hib \ R
are vertex-disjoint, we have the following equalities.
[
Hi \ R =
(Hia \ R)
(7)
Ca ∈Ci

Si ∩ (Hi \ R) =
Then

[
Ca ∈Ci

(OPTw (Hia ) ∩ (Hia \ R))

S
|Si ∩ (Hi \ R)| = Ca ∈Ci (OPTw (Hia ) ∩ (Hia \ R))
P
≤ Ca ∈Ci |OPTw (Hia ) ∩ (Hia \ R)|
P
≤ Ca ∈Ci |OPT(G) ∩ (Hia \ R)|
≤ |OPT(G) ∩ (Hi \ R)|.

(8)

by (8)
by (6)
by (7)

So we have |Si | = |Si ∩ (Hi \ R)| + |Si ∩ (Hi ∩ R)| ≤ |OPT(G) ∩ (Hi \ R)| + |Df (i) | + |Df (i+1) |.
S

a
Lemma 16. The union
i≥0,Ca ∈Ci Sol(Hi ) ∪ R is a feasible solution for G.
Proof. For any i ≥ 0 and any maximal circuit Ca ∈ Ci , let Mia be the graph obtained from Hia by
uncontracting all its inner contracted nodes. See Figure 6. By Lemma 4, there is at most one outer
node ria for each slice Hia .
Define a tree T based on all the slices: each slice is a node of T , and two nodes Hia and Hjb
are adjacent if they share any edge and |i − j| = 1. Root T at the slice H0a , which contains the
boundary of G. Let T (Hia ) be the subtree of T that roots at slice Hia . See Figure 6 as an example.
b
b \ {r b }. Then C is the maximal circuit
For each child Hi+1
of Hia , let Cb be the boundary of Hi+1
b
i+1
a
b
b \ {r b } is
in Ci+1 that is shared by Hi and Hi+1 . Further, by the construction of Hia , graph Mi+1
i+1
a subgraph of Mia .
b
We prove the lemma by induction on this tree T from leaves to root. Assume
S for each child Hi+1
b
of Hia , there is a feasible solution S b for the graph Mi+1
such that S b =
∪
b ) Sol(H)
H∈T (Hi+1

S

b ∩
Mi+1
. We prove that there is a feasible solution S a for Mia such that
j≥i+1 Df (j+1)
10

Figure 7: The dashed subgraph is the boundary of G[X]. All the vertices in the dashed subgraph
are in level f (i + 1) + 1, and all its edges are in Ef (i+1)+1 .
Sa =
S

S

H∈T (Hia )

 
S

Sol(H) ∪ Mia ∩
D
.
j≥i f (j+1)

For the root H0a of T , we have M0a ∩



⊆ R, and then the lemma follows from the case i = 0.
The base case is that Hia is a leaf of T . When Hia is a leaf, there is no inner contracted node in
a
Hi and we have Mia = Hia . So Sol(Hia ) is a feasible solution for Mia .
b
Recall that Hia and Hi+1
only share edges of (Ef (i+1)−1,f (i+1) ∪ Ef (i+1) ∪ Ef (i+1),f (i+1)+1 ) ⊆
Df (i+1) and vertices of Vf (i+1) . Let x be any inner contracted node of Hia and X be the vertex set
of the connected component of G corresponding to x. We need the following claim.
j≥0 Df (j+1)

b
b , then (S b ∪ D
Claim 17. If X ⊆ Mi+1
for some Hi+1
f (i+1) ) ∩ G[X] is connected.

Proof. By the construction of levels, all the vertices on the boundary of G[X] have level f (i +
1) + 1. See Figure 7. Then all the edges of ∂(G[X]) are in Ef (i+1)+1 ⊆ Df (i+1) . So subgraph
b
(S b ∪ Df (i+1) ) ∩ ∂(G[X]) is connected. Let u be any vertex in X and let v be any vertex in Mi+1
b , there exists
that has level f (i + 1). Then v is not in X. Since S b is a feasible solution for Mi+1
b
a path from u to v in S . This path must intersect ∂(G[X]) by planarity. So u and any vertex on
the boundary of G[X] are connected in (S b ∪ Df (i+1) ) ∩ G[X], giving the claim.
Let u and v be any two vertices of Mia. To prove the feasibility of S a , we prove
 u and v
S
a
b
b
a
are three-edge connected in S . Let M =
b
Hi+1
is a child of Hia V (Mi+1 \ {ri+1 }) and Yi =
V (Hia ) \ {inner contracted nodes of Hia }. Then V (Mia ) = Yia ∪ M . Depending on the locations of
u and v, we have three cases.
Case 1: u, v ∈ Yia . Note that we could construct S a in the following way. Initially we have S ∗ =
Sol(Hia ) ∪ (Df (i+1) ∩ Hia ). For any inner contracted node x of Hia , let X be the vertex set
b
of its corresponding connected component in G. Then there exists a child Hi+1
of Hia such
b
∗
b
that X ⊆ V (Mi+1 ), and we replace x with (S ∪ Df (i+1) ) ∩ G[X] in S . We do this for all
inner contracted nodes of Hia . Finally we add some edges of Df (i+1) into the resulting graph
such that Df (i+1) ⊆ S ∗ . Then the resulting S ∗ is the same as S a by the definition of S a . We
prove that any pair of the remaining vertices in V (Hia ) are three-edge connected during the
construction. This includes the remaining inner contracted nodes of Hia during the process,
but after all the replacements, there is no such inner contracted nodes, proving the case.

11

By the definition of Sol(Hia ), any pair of vertices of Hia are three-edge connected in Sol(Hia ).
Assume after the first k replacements, any pair of the remaining vertices in V (Hia ) are threeedge connected in the resulting graph S ∗ . Let x be the next inner contracted node to be
replaced, X be the vertex set of its corresponding component and S 0 be the resulting graph
b
b ). Let C be the simple
after replacing x. Let Hi+1
be the child of Hia such that X ⊆ V (Mi+1
b
b
cycle in ∂(Mi+1 \ {ri+1 }) that encloses X. Then all vertices of C have level f (i + 1) and are
b . Further, C ⊆ H a ∩ D
0
shared by Hia and Hi+1
f (i+1) ⊆ S . Let u and v be any two remaining
i
a
vertices of V (Hi ). There are three edge-disjoint u-to-x paths and three edge-disjoint v-to-x
paths in S ∗ , all of which must intersect C. So there exist three edge-disjoint u-to-X paths
and three edge-disjoint v-to-X paths in S 0 . Now we delete two edges in S 0 . If these two edges
are not both in C, then the vertices of C are still connected. Then one remaining u-to-C path
and one remaining v-to-C path together with the rest of C witness the connectivity between
u and v. If the two deleted edges are both in C, then there exist one u-to-X path and one
v-to-X path after the deletion. By Claim 17, subgraph (S b ∪ Df (i+1) ) ∩ G[X] is connected. So
all vertices of X are connected in S 0 . Then u and v are connected after the deletion. Finally,
after replacing all the inner contracted nodes, we only add edges of Df (i+1) into S ∗ , which
will not break three-edge-connectivity between any pair of vertices. This finishes the proof of
Case 1.
b1
b2
Case 2: u, v ∈ M. Let Mi+1
be the graph contains u and Mi+1
be the graph contains v. (The two
b1
b1
graphs could be identical.) Let Cu (resp. Cv ) be the simple cycle in ∂(Mi+1
\ {ri+1
}) (resp.
b2
b2
∂(Mi+1 \ {ri+1 })) that enclose u (resp. v). (The two cycles Cu and Cv could be identical.)
Since S b1 is three-edge connected, there are three edge-disjoint paths from u to some vertex
of Cu in S b1 . All these three paths must intersect Cu , so there are three edge-disjoint paths
b1
from u to Cu in (S b1 \ {ri+1
}) ⊆ S a . Similarly, there are three edge-disjoint paths from v to
b
b
a
2
Cv in (S 2 \ {ri+1
}) ⊆ S . Now we delete any two edges in S a . After the deletion, there exist
one u-to-w1 path and one v-to-w2 path where w1 ∈ Cu and w2 ∈ Cv . Since all vertices in
V (Cu ∪ Cv ) have level f (i + 1) and are in Yia , they are three-edge connected in S a by Case
1. This means there exists a path from w1 to w2 after the deletion. Therefore, u and v are
connected after deleting any two edges in S a , giving the three-edge-connectivity.
b
be the graph containing v. Then there is a vertex w in
Case 3: u ∈ Yia and v ∈ M. Let Mi+1
a
b
b
Yi ∩ (Mi+1 \ {ri+1 }). By Case 1, vertices u and w are three-edge connected, and by Case 2,
vertices v and w are three-edge connected. Then vertices u and v are three-edge connected
by the transitivity of three-edge-connectivity.

This completes the proof of Lemma 16.
Proof of Theorem 1. We first prove correctness of our algorithm, and then prove its running time.

12

By Lemma 16, S =

S

i≥0,Ca ∈Ci


OPTw (Hia ) ∪ R is a feasible solution. Thus

S


a)
OPT
(H
+ |R|
w
i
S a ∈Ci
P i≥0,C
a
≤ i≥0 Ca ∈Ci OPTw (Hi ) + |R|

P
≤ i≥0 |OPT(G) ∩ (Hi \ R)| + |Df (i) | + |Df (i+1) | + |R| by Lemma 15
P
≤ i≥0 |OPT(G) ∩ (Hi \ R)| + |R| + |R| + |R|
≤ |OPT(G)| + 3|R|
by (2)
≤ |OPT(G)| + 36/k · |OPT(G)|
by (5)
≤ (1 + 36/k)|OPT(G)|

|S| ≤

Let k = 36/, and then we obtain |S| ≤ (1 + )|OPT(G)|.
Let n = |V (G)| be the number of vertices of graph G. We could find R and construct all slices
in O(n) time by Lemma 8. By Lemma 12, each slice has branchwidth O(k). So by Theorem 3,
we could solve the minimum-weight 3-ECSS on each slice in linear time for fixed k. Based on
those optimal solutions for all slices, we could construct our solution in O(n) time. Therefore, our
algorithm runs in O(n) time.

4

PTAS for 3-VCSS

In this section, we prove Theorem 2. W.l.o.g. assume G is simple. Then G is our spanner. Let
OPT(G) be an optimal solution for G. Since G is simple and planar, we have |G| ≤ 3|V (G)|. Then
by (3) we have |G| ≤ 2|OPT(G)|. In this section, we only consider 3VC slices. So in the following,
we simplify 3VC slice to slice. We first construct slices from G. By (1), we have the following
|R| ≤ 2/k · |G| ≤ 4/k · |OPT(G)|.

(9)

Similar to 3-ECSS, we want to solve a minimum-weight 3-VCSS problem on each slice. But
before defining the weights for this problem on each slice, we first need to show any slice is triconnected. The following lemma is proved by Vo [27], we provide a proof for completeness.
Lemma 18. ([27]) Let C be a simple cycle of G that separates G \ C into two parts: A and B. Let
H be any connected component of A. If G is triconnected, then G/H, the graph obtained from G
by contracting H, is triconnected.
Proof. Let x be the contracted node of G/H. Then x and any other vertex of G/H are triconnected
since G is triconnected. Let u and v be any two vertices of G/H distinct from x. To prove the
lemma, we show u and v are triconnected. Since x and u are triconnected, there are three vertexdisjoint paths between u and x. Note that all the three paths must intersect cycle C since V (C)
form a cut for x and all the other vertices in G/H. Similarly, there are three vertex-disjoint paths
between v and x, all of which intersect cycle C. Now we delete any two vertices different from u
and v in G/H. If the two deleted vertices are both in C, then there exist one u-to-x path and one
v-to-x path after the deletion, which witness the connectivity between u and v. If the two deleted
vertices are not both in C, the remaining vertices in C are connected and then the remaining u-to-C
path and the remaining v-to-C path together with the rest of edges in C witness the connectivity
between u and v. So u and v are triconnected.
By the same proof, we can obtain the following lemma.
13

Lemma 19. Let C be a simple cycle of G. Let u and v be two vertices of G \ C whose neighbors
in G are all in C. Then if G is triconnected, the graph obtained from G by identifying u and v is
triconnected.
Let Ci be the set of all simple cycles in ∂(G[Vf (i) ]). Then we have the following lemma.
Lemma 20. For any i ≥ 0 and any simple cycle Ca ∈ Ci , the slice Hia is triconnected.
Proof. Let Yia be the set of vertices of Hia that are not contracted nodes. We could obtain Hia by
contracting each connected component of G \ Yia into a node. Each time we contract a connected
component H of G \ Yia , there is a simple cycle C that separates H and other vertices: if H is
outside of Ca , then C = Ca ; otherwise C is some simple cycle in Ci+1 that encloses H. Then
by Lemma 18 the resulting graph is still triconnected after each contraction. Therefore, the final
resulting graph Hia is triconnected.
Now we define the edge-weight function w on a slice Hia : we assign weight 0 to edges in
Hia ∩ (Df (i) ∪ Df (i+1) ) and weight 1 to other edges. Then we solve the minimum-weight 3-VCSS
problem on slice Hia by Theorem 3. Let Sol(Hia ) be a feasible solution for the minimum-weight
3-VCSS problem on Hia . Then it is also a feasible solution for 3-ECSS on Hia . Let OPTw (Hia ) be
an optimal solution for this problem on Hia . Then we can prove the following two lemmas, whose
proofs follow the same outlines of the proofs of Lemmas 15 and 16 respectively.
S
Lemma 21. For any i ≥ 0, let Si = Ca ∈Ci OPTw (Hia ). Then we can bound the number of edges
in Si by the following inequality
|Si | ≤ |OPT(G) ∩ (Hi \ R)| + |Df (i) | + |Df (i+1) |.
Proof. We first show OPT(G)∩Hia is a feasible solution for minimum-weighted 3-VCSS problem on
any slice Hia . Let Yia be the set of vertices of Hia that are not contracted nodes. We first contract
each component of OPT(G) \ Yia into a node. The resulting graph after each contraction is still
triconnected by Lemma 18. After all the contractions, we identify any two contracted nodes x1 and
x2 if their corresponding components in OPT(G) are connected in G \ Yia . This implies there exists
a simple cycle C in Ci or Ci+1 such that all neighbors of x1 and x2 are in C. So by Lemma 19 the
resulting graph after each identification is also triconnected. Finally we delete parallel edges and
self-loops if possible. After identifying all possible nodes, the resulting graph has the same vertex
set as Hia and is triconnected. Since the resulting graph is a subgraph of OPT(G) ∩ Hia , we know
OPT(G) ∩ Hia is a feasible solution for minimum-weighted 3-VCSS problem on Hia .
Note that for any slice Hia , we have (Hia ∩ R) ⊆ (Hi ∩ R) ⊆ (Df (i) ∪ Df (i+1) ). By the optimality
of OPTw (Hia ), we have w(OPTw (Hia )) ≤ w(OPT(G) ∩ Hia ). Since all the nonzero-weighted edges
are in Hia \ R, Observation 3 still holds. Then we have
|OPTw (Hia ) ∩ (Hia \ R)| ≤ |(OPT(G) ∩ Hia ) ∩ (Hia \ R)| = |OPT(G) ∩ (Hia \ R)|.

(10)

Since for distinct (edge-disjoint) simple cycles Ca and Cb in Ci , subgraphs Hia \ R and Hib \ R are
vertex-disjoint, we have the following equalities.
[
Hi \ R =
(Hia \ R)
(11)
Ca ∈Ci

14

Si ∩ (Hi \ R) =
Then

[
Ca ∈Ci

(OPTw (Hia ) ∩ (Hia \ R))

S
|Si ∩ (Hi \ R)| = Ca ∈Ci (OPTw (Hia ) ∩ (Hia \ R))
P
≤ Ca ∈Ci |OPTw (Hia ) ∩ (Hia \ R)|
P
≤ Ca ∈Ci |OPT(G) ∩ (Hia \ R)|
≤ |OPT(G) ∩ (Hi \ R)|.

(12)

by (12)
by (10)
by (11)

So we have |Si | = |Si ∩ (Hi \ R)| + |Si ∩ (Hi ∩ R)| ≤ |OPT(G) ∩ (Hi \ R)| + |Df (i) | + |Df (i+1) |.
S

a ) ∪ R is a feasible solution for G.
Lemma 22. The union
Sol(H
i
i≥0,Ca ∈Ci
Proof. For any i ≥ 0 and any simple cycle Ca ∈ Ci , let Mia be the graph obtained from slice Hia
by uncontracting all the inner contracted nodes of Hia . By Lemma 4, there is at most one outer
contracted node ria for any slice Hia .
Define a tree T based on all the slices: each slice is a node of T , and two nodes Hia and Hjb
are adjacent if they share any edge and |i − j| = 1. Root T at the slice H0a , which contains the
b
boundary of G. Let T (Hia ) be the subtree of T that roots at slice Hia . For each child Hi+1
of Hia ,
a
b
let Cb be the simple cycle in Ci+1 that is shared by Hi and Hi+1 . Then Cb is the boundary of
b
b }.
Hi+1
\ {ri+1
b
We prove the lemma by induction on this tree from leaves to root. Assume
S for each child Hi+1
b
of Hia , there is a feasible solution S b for the graph Mi+1
such that S b =
∪
b ) Sol(H)
H∈T (Hi+1

S

b ∩
Mi+1
Df (j+1) . We prove that there is a feasible solution S a for Mia such that
 
S
S j≥i+1

a∩
D
. For the root H0a of T , we have M0a ∩
Sol(H)
∪
M
Sa =
a
f
(j+1)
i
j≥i
H∈T (Hi )
S

j≥0 Df (j+1) ⊆ R, and then the lemma follows from the case i = 0.
The base case is that Hia is a leaf of T . When Hia is a leaf, there is no inner contracted node in
a
Hi and we have Mia = Hia . So Sol(Hia ) is a feasible solution for Mia .
We first need a claim the same as Claim 17. Note that any inner contracted node of Hia is
enclosed by some cycle Cb . Let x be any inner contracted node of Hia that is enclosed by Cb , and X
be the vertex set of the connected component of G corresponding to x. Then we have the following
claim, whose proof is the same as that of Claim 17.
b
b , then (S b ∪ D
Claim 23. If X ⊆ Mi+1
for some Hi+1
f (i+1) ) ∩ G[X] is connected.

Now we ready to prove S a is a feasible solution for Mia . That is, we prove it is triconnected.
Let u and v be 
any two vertices of Mia . Let Yia = V (Hia) \ {inner contracted nodes of Hia }. Since
S
b
b
V (Mia ) = Yia ∪
Hb
is a child of H a V (Mi+1 \ {ri+1 }) , we have four cases.
i+1

i

Case 1: u, v ∈ Yia .
node of Hia , by

For any contracted component X in G that corresponds to an inner contracted
b .
Claim 23 all vertices in X are connected in (S b ∪ Df (i+1) ) ∩ G[X] if X ⊆ Mi+1
a
b
a
Then all vertices of X are connected in S ∩ G[X], since for any child Hi+1 of Hi we have
(S b ∪ Df (i+1) ) ⊆ S a . By the triconnectivity of Sol(Hia ), there are three vertex-disjoint paths
between u and v in Sol(Hia ). Since each inner contracted node of Hia could be in only
one path witnessing connectivity, the three vertex-disjoint u-to-v paths in Sol(Hia ) could be
transferred into another three vertex-disjoint u-to-v paths in S a by replacing each contracted

15

inner contracted node x with a path in the corresponding component X. So u and v are
triconnected in S a .
Case 2: u, v ∈ Mbi+1 \ {rbi+1 }. Since V (Cb ) is a cut for vertices enclosed by Cb and those not
enclosed by Cb , by the triconnectivity of G we have |V (Cb )| ≥ 3. By inductive hypothesis,
b , so there are three vertex-disjoint u-to-r b
b
S b is a feasible solution for Mi+1
i+1 paths in S .
All these three paths must intersect Cb by planarity, so there are three vertex-disjoint u-tob }) ⊆ S a . Similarly, there are three vertex-disjoint v-to-C paths in
Cb paths in (S b \ {ri+1
b
b }) ⊆ S a . If we delete any two vertices in S a , then there exist at least one u-to-w
(S b \ {ri+1
1
path and one v-to-w2 path for some vertices w1 , w2 ∈ Cb . Since all vertices in Cb have level
f (i + 1), they are in Yia . Then by Case 1, vertices w1 and w2 are triconnected in S a , so they
are connected after deleting any two vertices. Therefore, u and v are also connected after the
deletion.
Case 3: u ∈ Yia and v ∈ Mbi+1 \ {rbi+1 }. If one of u and v is in Cb , they are triconnected by Case
1 or 2. So w.l.o.g. we assume u is not enclosed by Cb and v is strictly enclosed by Cb . Since G
is triconnected, we have |V (Cb )| ≥ 3. We could delete any two vertices in S a and there exists
at least one vertex w in Cb . By Case 1, vertices u and w are connected after the deletion,
and by Case 2, vertices v and w are connected after the deletion. So u and v are connected
after the deletion.
1
1
2
2
Case 4: u ∈ Mbi+1
\ {rbi+1
} and v ∈ Mbi+1
\ {rbi+1
}. W.l.o.g. assume u is strictly enclosed by Cb1
and v is strictly enclosed by Cb2 , otherwise, by Case 3 they are triconnected. Since G is
triconnected, we have |V (Cb1 )| ≥ 3. After deleting any two vertices in S a , there exists a
vertex w ∈ Cb1 . By Case 2, vertices u and w are connected after deletion, and by Case 3
vertices v and w are connected after deletion. So u and v are connected after deletion.

This completes the proof of Lemma 22.
Proof of Theorem
2. We first prove
S
 the correctness, and then prove the running time. Let the
a
union S =
i≥0,Ca ∈Ci OPTw (Hi ) ∪ R be our solution. By Lemma 22, the solution S is feasible
for G. Then we have
S

a
|S| =
i≥0,Ca ∈Ci OPTw (Hi ) ∪ R
S

a
=
+ |R|
i≥0,Ca ∈Ci OPTw (Hi )
P
S
a
≤ i≥0 Ca ∈Ci OPTw (Hi ) + |R|

P
≤ i≥0 |OPT(G) ∩ (Hi \ R)| + |Df (i) | + |Df (i+1) | + |R| by Lemma 21
P
≤ i≥0 |OPT(G) ∩ (Hi \ R)| + |R| + |R| + |R|
≤ |OPT(G)| + 3|R|
by (2)
≤ (1 + 12/k)|OPT(G)|.
by (9)
We set k = 12/ and then we have |S| ≤ (1 + )|OPT(G)|.
Let n = |V (G)| be the number of vertices in graph G. We could find the edge set R in linear
time. By Lemma 9 we could construct all slices in O(n) time. So the slicing step runs in linear
time. By Lemma 12, the branchwidth of each slice is O(k) = O(1/). Therefore, we could solve the
minimum-weight 3-VCSS problem on each slice in linear time by Theorem 3. Based on the optimal
solutions for all the slices, we could construct our final solution S in linear time. So our algorithm
runs in linear time.
16

5

Dynamic Programming for Minimum-Weight 3-ECSS on graphs
with bounded branchwidth

In this section, we give a dynamic program to compute the optimal solution of minimum-weighted
3-ECSS problem on a graph G with bounded branchwidth w. This will prove Theorem 3 for
the minimum-weight 3-ECSS problem. Our algorithm is inspired by the work of Czumaj and
Lingas [9, 10]. Note that G need not be planar.
Given a branch decomposition of G, we root its decomposition tree T at an arbitrary leaf.
For any edge α in T , let Lα be the separator corresponding to it, and Eα be the subset of E(G)
mapped to the leaves in the subtree of T \ {α} that does not include the root of T . Let H be a
spanning subgraph of G[Eα ]. We adapt some definitions of Czumaj and Lingas [9, 10]. An separator
completion of α is a multiset of edges between vertices of Lα , each of which may appear up to 3
times.
Definition 1. A configuration of a vertex v of H for an edge α of T is a pair (A, B), where A is
a tuple (a1 , a2 , . . . , a|Lα | ), representing that there are ai edge-disjoint paths from v to the ith vertex
of Lα in H, and B is a set of tuples (xi , yi , bi ), representing that there are bi edge-disjoint paths
between the vertices xi and yi of Lα in H. (We only need those configurations where |ai | ≤ 3 for
P|Lα |
P
all 0 ≤ i ≤ |Lα | and |bi | ≤ 3 for all i ≥ 0.) All the i=1
ai + i bi paths in a configuration should
be mutually edge-disjoint in H.
Definition 2. For any pair of vertices u and v in H, let ComH (u, v) be the set of separator
completions of α each of which augments H to a graph where u and v are three-edge connected.
For each vertex v in H, let P athH (v) be a set of configurations of v for α. Let P athH be the set of
all the non-empty B in which all tuples can be satisfied in H. Let CH be the set consisting of one
value in each ComH (u, v) for all pairs of vertices u and v in H, and PH be the set consisting of one
value in each P athH (v) for all vertices v in H. We call the tuple (CH , PH , P athH ) the connectivity
characteristic of H, and denote it by Char(H).
Note that |Lα | ≤ w for any edge α. Subgraph H may correspond to multiple CH and PH , so H
may have multiple connectivity characteristics. Further, each value in PH represents at least one
2
vertex. For any edge α, there are at most 4O(w ) distinct separator completions (O(w2 ) pairs of
O(w2 )

vertices, each of which can be connected by at most 3 parallel edges) and at most 24
distinct
2
sets CH of separator completions. For any edge α, there are at most 4O(w ) different configurations
for any vertex in H since the number of different sets A is at most 4w , the number of different
2
sets B is at most 4O(w ) (the same as the number of separator completions). So there are at most
O(w2 )

O(w2 )

24
different sets of configurations PH , and at most 24
different sets B. Therefore, there
O(w2 )
4
are at most 2
distinct connectivity characteristics for any edge α.
P|L|
Definition 3. A configuration (A, B) of vertex v for α is connecting if the inequality i=1 ai ≥ 3
holds where ai is the ith coordinate in A. That is, there are enough edge-disjoint paths from
v to the corresponding separator Lα which can connect v and vertices outside Lα . Char(H) is
connecting if all configurations in its PH set are connecting. Subgraph H is connecting if at least
one of Char(H) is connecting. In the following, we only consider connecting subgraphs and their
connecting connectivity characteristics.

17

In the following, we need as a subroutine an algorithm to solve the following problem: when
given a set of demands (xi , yi , bi ) and a multigraph, we wantPto decide if there exist bi edge-disjoint
paths between vertices xi and yi in the graph and all the i bi paths are mutually edge-disjoint.
Although we do not have a polynomial time algorithm for this problem, we only need to solve
this on graphs with O(w) vertices, O(w2 ) edges and O(w2 ) demands. So even an exponential time
algorithm is acceptable for our purpose here. Let ALG be an algorithm for this problem, whose
running time is bounded by a function f (w), which may be exponential in w.
For an edge α in the decomposition tree T , let β and γ be its two child edges. Let H1 (H2 ) be
a spanning subgraph of G[Eβ ] (G[Eγ ]). Let H = H1 ∪ H2 . Then we have the following lemma.
Lemma 24. For any pair of Char(H1 ) and Char(H2 ), all the possible Char(H), that could be
2

obtained from Char(H1 ) and Char(H2 ), can be computed in O(4w f (w) + 4w

2 4w2

) time.

Proof. We compute all the possible sets for the three components of Char(H).
Compute all possible CH Each CH contains two parts: the first part covers all pairs of vertices
in the same Hi for i = 1, 2 and the second part covers all pairs of vertices from distinct subgraphs.
For the first part, we generalize each value C ∈ CHi for i = 1, 2 into a possible set XC . Notice
that each separator completion can be represented by a set of demands (x, y, b) where x and y
are in the separator. For a candidate separator completion C 0 of α, we combine C 0 with each
B ∈ P athH3−i to construct a graph H 0 and define the demand set the same as C. By running
ALG on this instance, we can check if C 0 is a legal generalization for C. This could be computed
2
2
in 4O(w ) w2 + 4O(w ) f (w) time for each C. All the legal generalizations for C form XC .
Now we compute the second part. Let (A1 , B1 ) ∈ PH1 and (A2 , B2 ) ∈ PH2 be the configurations
for some pair of vertices u ∈ H1 and v ∈ H2 respectively. We will compute possible ComH (u, v).
We first construct a graph H 0 on Lβ ∪ Lγ ∪ {u, v} by the two configurations: add i parallel edges
between two vertices if there are i paths between them represented in the configurations. Then we
check for each candidate separator completion C 0 if u and v are three-edge connected in H 0 ∪ C 0 .
We need O(w3 ) for this checking if we use Orlin’s max-flow algorithm [23]. All those C 0 that are
capable of providing three-edge-connectivity with H 0 form ComH (u, v). This can be computed in
2
4O(w ) w3 time for each pair of configurations.
A possible CH consists of each value in XC for every C ∈ CHi for i = 1, 2 and each value in
ComH (u, v) for all pairs of configurations of PH1 and PH2 . To compute all the sets, we need at
2
2
2
most 4O(w ) w3 + 4O(w ) f (w) time. There are at most 4O(w ) sets and each may contain at most
2 O(w2 )

2

4O(w ) values. Therefore, to generate all the possible CH from those sets, we need at most 4w 4
time.
Compute all possible PH We generalize each configuration (A, B) of v in PHi (i = 1, 2) into a
set Yv of possible configurations. For each set B 0 in P athH3−i , we construct a graph H 0 by A, B and
B 0 on vertex set Lβ ∪ Lγ ∪ {v}: if there are b disjoint paths between a pair of vertices represented
in A, B or B 0 , we add b parallel edges between the same pair of vertices in H 0 , taking O(w2 ) time.
For a candidate value (A∗ , B ∗ ) for α, we define a set of demands according to A∗ and B ∗ and run
ALG on all the possible H 0 we construct for sets in P athH3−i . If there exists one such graph that
satisfies all the demands, then we add this candidate value into Yv . We can therefore compute each
2
2
set Yv in 4O(w ) w2 + 4O(w ) f (w) time. A possible PH consists of each value in Yv for all v ∈ V (H).
2
2
There are at most 4O(w ) such sets and each may contain at most 4O(w ) values. So we can generate
2
2 O(w )
all possible PH from those sets in 4w 4
time.

18

Compute PathH For each pair of B1 ∈ P athH1 and B2 ∈ P athH2 , we construct a graph H 0 on
vertex set Lβ ∪Lγ : if two vertices are connected by b disjoint paths, we add b parallel edges between
those vertices in H 0 . Since each candidate B 0 for α can be represented by a set of demands, we only
need to run ALG on all possible H 0 to check if B 0 can be satisfied. We add all satisfied candidates
2
2
B 0 into P athH . This can be computed in 4O(w ) w2 + 4O(w ) f (w) time.
2

Therefore, the total running time is O(4w f (w) + 4w
all possible cases, and the correctness follows.

2 4w2

). For each component we enumerate

Our dynamic programming is guided by the decomposition tree T from leaves to root. For each
edge α, our dynamic programming table is indexed by all the possible connectivity characteristics. Each entry indexed by the connectivity characteristic Char in the table is the weight of the
minimum-weight spanning subgraph of G[Eα ] that has Char as its connectivity characteristic.
Base case For each leaf edge uv of T , the only subgraph H is the edge uv and the separator only
contains the endpoints u and v. ComH (u, v) contains the multisets of edge uv that appears twice.
P athH (u) contains two configurations: ((3, 0), {(u, v, 1)}) and ((3, 1), ∅), and P athH (v) contains
two configurations: ((0, 3), {(u, v, 1)}) and ((1, 3), ∅). P athH contains one set: {(u, v, 1)}.
For each non-leaf edge α in T , we combine every pair of connectivity characteristics from its
two child edges to fill in the dynamic programming table for α. The root can be seen as a base
case, and we can combine it with the computed results. The final result will be the entry indexed
by (∅, ∅, ∅) in the table of the root. Let m = |E(G)|. Then the size of the decomposition tree T
2

is O(m). By Lemma 24, we need O(4w f (w) + 4w

2 4w2

) time to combine each pair of connectivity

2
4O(w )

characteristics. Since there are at most 2
connectivity characteristics for each node, the total
2 4w 2
w2
w
4
m). Since the branchwidth w of G is bounded, the
running time will be O(2 f (w)m + 4
running time will be O(|E(G)|).
Correctness The separator completions guarantee the connectivity for the vertices in H, and
the connecting configurations enumerate all the possible ways to connect vertices in H and vertices
of V (G) \ V (H). So the connectivity requirement is satisfied. The correctness of the procedure
follows from Lemma 24.
Acknowledgements

We thank Glencora Borradaile and Hung Le for helpful discussions.

19

References
[1] B. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of
the ACM, 41(1):153–180, 1994.
[2] M. Bateni, M. Hajiaghayi, and D. Marx. Approximation schemes for Steiner forest on planar
graphs and graphs of bounded treewidth. J. ACM, 58(5):21, 2011.
[3] A. Berger and M. Grigni. Minimum weight 2-edge-connected spanning subgraphs in planar
graphs. In Proceedings of the 34th International Colloquium on Automata, Languages and
Programming, volume 4596 of Lecture Notes in Computer Science, pages 90–101, 2007.
[4] G. Borradaile, C. Kenyon-Mathieu, and P. Klein. A polynomial-time approximation scheme
for Steiner tree in planar graphs. In Proceedings of the 18th Annual ACM-SIAM Symposium
on Discrete Algorithms, volume 7, pages 1285–1294, 2007.
[5] G. Borradaile and P. Klein. The two-edge connectivity survivable network problem in planar
graphs. In Proceedings of the 35th International Colloquium on Automata, Languages and
Programming, pages 485–501, 2008.
[6] G. Borradaile, P. Klein, and C. Mathieu. An O(n log n) approximation scheme for Steiner tree
in planar graphs. ACM Transactions on Algorithms, 5(3):1–31, 2009.
[7] J. Cheriyan and R. Thurimella. Approximating minimum-size k-connected spanning subgraphs
via matching. SIAM Journal on Computing, 30(2):528–560, 2000.
[8] A. Czumaj, M. Grigni, P. Sissokho, and H. Zhao. Approximation schemes for minimum 2edge-connected and biconnected subgraphs in planar graphs. In Proceedings of the fifteenth
Annual ACM-SIAM Symposium on Discrete Algorithms, pages 496–505. Society for Industrial
and Applied Mathematics, 2004.
[9] A. Czumaj and A. Lingas. A polynomial time approximation scheme for euclidean minimum
cost k-connectivity. In Automata, Languages and Programming, pages 682–694. Springer, 1998.
[10] A. Czumaj and A. Lingas. On approximability of the minimum cost k-connected spanning
subgraph problem. In Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 281–290, 1999.
[11] H. N. Gabow and S. R. Gallagher. Iterated rounding algorithms for the smallest k-edge
connected spanning subgraph. SIAM Journal on Computing, 41(1):61–103, 2012.
[12] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of
NP-Completeness. WH Freeman & Co., 1979.
[13] T. F. Gonzalez. Handbook of Approximation Algorithms and Metaheuristics. CRC Press, 2007.
[14] P. Gubbala and B. Raghavachari. Approximation algorithms for the minimum cardinality
two-connected spanning subgraph problem. In Integer Programming and Combinatorial Optimization, pages 422–436. Springer, 2005.

20

[15] P. Gubbala and B. Raghavachari. A 4/3-approximation algorithm for minimum 3-edgeconnectivity. In Algorithms and Data Structures, pages 39–51. Springer, 2007.
[16] J. Hopcroft and R. Tarjan. Algorithm 447: Efficient algorithms for graph manipulation.
Commun. ACM, 16(6):372–378, June 1973.
[17] R. Jothi, B. Raghavachari, and S. Varadarajan. A 5/4-approximation algorithm for minimum
2-edge-connectivity. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 725–734, 2003.
[18] P. Klein. A linear-time approximation scheme for TSP in undirected planar graphs with
edge-weights. SIAM Journal on Computing, 37(6):1926–1952, 2008.
[19] P. Klein and S. Mozes. Optimization algorithms for planar graphs. In preparation, manuscript
at http://planarity.org.
[20] R. Lipton and R. Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied
Mathematics, 36(2):177–189, 1979.
[21] K. Mehlhorn, A. Neumann, and J. M. Schmidt. Certifying 3-edge-connectivity. In GraphTheoretic Concepts in Computer Science, pages 358–369. Springer, 2013.
[22] H. Nagamochi and T. Ibaraki. Computing edge-connectivity in multigraphs and capacitated
graphs. SIAM Journal on Discrete Mathematics, 5(1):54–66, 1992.
[23] J. B. Orlin. Max flows in O(nm) time, or better. In Proceedings of the forty-fifth Annual ACM
Symposium on Theory of Computing, pages 765–774. ACM, 2013.
[24] J. M. Schmidt. Contractions, removals, and certifying 3-connectivity in linear time. SIAM
Journal on Computing, 42(2):494–535, 2013.
[25] P. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217–241,
1994.
[26] R. Tarjan. A note on finding the bridges of a graph. Information Processing Letters, 1974.
[27] K.-P. Vo. Finding triconnected components of graphs.
13(2):143–165, 1983.

21

Linear and multilinear algebra,

