Approximation Schemes for Minimum 2-Edge-Connected and Biconnected Subgraphs in Planar Graphs
Artur Czuma j
Abstract Given an undirected graph, finding either a minimum 2-edge-connected spanning subgraph or a minimum 2vertex-connected (biconnected) spanning subgraph is MaxSNP-hard. We show that for planar graphs, both problems have a polynomial time approximation scheme (PTAS) with running time nO(1/) , where n is the graph size and  is the relative error allowed. When the planar graph has edge costs, we approximately solve the analogous min-cost subgraph problems in time nO( /) , where  is the ratio of the total edge cost to the optimum solution cost. 1 Intro duction

Michelangelo Grigni

Papa Sissokho

Hairong Zhao

Given an undirected graph G, the minimum 2-edgeconnectivity problem is to find a spanning subgraph with a minimum number of edges which is 2-edge connected (remaining connected after removing any one edge). The minimum biconnectivity problem is similar, except that the subgraph must be 2-vertex-connected (biconnected, remaining connected after removing any one vertex). When G has edge costs, we define the minimum-cost 2-edge-connectivity and biconnectivity problems similarly, where now we minimize the total edge cost of the subgraph. All these problems are NP-hard, even in the unweighted planar case. Furthermore they are MaxSNPhard for general graphs [6, 10] and for bounded-degree graphs [7]. Much effort has been put into achieving polynomial-time constant approximation ratio algorithms, see e.g., [4, 5, 6, 11, 16]. In arbitrary unweighted graphs, the best currently known approximation ratios are 5 for 2-edge-connectivity [11] and 4 for biconnectiv4 3 ity [16].
 Department of Computer Science, New Jersey Institute of Technology, Newark NJ 07102, USA. Email: czumaj@cis.njit.edu, hairong@cis.njit.edu.  This work was supp orted by NSF Grants CCR-9820931 and CCR-0208929. Department of Mathematics and Computer Science, Emory University, Atlanta GA 30322, USA. Email: mic@mathcs.emory.edu.  Department of Mathematics, Illinois State University, Normal IL 61790, USA. Email: psissok@ilstu.edu.

We would prefer a polynomial time approximation scheme (PTAS): an algorithm taking an instance G and a positive , returning a solution with cost at most (1+) times optimum, and running in time that is polynomial for each fixed . The MaxSNP-hardness results imply that there is no hope of a PTAS in general (unless P=NP), but a PTAS could still exist for special cases. Indeed, based on the framework of Arora [2], a PTAS was found [7, 8] for the problem of finding a minimumcost k -vertex (or k -edge) connected spanning subgraph in complete Euclidean graphs in bounded dimension. In this paper we consider the case that the input graph G is planar. We show a PTAS for the minimum 2-edge-connectivity problem and a PTAS for the minimum biconnectivity problem, both running in time nO(1/) . More generally, when the planar graph has edge weights our algorithms approximately solve the minimum-cost problems in time nO( /) , where  is the ratio of the total edge cost to the optimum solution cost. This is a PTAS when  is bounded; note that  is bounded (by 3) when the edge weights are uniform. Our general approach resembles the approximation schemes for metric-TSP in planar graphs [3, 12, 13]. We use a separator theorem, hierarchical decomposition, and dynamic programming. Our separator finds lowcost cycles in a planar graph so that after contracting those cycles (and committing their edges to our approximate solution), the remaining graph has a logarithmic size vertex separator. Using this, we recursively divide the input graph G into pieces, forming a decomposition tree T of logarithmic depth. Each piece has a logarithmic number of "portal" vertices connecting it to the rest of G. For each piece, we enumerate all the different ways that some subgraph of G (outside this piece) may influence the connectivity constraints within this piece. We call these the external types of the piece, and we show that the number of such types is a simple exponential in the number of portals. For each piece in T and for each external type, we must find a near minimum cost subgraph H of the piece, so that H together with the external type can meet the global connectivity constraints. We solve these problems by dynamic programming, working up T from the leaves to the root G.

Copyright © 2004 by the Association for Computing Machinery, Inc. and the Society for industrial and Applied Mathematics. All Rights reserved. Printed in The United States of America. No part of this book may be reproduced, stored, or transmitted in any manner without the written permission of the publisher. For information, write to the Association for Computing Machinery, 1515 Broadway, New York, NY 10036 and the Society for Industrial and Applied Mathematics, 3600 University City Science Center, Philadelphia, PA 19104-2688

496


In the following, 2-EC denotes "2-edge-connected", 2-VC denotes "2-vertex-connected" (or biconnected), 2ECSS denotes "2-edge-connected spanning subgraph", 2-VCSS denotes "2-vertex-connected spanning subgraph", and c(H ) denotes the total edge cost of a subgraph H . Our main results are summarized in the following two theorems. Theorem 1.1. Let  > 0, let G be a 2-EC planar graph with edge costs, and let OPT be the minimum cost of a 2-ECSS in G. There is an algorithm taking inputs G and , running in time nO(c(G)/(OPT·)) , and producing a 2-ECSS H in G such that c(H )  (1 + ) · OPT. Theorem 1.2. Let  > 0, let G be a 2-VC planar graph with edge costs, and let OPT be the minimum cost of a 2-VCSS in G. There is an algorithm taking inputs G and , running in time nO(c(G)/(OPT·)) , and producing a 2-VCSS H in G such that c(H )  (1 + ) · OPT.

As remarked above, each claimed algorithm is a PTAS when the ratio  = c(G)/OPT is bounded. In particular, Theorems 1.1 and 1.2 imply a PTAS for Definition 2.1. A bipartition of a set P is a pair of the unweighted minimum 2-edge-connectivity and the nonempty subsets {S1 , S2 } such that S1  S2 = P and minimum biconnectivity problems. S 1  S2 =  . Suppose G is a graph, P  V (G), and k is a positive Corollary 1.1. Let  > 0, let G be a 2-EC planar integer. The (k-E C, P )-type of G is a table t indexed graph, and let OPT be the minimum number of edges of by bipartitions {S1 , S2 } of P , and holding the values a 2-ECSS in G. There is an algorithm taking inputs G t(S1 , S2 ) = min (k , Ce (S1 , S2 )). G and , running in time nO(1/) , and producing a 2-ECSS Suppose t1 and t2 are (k-E C, P )-types of two H in G that has at most (1 + ) · OPT edges. graphs sharing the vertex subset P ; they are compatible iff t1 (S1 , S2 ) + t2 (S1 , S2 )  k for al l {S1 , S2 }. Corollary 1.2. Let  > 0, let G be a 2-VC planar graph, and let OPT be the minimum number of edges of Intuitively, the (k-E C, P )-type describes how P is a 2-VCSS in G. There is an algorithm taking inputs G crossed by edge cuts using less than k edges. We and , running in time nO(1/) , and producing a 2-VCSS are usually only interested in the type when G is (k-E C, P )-safe, meaning that all edge cuts of G not H in G that has at most (1 + ) · OPT edges. crossing P use at least k edges. The relevance of such Our main technical contributions are the mo dified types to the k -ECSS problem follows from this simple separator theorem, the notion of types (both 2-EC claim: and 2-VC, each represented by small graphs), and the simple exponential bounds on the number of external Claim 2.1. Suppose H1 and H2 are graphs with distypes possible within a portal face. In this abstract we joint edge sets, and V (H1 )  V (H2 ) = P . Then H1  H2 concentrate on Theorem 1.1, with only a sketch of the is k -EC iff: new ideas required for Theorem 1.2. 1. H1 is (k-E C, P )-safe, 2 Cuts and k -EC Typ es In this paper, graphs are undirected, without self-lo ops but possibly with parallel edges. Each edge e has a nonnegative cost ce ; a subgraph or minor H inherits edge costs from its parent graph, and c(H ) denotes the total edge cost of H . Suppose G = (V , E ) is a graph and S1 , S2 are disjoint subsets of its vertex set V = V (G). S1 and S2 are separated if there is no path 2. H2 is (k-E C, P )-safe, and 3. the (k-E C, P )-types of H1 and H2 are compatible.

in G from a vertex of S1 to a vertex of S2 . An edge set F  E separates S1 and S2 if they are separated in G - F ; we also say that F is an edge cut for S1 and S2 . Similarly, a vertex cut for S1 and S2 is some U  V - (S1  S2 ) such that S1 and S2 are separated in G - U . We let Cute (S1 , S2 ) denote a minimum size G edge cut, and Ce (S1 , S2 ) = |Cute (S1 , S2 )| is the edge G G capacity between S1 and S2 . We define Cutv (S1 , S2 ) G and Cv (S1 , S2 ) similarly. We may efficiently compute G such min cuts using max-flow. For P  V , we say that a (vertex or edge) cut crosses P if it separates some S1 and S2 such that S1  S2 = P . A cycle has no repeated vertex, but it may consist of two vertices joined by two parallel edges. For e  E , G/e denotes the graph obtained by contracting e (that is, identifying its endpoints). If C is a cycle of G, G/C is the graph obtained by contracting the edges of C . After contraction we discard self-lo ops, but we retain parallel edges. A minor of graph G is a graph obtained from G through a series of such edge contractions and edge/vertex deletions.

We may abbreviate the third condition above by saying that H1 and H2 (or H1 and the type of H2 , or vice versa) are compatible. Suppose G1 and G2 are edge disjoint graphs with V (G1 )  V (G2 ) = P . To solve the k -ECSS problem in G1  G2 , it suffices to do the following:

497


1. For each possible type t1 of a subgraph of G1 , find a min-cost (k-E C, P )-safe spanning subgraph H2 of G2 compatible with t1 . 2. For each possible type t2 of a subgraph of G2 , find a min-cost (k-E C, P )-safe spanning subgraph H1 of G1 compatible with t2 . 3. Consider all pairs of H1 from Step 1 and H2 from Step 2. Return the min-cost compatible pair. We will use a similar approach in our algorithm; in particular we need a polynomial bound on the number of distinct subgraph types considered. We may succinctly represent the (k-E C, P )-type of G by a smaller graph t(G) which contains P and has the same type. In particular a minor of G contains P as long as we have neither deleted a vertex of P , nor contracted two vertices of P together. In the special case of k = 2, we shall construct such a t(G) from G by applying the following rules, until none apply: 1. If a cycle C has a chord (an edge e  E (C ) connecting two vertices of C ), delete the chord.

a2 consecutive at p, so that f1 and f2 share at least one edge. Now consider the part of t(G) drawn between a1 and a2 : it has no cycles (by rule 2) and is connected, so it is a tree. Because t(G) is (2-E C, P )-safe, it is a path from p to q . By rule 3 it must be an edge directly between p and q . But then it is a chord between f1 and f2 , so it should have been deleted by rule 1. Therefore A is a simple outerplanar graph on vertex set P , so it has less than 2|P | arcs. Further if we add arcs from the outer faces of t(G) (those faces bounded by a segment of the boundary), we still have at most three parallel arcs per pair of portals, therefore at most 6|P | arcs. For each p  P , its degree in t(G) is at most the number of adjacent arcs; therefore the sum of the degree of p in t(G), over all p  P , is at most = 12|P |. Now if we erase each portal and an infinitesimal neighborhood around it, the graph t(G) is transformed into a forest (by rule 2) with leaves, and all internal vertices of degree at least 3 (by rule 3). Then t(G) has less than vertices not in P , or in other words t(G) has less than 13|P | vertices overall.

we see that it is also a planar (2-E C, P )-safe graph embedded in the disk with P on the boundary. Every internal face f of t(G) has at least two portals. If f has exactly two portals, we draw an arc ef inside f between those two portals. If f has d  3 portals, we draw a cycle of d arcs within f connecting the portals. These arcs form an outerplanar graph A on the portals. We claim A has no parallel edges. Suppose instead that two portals p, q  P are connected by two parallel arcs a1 and a2 , from faces f1 and f2 . Since all faces must involve at least two portals, we can choose a1 and

Lemma 2.2. With G and P embedded as in the previous lemma, the number of distinct (2-E C, P )-types defined 2. If a cycle C has at most one vertex in P , contract by subgraphs of G is 2O(|P |) . C to a point. Proof. Let H be a subgraph of G containing P . By 3. If a vertex v  P has degree 2, contract it with a trimming H , we can make it (2-E C, P )-safe without neighbor. changing its (2-E C, P )-type. In the previous pro of we The correctness of the above follows from the observa- saw that t(H ) can be described by a planar forest T tion that all 0-edge cuts and 1-edge cuts of P are invari- with at most 12|P | leaves, internal vertices of degree ant under the above rules. In our application we need at least three, and each leaf labeled by some p  P , to consider the situation where G is embedded in a disk where the labels for a given p are on consecutive leaves. O (| P | ) with the vertices of P on the boundary. In the next two By standard tree counting techniques, there are 2 lemmas we bound the size of t(G), and we also bound such graphs, and therefore at most that many distinct the total number of possible (2-E C, P )-types induced (2-E C, P )-types. by subgraphs of G. 3 Planar Separators Lemma 2.1. Suppose G is a (2-E C, P )-safe planar We want to approximately solve the 2-ECSS problem graph embedded in the disk, with the vertices of P on the in a planar graph G embedded on a sphere. If we can disk boundary. Then t(G) is a planar graph embedded find a low-cost simple cycle C in G, then we may divide in the same way, with O(|P |) vertices. our problem into subproblems by contracting C . This Proof. By considering the three rules used to form t(G), follows from two observations: Fact 3.1. For any subgraph H of G containing C , H is a 2-ECSS in G iff H/C is a 2-ECSS in G/C . (This does not use planarity.)

Fact 3.2. When we contract C , the sphere pinches into two spheres kissing at the new contracted vertex (a cut-point). Therefore the 2-ECSS problem in G/C is equivalent to two disjoint 2-ECSS problems, one on each sphere. Therefore to approximately solve the 2-ECSS problem in G, we contract C and approximately solve the two

498


independent 2-ECSS subproblems. Then we lift the edges of those two solutions back to G and add the cycles F in G edges of C , to get a 2-ECSS in G. The additive error of this solution (the difference between its cost and the optimal cost) is at most the sum of the errors of the two subproblems plus c(C ). We will not always be lucky enough to find a light cycle which do es a go o d enough job of separating G, therefore we consider a more general kind of separator combining cycles with a Jordan cut : a Jordan cut of G Jordan cut J in G' is a closed Jordan curve in the embedding of G that do es not cross (intersect the interior of ) any edge. Given a Jordan cut J , every edge is either in the interior or the exterior of J , but those vertices and faces intersected by J are not counted in either the interior or the exterior of J . The following theorem is a mo dification of Miller's G1 G2 planar separator theorem, as already used for the planar TSP [3, 12, 15]. Our main technical change is to use up to three "caps" of Miller's cycle tree (the ro ot cap and at most two leaf caps) as contractible cycles. Due to Figure 1: The separator theorem. The Jordan cut space limitations, we omit the details here. vertices become portals in G1 and G2 . (up to three) pinched cycle interiors, the interior of J , and the exterior of J . We let G1 denote Q together with the subgraph of G interior to J , and we let G2 denote Q together with the subgraph of G exterior to J . In this way G1  G2 = G , E (G1 )  E (G2 ) = , and 1. F is the union of at most three vertex-disjoint V (G1 )  V (G2 ) = Q. In the inherited embedding of simple cycles (maybe none). Their total edge cost G1 (or G2 ) all vertices of Q appear on a single new face c(F ) is O(M /k ). The cycles are non-nesting, which we call a portal face ; the old faces that intersected meaning we may choose an embedding of G so that J are gone. When solving 2-ECSS in G, we will see that the "pinched off " cycle interiors become independent 2their interiors are disjoint. ECSS problems, but the subproblems in G1 and G2 are 2. The interior of each Ci has weight at most (2/3)W . dependent because they share Q. 3. Let G be the embedded graph that results after we "pinch off " the interiors of the cycles ( G is G/F 4 The 2-ECSS Algorithm minus the interior parts from each cycle). Each We are given as input an embedded planar 2-EC graph new contracted vertex has weight 0. G0 with n vertices, non-negative edge costs, and a 4. J is a Jordan cut of G passing through the new parameter  > 0. We assign weight 1 to each vertex contracted vertices, and the interior and exterior and weight 0 to each face. By existing approximation of J each have weight at most (2/3)W . algorithms we estimate OPT(G0 ), the minimum cost of o 5. Q, the set of vertices of G n J , has size at most a 2-ECSS, within a constant factor. We fix an integer k = (( /) log n), where  = c(G0 )/OPT(G0 ). k. We build a ro oted decomposition tree T from G0 See Figure 1. When we apply the above theorem, we as follows. Each node of T stores an embedded planar say Q is the set of new1 portal vertices introduced by graph G, which has edge costs, vertex/face weights, and the separator. The original graph G has been divided some distinguished subset P of "portal" vertices. The into at most five parts of weight at most (2/3)W : the root of T stores G0 itself, with no portals. Each node of T has at most five children, defined inductively as 1 We are reserving "P " to denote all p ortals in a graph, new or follows. Let G be the graph stored at a no de of T , and let W old. Theorem 3.1. Let G be a plane graph with n vertices, with non-negative weights on its vertices and faces, and non-negative costs on its edges. Let W be the total weight and let M be the total cost. Given parameter k  1, in O(n log n) time we may find a subgraph F of G and a Jordan cut J (as described below) so that:

499


be its total vertex/face weight. If W is O(k 2 ), then this no de is a leaf of T . Otherwise, apply Theorem 3.1 to partition G into at most five pieces (up to three pinched cycle interiors and G1 , G2 ), each of total weight at most (2/3)W . Uncontracted portal vertices from G remain as portals in each piece where they appear; the graphs G1 and G2 each get at most k new portals, the set Q. In G1 and G2 , we assign a weight of W/(12k ) to each new portal, and weight W/12 to the new portal face. With these new weights, G1 and G2 still have total weight at most (5/6)W . By the separator properties, we see that each G in T is (2-E C, P )-safe, and that the tree T has depth O(log n) and size O(n log n). By our construction P is the set of portals in G, which have been intro duced by some Jordan cut but not yet cut off by a cycle contraction or another Jordan cut. It follows from our portal/hole weighting scheme [3, 12] that |P | is O(k ), and G has O(1) portal faces. Each portal face contains a hole made by a Jordan cut at some ancestor of G in T . Note that a Jordan cut might cut (simply) across an existing portal face, in which case some old portals may appear on the new portal face, but this still counts as a single portal face. Or in terms of an embedding on a sphere with holes, all old holes crossed by the Jordan cut disappear, with segments of their boundaries incorporated into the one new hole boundary. G is connected via P to the rest of G0 (really a pinched and contracted version of G0 ) which can be embedded as disjoint pieces, one in each portal face of G. Therefore the (2-E C, P )-type imposed on P by the rest of G0 decomposes into independent types, one in each portal face of G. By applying Lemma 2.2 to each portal face, we may bound and enumerate the 2O(|P |) = nO( /) different (2-E C, P )-types that may be imposed on P by the rest of G0 . Call this list the list of external types for G. It is more efficient, although not essential for our purposes, if we represent each external type t of G as a planar graph of size O(|P |) (see Lemma 2.1) embedded in the portal faces of G. In particular at the ro ot of T the input graph G0 has no portals, and therefore it has the "empty" external type t0 . Having computed T and these external type lists, we may now define a set of subproblems that we want to approximately solve:

is compatible with G itself. The total number of subproblems (over all choices of G and t) is nO( /) , and the subproblem (G0 , t0 ) is our original 2-ECSS problem. We will approximately solve each subproblem starting at the leaves of T and finishing at the ro ot. We use dynamic programming, storing our solutions to avoid recomputation. In the base case, G is a leaf of T and has size N = O(k 2 ). Then we apply an enumerative metho d based on Lipton-Tarjan se arators [14] to exactly solve such p O( N ) subproblems in 2 = nO( /) time (this may be regarded as a continuation of our metho d, using Jordan cuts without cycle contractions). We omit details. Otherwise G is not a leaf, and has up to five children in T as found by Theorem 3.1. We have a specific external type t, which decomposes into an independent external type in each portal face of G. For each child GC of G which was pinched off in the interior of some cycle C , let tC be the subtype of t induced by the portal faces inside C , and lo okup our solution HC to the subproblem (GC , tC ). We lift the edges of HC and the edges of C to be part of our approximate solution H for the (G, t) subproblem. Now we must consider the two remaining children G1 and G2 . As in Theorem 3.1, let G be what is left of G after we contract the (up to three) cycles and pinch off their interiors; so G1  G2 = G . Let t denote the external type induced by t in the portal faces of G . Not knowing the optimal choice of external types t1 and t2 for G1 and G2 , we try them all. That is, for every pair (t1 , t2 ) where subproblems (G1 , t1 ) and (G2 , t2 ) were found feasible, we lo okup their solutions H1 and H2 and check whether H = H1  H2 is compatible with t . We take the cheapest compatible H found, and lift its edges back to G. These edges of H , together with the C and HC edges mentioned earlier, comprise our approximate solution H for the (G, t)-subproblem. Although G is not actually associated with a no de of T , note that we can still speak sensibly of the (G , t ) subproblem as defined above. In fact it would be a simple matter to reformulate T as a binary tree including G : at each internal no de of T we would either pinch one cycle, or apply a Jordan cut.

4.1 Analysis Our algorithm solves nO( /) subproblems, each in nO( /) time, so the total running time is nO( /) . Definition 4.1. For G in T (with portal set P ) and Consider a feasible subproblem (G, t). By planarity, an external type t for G, the subproblem (G, t) is this: t decomposes into independent types in each portal face, find a min-cost (2-E C, P )-safe spanning subgraph H of and these faces cannot cross a cycle; therefore each G which is compatible with t, or else declare that (G, t) cycle-pinched subproblem (G , t ) and the remaining CC is infeasible (no such H ). subproblem (G , t ) are all feasible. Taking the external a Checking feasibility is simple: just check whether t type on G1 induced by G2  t s t1 , we see that (G1 , t1 )

500


is feasible. Supposing (by induction) that our algorithm found some solution H1 for (G1 , t1 ), then H1  t induces an external type t2 on G2 such that (G2 , t2 ) is also feasible. Therefore by induction up T , our algorithm finds some solution for each feasible (G, t)-subproblem. Now suppose H is the solution our algorithm finds for a feasible subproblem (G, t). Define the error on (G, t) as the difference between the found cost c(H ) and the minimum possible cost. For each pinched cycle C (up to three), by Facts 3.1 and 3.2 subproblem (G, t) will inherit the error of (GC , tC ) plus an additional additive error of at most c(C ). After pinching cycles, the remaining error of (G, t) is that from (G , t ). Recall G = G1  G2 ; let H  be the unknown optimal solution for (G , t ). Let t denote 1 the external type of G1 induced by (H   G2 )  t , and similarly let t denote the external type of G2 induced 2 by (H   G1 )  t . Then (Gi , t ) has the optimal solution i H   Gi (for i = 1, 2), and (t , t ) is a compatible type 12 pair considered by our algorithm; if we solved these two subproblems optimally, our solution cost would be c(H  ). Therefore our error on (G , t ) is at most the sum of our errors on (G1 , t ) and (G2 , t ), even though 1 2 we might not actually find our best solution H using this pair. Therefore error terms simply add at a Jordan cut. Therefore the total error of our ro ot problem (G0 , t0 ) is at most the sum of c(C ) over all cycles contracted in T . We see that for any level of T , the total edge cost of that level is at most c(G0 ), therefore the total edge cost of all cycles contracted on that level is O(c(G0 )/k ). Summing over all O(log n) levels of T , the total error from all levels of T is O((c(G0 )/k ) log n). By an appropriate choice of the leading constant defining k , this is at most  · OPT(G0 ). Therefore our final solution has cost at most (1 + )OPT(G0 ), proving Theorem 1.1. 5 Sketch of the 2-VCSS Algorithm Here we sketch the 2-VCSS algorithm claimed in Theorem 1.2. The main idea is similar to the 2-ECSS algorithm. Given the input plane graph G0 , we use the separator theorem to decompose G0 hierarchically into small pieces. For each piece, we use types to enumerate the different ways that the "rest" of the graph may influence the connectivity constraints within this piece. Then, we use dynamic programming to approximately find the minimum subgraph compatible for each type of each piece. Similarly we can prove that the number of external types of each piece is a simple exponential in the number of portals (Lemma 5.2), yielding the same running time analysis. Again the only source of error is in the weight of the separating cycle edges, yielding the same error analysis.

However, there are some difficulties preventing us from using the same technique to solve the 2-VCSS problem. The principle difficulty is cycle contraction. In the 2-ECSS algorithm, the decomposition, type definition and dynamic programming are all performed on the minors of G0 , and we showed this is sufficient. But it is no longer reasonable to contract the cycles in the 2-VCSS problem, because this changes the problem (in particular, it may intro duce a false cutvertex). Therefore for each node in T , we keep a pair of graphs, the compressed subgraph G as defined in the 2-ECSS algorithm and its corresponding uncompressed subgraph G, that is the subgraph of G0 induced by all vertices which appear (after cycle contractions) as some vertex in G. As before, the separator theorem is still applied to G, and the decomposition of G is obtained naturally. But the type and dynamic programming will be defined on G. The uncompressed graph G also contains portal vertices and portal faces, which are the preimages of the portals and portal faces in G. Specifically, let J be the Jordan cut when we apply the separator theorem to G. Let p be a vertex on J . If p is mapped to a single vertex of G, then p is a new portal that will be contained in the subgraphs of G. Otherwise, p is mapped to many vertices which are on a series of cycles in G, then at most 2 of these vertices will be specified as new portals of G. These two vertices are where the Jordan cut J would intersect G if we uncontract the cycles represented by p. Thus we still have O(k ) portals in G. Each portal appears on some portal face in G corresponding to the portal faces of G, and the portal faces identify where "the rest of G0 " would appear in our embedding. The edges of each separating cycle will appear in G as hard edges which are committed to our solution as in the 2-ECSS algorithm. We must also redevelop the notion of types in the biconnected context, so that we may again use types to characterize the possible counterparts of an uncompressed graph; this is the point of Lemma 5.1 below. For convenience, we develop types simply as graphs (rather than abstract cut tables represented by graphs, as in Section 2). We begin with a definition analogous to "(k-E C, P )-safe" graphs. Definition 5.1. For a graph G = (VG , EG ) with a portal set P  VG , any graph H = (VH , EH ) for which VH  VG  P is cal led a counterpart (of G). G is cal led (2-V C, P )-safe if it has a counterpart H such that G  H is biconnected. 5.1 Typ es of (2-V C, P )-safe planar graphs The type of a (2-V C, P )-safe graph is a graph describing a simplified characterization of the biconnectivity infor-

501


mation of the portals in the graph. Definition of the typ e. Our definition of type is operational and it is oriented towards Lemmas 5.1 and 5.2 below. Let H = (VH , EH ) be any (2-V C, P )-safe graph (do es not have to be planar) with a distinguished portal set P and a distinguished set of hard edges EH,r . We define the type t(H ) of H by performing a series of operations on H . See Figure 2 for an illustration. 1. Let Hr be the graph consisting all portals of P and all the edges of EH,r . We construct a simplified graph Hr from Hr that is a forest formed by a collection of (possibly connected) stars2 : (a) All vertices of Hr are included in Hr . (b) Every portal of P is marked as a super-portal. (c) For each blo ck of Hr (hard blo ck) with at least two vertices, create a new vertex in Hr as a super-portal and connect by an edge the superportal to every vertex in the blo ck. (d) Mark all cutvertices and the end vertices of the isolated edges in Hr as super-portals in Hr . (e) Assign distinct IDs to all super-portals. 2. Replace the subgraph Hr of H by the graph Hr and remove those vertices that have no ID and are adjacent only to a super-portal (notice that the removed vertices are all connected only to vertices of a hard blo ck of Hr ). Let the obtained graph be H. 3. For each blo ck of H that is not a bridge, if it has exactly two cutvertices and do es not contain a super-portal, contract it into a single vertex. 4. Repeat the following two operations until none apply. (a) Remove all chords in any cycle of H . (b) For each path  of H with no super-portals as internal vertices and all internal vertices with degree exactly 2, contract  to an edge with the same end vertices as  .

(a) Add each cutvertex x in H to t(H ), and refer to x as a cutvertex in t(H ). If it is a superportal p in H , then it is a portal-no de in t(H ) with the ID of p. (b) For each blo ck in H that do es not contain any super-portals, contract it to a vertex in t(H ). We refer to this vertex in t(H ) as a block-vertex. (c) For each blo ck in H containing exactly one super-portal p, contract this blo ck to a blo ckvertex. If the blo ck is not a bridge and p is not a cutvertex in H , then this block-vertex is a portal no de in t(H ) with the ID of p. (d) Connect a block-vertex by an edge in t(H ) to each cutvertex adjacent to it or to the endvertices of the bridge if the blo ck-vertex is obtained from the bridge in H . (e) If a blo ck has two or more super-portals, then keep the blo ck in t(H ) as it is in H . (f ) Finally, for each path  of t(H ) with no portalnodes as internal vertices and all internal vertices with degree exactly 2, contract  to a single edge with the same end vertices as  . Note the concept of super-portal can be applied to any graph H that contains portals and hard edges, and it is completely determined by the portal set and the hard edge set of H . Prop erties of the typ es. We list now some basic properties of the types. First of all, the number of labels of t(H ) is identical to the number of super-portals of H . Secondly, let us notice that the type t(H ) is uniquely defined. This allows us to say that two (2-V C, P )safe graphs H1 and H2 on the same vertex set and with the same set of portals and hard edges have the same type if t(H1 ) and t(H2 ) are identical with respect to their IDs. Thirdly, all vertices that are not portalnodes have degree at least 3. Next, we notice that if H is biconnected and the portal set and hard edges are empty, then t(H ) contains a single vertex (blo ckvertex). Finally, if we consider the subgraph of H induced by non-portals and the corresponding subgraph in t(H ), we only removed the cutvertices of H that are internal "vertices" on "paths" consisting only degree 2 internal vertices3 . Thus, the connections among portals in H are represented by the connections of portal no des in t(H ). This property can be summarized in the following lemma.

5. Let H be the graph obtained after Steps 1­4. The type t(H ) is a graph with some vertices labeled (having IDs, these are vertices corresponding to super-portals and will be called portal no des) and the other vertices not labeled that is constructed Lemma 5.1. Let G and H be two (2-V C, P )-safe from H as follows: graphs that have the same set of portals P and the same
2 Notice a similarity of this construction to the standard construction of cutvertex-trees, see, e.g., [9]. 3 Some

vertices are in fact blocks with two cutvertices.

502


set of hard edges Er . Let t(H ) be the type of H . Then cycles. Because the depth of the decomposition tree for any spanning subgraph G of G that contains al l hard is at most O(log n) and at each no de we intro duce at edges in Er , t(G ) and t(H ) have the same set of portal- most 3 "cycles" 4 , the number of hard "cycles" is at nodes with respect to IDs, and G  H is biconnected if most O(log n). Hence the number of super-portals of H and only if t(G )  t(H ) is 2-edge connected and the is O(k ) + O(log n) = O(k ). By Lemma 5.2, H has at cutvertices of t(G )  t(H ) are block-vertices of t(H ) or most 2O(k) = nO( /) external types. t(G ) or the super-portals resulting from contraction of hard blocks as defined in the type. 6 Concluding Remarks A deficiency of our algorithms is their dependence on the Next, we consider the number of types. Specifically, ratio  = c(G)/OPT. We know of no hardness result we consider the number of external types of (2-V C, P )justifying this dependency, and indeed a very similar safe plane graphs. Let G be a (2-V C, P )-safe plane dependency in the context of the TSP was eliminated graph with a hard edge set Er and a portal face set using a "spanner" construction [1, 3, 13] which safely F . Let the super-portal set of G determined by P and prunes some heavy edges out of G. Er be Ps . If H be a counterpart of G that can be Another direction of research is to extend our methembedded in F , then we say the type t(H ) of H is an o ds to similar problems, such as the 3-ECSS problem in external type of G with respect to F . We will fo cus on planar graphs, or the 2-ECSS and 2-VCSS problems in the counterpart H of G that also is (2-V C, P )-safe and more general graph families. We remark on some of shares the same set of super-portals Ps (i.e., H and G these problems below; in all cases, progress depends on have the same set of portals and hard edges). Then, the the development of appropriate separator theorems. type t(H ) is called an external type of G with respect Planar 3-ECSS: Here we need to generalize to Ps and F . Our goal is to show that the number of Lemma 2.2; let us remark that counting planar Gomoryexternal types of G with respect to Ps and F is small, Hu trees is not sufficient. Also cycle contraction no that is, it is only exponential in |Ps |. Now we state the longer works here, because the cycle vertices are not 3main lemma bounding the number of types; we omit the edge connected. However we can modify our separator pro of in this abstract. theorem to replace cycles with bicycles : a bicycle is two Lemma 5.2. Let G = (VG , EG ) be a (2-V C, P )-safe nested cycles, with all in-between faces visible from one of the two cycles. The connecting endpoints on the cyplane graph with a hard edges set Er , a super-portal set Ps and a portal face set F . G is embedded in a way such cles are 3-edge connected, and we may safely contract that al l super-portals of Ps wil l be on the border of the them to a cut-point. The bicycle edges surviving this contraction are committed to the solution by resetting portal faces if we replace the graph Gr consisting of P Gr as in the definition of type. Then the their costs to zero. and Er with Forbidden minor 2-ECSS (or 2-VCSS): Here number of external types of G with respect to Ps and F we have two difficulties: first, the usual separator O(|Ps |) . induced by (2-V C, P )-safe graphs is at most 2 theorems do not pro duce cycles (just trees). Also the Let (H, H ) be a pair stored in a no de of T where appropriate generalization of Lemma 2.2 may require H is the uncompressed (2-V C, P )-safe graph. Suppose a careful application of the Robertson-Seymour theory, H has portal set P and hard edge set Er . Let t be which appears difficult. For the special case of boundedan external type of H. We say H is compatible with genus graphs, both of these issues look more tractable. t if t(H)  t is 2-edge connected and the cutvertices of t(H)  t are blo ck-vertices of t(H) or t or super- References portals representing hard blo cks. As in the 2-ECSS algorithm, we define the subproblem instance to be for H and a compatible external type t finding a min-cost [1] I. Althofer, G. Das, D. P. Dobkin, D. Joseph, and ¨ J. Soares. On sparse spanners of weighted graphs. (2-V C, P )-safe subgraph of H which is compatible with Discrete Comput. Geom., 9(1):81­100, 1993. An early t. version app eared in SWAT'90, LNCS V. 447. By Lemma 5.2, the number of possible external [2] S. Arora. Polynomial time approximation schemes types is determined by the number of super-portals of for Euclidean traveling salesman and other geometric H. We now show the number of super-portals in each problems. Journal of the ACM, 45(5): 753­782, 1998. subgraph obtained from separator theorem is O(k ). By definition, the number of super-portals of H is at most 4 They may not b e simple cycles in H, but b e glued with a set the number of portals in it plus the number of separating cycles (hard cycles) and the cutvertices between these of other cycles from previous recursive calls.

503


[3] S. Arora, M. Grigni, D. Karger, P. Klein, and A. Woloszyn. A p olynomial time approximation scheme for weighted planar graph TSP. Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 33­41, 1998. [4] J. Cheriyan, A. Seb¨, and Z. Szigeti. An improved apo proximation algorithm for minimum size 2-edge connected spanning subgraphs. Proc. 6th IPCO, LNCS, 1412:126­136, 1998. [5] J. Cheriyan, S. Vempala, and A. Vetta. Approximation algorithms for minimum-cost k-vertex connected subgraphs. Proc. 34th ACM Symposium on Theory of Computing, pages 306­312, 2002. [6] B. Csaba, M. Karpinski, and P. Krysta. Approximability of dense sparse instances of minimum 2connectivity, TSP and path problems. Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 74­83, 2002. [7] A. Czuma j and A. Lingas. On approximability of the minimum cost spanning subgraph problem. Proc. 10th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 281­290, 1999. [8] A. Czuma j and A. Lingas. Fast approximation schemes for Euclidean minimum-cost multi-connectivity. Proc. 27th Annual Intl. Col loq. on Automata, Languages, and Programming (ICALP), LNCS, 1853:856­868, 2000. [9] R. Diestel. Graph theory. Springer-Verlag, New York, 2000. [10] C. G. Fernandes. A better approximation ratio for the minimum size k-edge-connected spanning subgraph problem. Journal of Algorithms, 28:105­124, 1988. [11] R. Jothi, B. Raghavachari, and S. Varadara jan. A 5/4-approximation algorithm for minimum 2-edgeconnectivity. Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 725­734, 2003. [12] M. Grigni, E. Koutsoupias, and C. Papadimitriou. An approximation scheme for planar graph TSP. Proc. 36th IEEE Symposium on Foundations of Computer Science, pages 640­645, 1995. [13] M. Grigni and P. Sissokho. Light spanners and approximate TSP in weighted graphs with forbidden minors. Proc 13th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 852­857, 2002. [14] R. Lipton and R. Tarjan. Applications of a planar separator theorem. SIAM Journal on Computing, 9(3):615­627, 1980. [15] G. L. Miller. Finding small simple cycle separators for 2-connected planar graphs. Journal of Computer and System Sciences, 32:265­279, 1986. [16] S. Vempala and A. Vetta. Factor 4/3-approximations for minimum 2-connected subgraphs. Proc. 3rd Workshop APPROX, LNCS, 1913:262­273, 2000.

A

Figures illustrating (2-V C, P )-safe graph

the

typ e

of

a

Figure 2: Type of a (2-V C, P )-safe graph used in the 2-VCSS Algorithm

hard edge portal

normal edge Jordan cut in the uncompressed graph

(a) A (2-V C, P )-safe graph H

super-portal

(b) Hr obtained after step 1

504


(c) H obtained after step 2

cutvertex portal node

block vertex

(f ) graph obtained after step 5a-5f

(d) H after step 3

(g) the type t(H ) of H

(e) H

o

btained after step 4

505