Minimum-Weight Cycles in 3-Separable Graphs Collette R. Coullard, 1 L. Leslie Gardner, 2 Donald K. Wagner 3 1 Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, Illinois 60208 2 School of Business, University of Indianapolis, 1400 E. Hanna Avenue, Indianapolis, Indiana 46227 3 Division of Mathematical, Computer, and Information Sciences, Office of Naval Research, Arlington, Virginia 22217 Accepted 20 December 1996 Abstract: This paper presents a polynomial-time algorithm for the minimum-weight-cycle problem on graphs that decompose via 3-separations into well-structured graphs. The problem is NP-hard in general. Graphs that decompose via 3-separations into well-structured graphs include Halin, outer-facial, deltawye, wye-delta, flat, and twirl–wheel graphs. For each of these classes of graphs, given the decomposition, the algorithm runs in linear time. q 1997 John Wiley & Sons, Inc. Networks 29: 151–160, 1997 1. INTRODUCTION Many graph-optimization problems that are NP-hard in general can be solved in polynomial time when restricted to classes of well-structured graphs. For instance, the traveling-salesman problem (TSP) admits a polynomial-time algorithm on Halin graphs [4] and, more generally, on outer-facial graphs [12, 13]. These algorithms use in a critical way the fact that Halin and outer-facial graphs decompose via 3-separations into wheels. This paper examines this phenomenon more closely. The problem considered here is the minimum-weightcycle problem, which is a generalization of the TSP. An instance of the minimum-weight-cycle problem is given by a graph G Å (V, E) and a vector of real weights {w(e)É e √ E}; the problem is to find a cycle of minimum Correspondence to: D. K. Wagner; e-mail: wagnerd@onrhq.onr. navy.mil weight. (Here, a cycle has no repeated vertices and its weight is the sum of the weights of its edges.) The TSP reduces to the minimum-weight-cycle problem by subtracting a large positive constant from each edge weight. In solving the minimum-weight-cycle problem, it clearly suffices to assume that G is 2-connected. It is also not hard to see that the problem can be reduced in linear time to the case where G is 3-connected using the decomposition algorithm of Hopcroft and Tarjan [14]. This paper gives a unified approach for solving the minimum-weight-cycle problem on several classes of 3connected graphs. The essential property that these classes have in common is that their members can be decomposed via 3-separations into well-structured graphs. For example, consider a Halin graph G Å (V, E). Then, it is well known that if G is not a wheel then G has a 3-edge cut such that shrinking one shore of the cut to a vertex yields a wheel W and shrinking the other yields a smaller Halin graph H. Applying this decomposition recursively to H yields a decomposition of G into a set q 1997 John Wiley & Sons, Inc. CCC 0028-3045/97/030151-10 151 0757 / 8u0f$$0757 03-17-97 20:44:01 netwa W: Networks 0757 152 COULLARD, GARDNER, AND WAGNER of wheels. Roughly, the present algorithm for solving the minimum-weight-cycle problem on G proceeds by first solving the minimum-weight-cycle problem on W. Then, this information is encoded on H in such a way that solving the problem on H also solves it on G. Thus, solving the problem on G is reduced to solving a sequence of problems on the set of wheels that make up its decomposition. This rest of this paper consists of five major sections: Section 2 describes the graph-theoretic preliminaries. Section 3 gives a preview of the algorithm. Section 4 contains the algorithm; Section 5, its complexity analysis; and Section 6, its proof of correctness. Undefined graph-theoretic terminology and notation is consistent with Bondy and Murty [2]. 2. DECOMPOSITION OF 3-CONNECTED GRAPHS Let G Å (V, E) be a connected graph and F ⊆ E. The set V (G[F]) > V (G[E 0 F]) is the set of vertices of attachment of G[F] and is denoted A(G, F). (Here, G[F] denotes the subgraph of G induced by F.) Note that A(G, F) Å A(G, E 0 F). For a positive integer k, a k-separation of G is defined to be a partition {E1 , E2 } of E such that É E1É ¢ k ° É E2É and É A(G, E1 )É Å k. A cyclic kseparation is a k-separation such that both E1 and E2 contain a cycle. For a positive integer n, G is (cyclically) nconnected if the graph G has no (cyclic) k-separation for k õ n. The graph G is minimally n-connected if it is nconnected, and for every e √ E, G "e has an (n 0 1)separation. Let G Å (V, E) be a 3-connected graph having a cyclic 3-separation {E1 , E2 }. Let A(G, E1 ) Å {x, y, z}, and let {e, f, g, t} be a set disjoint from V < E. Consider the following 3-step procedure: First, add e, f, g, and t to G[E1 ] and G[E2 ] so that t is a vertex and is adjacent precisely to x, y, and z via edges e, f, and g, respectively. Second, contract those edges in {e, f, g} that are incident to a degree-two vertex with the convention that new vertex that results retains the name t. Finally, if any edges of {e, f, g} were contracted, then a renaming procedure is carried out. If g (say) was contracted in the graph obtained from G[E1 ], then the edge g in the graph obtained from G[E2 ] is renamed to q, where q is the unique edge of E1 that is incident to z in G[E1 ]. The resulting set of graphs {G1 , G2 } is a simple decomposition of G; see Figure 1. The vertex t is the marker vertex associated with the simple decomposition, and the edges of the set {e, f, g} incident to t in G1 and G2 are marker edges. Note that both G1 and G2 are 3-connected. A decomposition D of G is defined inductively as either {G} or the set obtained from a decomposition D * of G by replacing exactly one member H of D * by the members 0757 / 8u0f$$0757 03-17-97 20:44:01 netwa Fig. 1. of a simple decomposition of H. In the latter case, D * is a refinement of D. A decomposition D is minimal with respect to some property P if D satisfies P but no refinement of D satisfies P. Two decompositions of G are equivalent if they differ only in the names used for the marker edges and vertices. A decomposition D of G is unique with respect to some property P if D satisfies P and any other decomposition of D that satisfies P is equivalent to D. A wheel is a graph on n / 1 vertices of which n induce a cycle and the remaining vertex is joined to each vertex of the cycle by a single edge. A twirl is a complete bipartite graph K3,n with n ¢ 3. A twirl–wheel graph is a 3connected graph that has a decomposition every member of which is a wheel or a twirl. One motivation for the consideration of twirl–wheel graphs is from the decomposition theory for minimally 3-connected graphs developed in Coullard et al. [6]; it was shown that twirls and wheels are two of the three building blocks for the class of minimally 3-connected graphs. Theorem 2.1 [6]. Every minimally 3-connected graph has a unique minimal decomposition with respect to the property that every member is either cyclically 4-conj nected, a twirl, or a wheel. Gardner [10] showed that the minimum-weight-cycle problem is NP-hard for the class of minimally 3-connected, cyclically 4-connected graphs. Thus, in looking for a class of minimally 3-connected graphs that admits a polynomial-time algorithm, it is reasonable to consider twirl–wheel graphs. Minimally, 3-connected twirl–wheel graphs include Halin graphs, which were introduced by Halin [11]. A graph is a Halin graph if it is a 3-connected, planar graph that has an embedding in the plane in which the outer face has an edge in common with every other face. Many optimization problems can be solved efficiently on Halin graphs; see, e.g., Syslo and Proskurowski [17] and Coullard and Pulleyblank [5]. As noted in the Introduction, Halin graphs have a decomposition, every member of which is a wheel. Indeed, the unique decomposition of a W: Networks 0757 MINIMUM WEIGHT CYCLES IN 3-SEPARABLE GRAPHS Halin graph given by Theorem 2.1 consists entirely of wheels. Outer-facial graphs generalize Halin graphs. A graph is outer-facial if it is 3-connected and planar and has an embedding in the plane in which the outer face has a vertex in common with every other face. Outer-facial graphs are not necessarily minimally 3-connected, and so Theorem 2.1 does not apply. But Hartvigsen and Pulleyblank [12] showed that every outer-facial graph can be obtained from a Halin graph by contracting some of the edges of the cycle that define the outer face. Consequently, it is easily shown that every outer-facial has a decomposition, every member of which is a wheel. Outer-facial graphs are not the only 3-connected graphs that decompose into wheels. Another such class consists of the so-called delta-wye graphs. A 2-connected graph is a delta-wye graph if it is reducible to a single edge by a sequence of series, parallel, and delta-wye reductions; a series reduction is the contracting of an edge incident to a degree-two vertex, a parallel reduction is the deleting of an edge that is in a 2-cycle (i.e., a cycle with exactly two edges), and a delta-wye reduction is first the deleting of the edges of a 3-cycle and then adding one new vertex and three new edges such that the new edges join the new vertex to each of the vertices of the 3-cycle. del Greco and Gardner [7] showed that a 3connected graph having at least four vertices is a deltawye graph if and only if it has a decomposition, every member of which is a wheel. Thus, 3-connected deltawye graphs include outer-facial and thus Halin graphs. Another class of delta-wye graphs was studied by Chopra and Johnson [3]. They defined flat graphs as those planar graphs that have no cube or the planar dual of a cube as a minor. (A cube is the planar graph that consists of two vertex-disjoint 4-cycles plus four additional edges, no two of which are adjacent and each joining the two 4-cycles. The cube is an example of a cyclically 4-connected graph. A graph H is a minor of a graph G if H can be obtained from G by a sequence of edge deletions and contractions.) Using the ‘‘forbidden-minor’’ characterization of deltawye graphs given in El-Mallah and Colbourn [8], it is easily shown that flat graphs are delta-wye graphs. A class of graphs related to delta-wye graphs are wyedelta graphs, which are also known as partial 3-trees (see [1]) and graphs of tree-width 3 (see [15]). A graph is a wye-delta graph if it can be reduced to a single edge by series, parallel, and wye-delta reductions, where a wyedelta reduction is just the inverse of a delta-wye reduction, i.e., first delete a degree-three vertex and then add three new edges that form a 3-cycle on its neighbors. A 3-connected wye-delta graph is not necessarily a twirl– wheel graph; the cube provides a counterexample. Indeed, del Greco and Gardner [7] showed that every 3-connected wye-delta graph has a decomposition, every member of which is a twirl, a wheel, or a cube. Note this does not 0757 / 8u0f$$0757 03-17-97 20:44:01 netwa 153 imply that every 3-connected twirl–wheel graph is a wyedelta graph. The graph in Figure 2 is a minimally 3connected twirl–wheel graph that is not a wye-delta graph. One might be tempted to consider the common generalization of delta-wye and wye-delta graphs that arises by allowing series, parallel, delta-wye, and wye-delta reductions. The class of graphs that are reducible in this sense includes all planar graphs; this is a result of Epifanov [9] (see also Truemper [18]). The minimum-weightcycle problem, however, is NP-hard on planar graphs. 3. A PREVIEW OF THE ALGORITHM To facilitate the description of the algorithm, it is useful to consider a simple scenario. Consider an instance of the minimum-weight-cycle problem on a 3-connected twirl– wheel graph G Å (V, E). Suppose that G has a simple decomposition {J, K} such that K is a wheel. Suppose further that J and K have exactly one marker edge in common, say e. Let t be the associated marker vertex, and let {e, f, g} be the set of edges incident to t in J (and thus in K). Let x, y, and z be the respective other ends of e, f, and g in J. Thus, e is also incident to x in K. Observe that any cycle of G is contained in E(J " t), is contained in E(K " t), or has a nonempty intersection with both E(J " t) and E(K " t). (For notational convenience, cycles are equated with their edge sets.) If a cycle C has a nonempty intersection with both E(J " t) and E(K " t), then C > E(J " t) [respectively, C > E(K " t)] together with exactly two of the edges incident to t form a cycle CJ (respectively, CK ) of J (respectively, K). Moreover, CJ > {e, f, g} Å CK > {e, f, g}. Now, assume that C is a minimum-weight cycle of G which happens to meet both E(J " t) and E(K " t). Assign a weight of zero to each edge of K that is incident to t, and allow the remaining edges of K to keep their original weight. Observe that among all cycles C * of K that satisfy C * > {e, f, g} Å CJ > {e, f, g}, CK is either a minimumweight cycle of K or a minimum-weight cycle of K that does not contain x. Fig. 2. W: Networks 0757 154 COULLARD, GARDNER, AND WAGNER Based on the above observations, a procedure for solving the minimum-weight-cycle problem on G might go as follows: In K, find five cycles: a cycle Cf g that is a minimum-weight cycle among all cycles that contain f and g, a cycle C fmg (the ‘‘m’’ stands for miss) that is a minimum-weight cycle among all cycles that contain f and g and do not contain (i.e., misses) x, a cycle Cef that is a minimum-weight cycle among all cycles that contain e and f, a cycle Ceg that is a minimum-weight cycle among all cycles that contain e and g, and a cycle CM that is a minimum-weight cycle among all cycles that have an empty intersection with {e, f, g}. Finding these five cycles can be done efficiently since K has only O(ÉV ( K)É2 ) cycles. The weights of the first four of these cycles are now ‘‘loaded’’ onto the vertex t of J. The minimumweight-cycle problem on G is now reduced to the more general ‘‘minimum-load-cycle’’ problem on J, where the load of a cycle is the sum of its edge weights plus the appropriate load from vertex t. To be more specific, now let CJ be an arbitrary cycle of J. If CJ does not contain t, then define its load to be equal to its weight [denoted w(CJ )]; if CJ contains t, then define its load to be w(CJ ) / l(t, u), where tu is the unique edge of J incident to t not in CJ , and computing the loads of the various cycles in the nice member. This is because, at a general iteration, this member might contain several marker vertices. Given a particular cycle and a marker vertex on the cycle, there are at most two possible choices for which load to use for the vertex in computing the load of the cycle [e.g., in the above example, if CJ contains f and g, then the two choices are w(Cf g ) and w(C fmg )]. Clearly, if the choice of load for this marker vertex can be made independently of the choices for the other marker vertices in the cycle, then the choice is easy—choose the one that represents the cheapest feasible extension of the cycle [e.g., w(Cf g ) if CJ does not contain x and w(C fmg ) otherwise]. As it turns out, the choice of load for a marker vertex is not necessarily independent of the cycle’s other marker vertices. As will be seen, however, it is sufficient to consider pairs of marker vertices in the cycle. Specifically, if two marker vertices of the cycle are joined by a marker edge or are both joined to a third vertex not on the cycle by marker edges, then choosing the ‘‘hit’’ load [i.e., w(Cf g )] for one of the vertices forces the choice of the ‘‘miss’’ load [i.e., w(C fmg )] for the other. This idea is captured precisely in the next section with the notion of a hit set. l(t, u) 4. THE MINIMUM-LOAD-CYCLE PROBLEM Å w(Cf g ) if u Å x and CJ does not contain u, w(C fmg ) if u Å x and CJ contains u, w(Ceg ) if u Å y, and w(Cef ) if u Å z. Basically, l(t, u) is acting as a surrogate in CJ ; it represents the cheapest way of feasibly extending CJ to a cycle of G. (By ‘‘feasibly,’’ it is meant that the extension of CJ must be a cycle of G. In the above example, if CJ contains f, g, and x, and Cf g contains x, then extending CJ using Cf g is not a cycle of G. On the other hand, extending CJ using C fmg does yield a cycle of G.) Now, the weight of a minimum-weight cycle of G is equal to either the load of a minimum-load cycle in J or the previously computed w(CM ), whichever is smaller. Given this quantity, it is straightforward to backtrack and actually find a minimum-weight cycle of G. The algorithm now proceeds recursively on J. At a general iteration, the algorithm finds a simple decomposition of the current graph such that one member of the decomposition is ‘‘nice’’ (e.g., a twirl, a wheel, or a cube). A small number of minimum-load-cycle problems are solved on this nice member, and the resulting loads are assigned to the associated marker vertex in the other member. One of the main difficulties in the above process is in 0757 / 8u0f$$0757 03-17-97 20:44:01 netwa A loaded graph consists of a graph G Å (V, E), a set T ⊆ V of degree-three vertices, a set M ⊆ E such that each edge of M is incident to a vertex of T, a set L of load functions, and weight vector w Å {w(e)É e √ E}. By an abuse of notation, G is used to denote the graph G Å (V, E) as well as the loaded graph G Å (V, E, T, M, L, w). A load function is a real-valued function defined on ordered pairs of adjacent vertices, say (t, u), such that t √ T. (The vertex u might also be in T.) The load function is associated with t. The set L consists of two load functions for each pair (t, u), where t √ T; these are denoted l(t, u) and l m (t, u). Each such pair is assumed to satisfy l(t, u) ° l m (t, u). In the context of the previous section, G is a member of some decomposition; T, the set of its marker vertices; M, the set of its marker edges; L, the set of its vertex loads; and w, the vector of its edge weights. [The load notation here is a refinement of that in the previous section; here l(t, u) represents the ‘‘hit’’ load of t and l m (t, u ) represents the ‘‘miss’’ load, i.e., in the example of the previous section, if CJ contains f and g, then l(t, u) Å w(Cf g ) and l m (t, u) Å w(C fmg ).] The next definitions are aimed at defining the notion of a hit set of a cycle discussed previously. Let C be a cycle of a loaded graph G Å (V, E, T, M, L, w). A vertex x √ T > V (C) is critical if there exists an edge of M 0 C that joins x to a vertex in V (C) 0 T. A pair of W: Networks 0757 MINIMUM WEIGHT CYCLES IN 3-SEPARABLE GRAPHS 155 vertices {x, y} ⊆ T > V (C) are incompatible if either they are joined by an edge in M 0 C or both x and y are joined to a third vertex z √ T < V (C) by edges in M. A set H ⊆ T > V (C) is a hit set of C if H does not contain any critical vertices of C and H contains at most one vertex from any incompatible pair of C. Given a cycle C of a loaded graph G Å (V, E, T, M, L, w) and a hit set H of C, the load of C with respect to H, denoted l(C, H), is defined to be LK , wK ): set TK :Å (T > VK ) < {t} and MK :Å (M > EK ) < M; for each edge e √ EK , set wK (e) :Å 0 if e is incident to t and wK (e) :Å w(e) otherwise; for each s£ √ EK with s √ TK , set l(C, H) and :Å ∑ w(e) / e√C ∑ l(t, u) / t√H tu √ E0C ∑ lK (s, £ ) :Å l(s, J(s)) if £ Å t, and l(s, £ ) otherwise l (t, u). t √ (T>V (C ) )0H tu √ E0C l Km (s, £ ) :Å ALGORITHM MLCP Input: A loaded 3-connected graph G Å (V, E, T, M, L, w) that has a decomposition, the members of which belong to a nice class. if s Å t l m (s, J(s)) if £ Å t, and l (s, £ ) STEP 3. Create the loaded graph J Å (VJ , EJ , TJ , MJ , LJ , wJ ): set TJ :Å (T > VJ ) < {t} and MJ :Å (M > EJ ) < M; for each edge e √ EJ , set wJ (e) :Å 0 if e √ M and wJ (e) :Å w(e) otherwise; for each su √ EK with s √ TK , set lJ (s, u) :Å lK (CK (u ) ) if s Å t, l(s, K(s)) if u Å t, and l(s, u) otherwise and l Jm (s, u) :Å lK (C Km (u ) , H Km (u ) ) if s Å t, l m (s, K(s)) if u Å t, and l (s, u) STEP 2. Create the loaded graph K Å (VK , EK , TK , MK , netwa otherwise; set LK :Å {l(s, £ )És£ √ EK , s √ TK } < {l m (s, £ )És£ √ EK , s √ TK }. For each neighbor £ of t in K, compute a cycle C£ that is a minimum-load cycle among all cycles of K that contain t, but do not contain t£ ; compute a cycle C £m that does not contain t£ , has a hit set H £m that contains t, and satisfies lK (C £m , H £m ) Å min{lK (C, H)Ét£ √ C, t √ H}; and compute a cycle CM that is a minimum-load cycle among all cycles of K that do not contain t. m STEP 1. If G belongs to a nice class, then compute and output a minimum-load cycle of G and stop. Otherwise, let {J, K} be a simple decomposition of G such that K belongs to a nice class and J has a decomposition, the members of which belong to a nice class. Let t be the associated marker vertex, and let M be the associated set of marker edges. 03-17-97 20:44:01 0 m Output: A minimum-load cycle of G. / 8u0f$$0757 if s Å t m The load of C, denoted l(C), is defined to be min{l(C, H)ÉH is a hit set of C}. The minimum-load-cycle problem is that of determining a minimum-load cycle of G. By taking M, T, and L to be empty, the minimumload-cycle problem reduces to the minimum-weight-cycle problem. Moreover, if the algorithm below for solving the minimum-load-cycle problem starts with M, T, and L empty, then throughout the course of the algorithm, M and T will be the sets of marker edges and marker vertices of the current graph and L will be the associated load functions. The algorithm is now described. Its complexity is given in Section 5 and its validity is established in Section 6. A couple of definitions are needed. A class of graphs will be called nice if the class admits a polynomial-time algorithm for the minimum-load-cycle problem. Now, let {J, K} be a simple decomposition of a 3-connected graph G Å (V, E), and let t be the associated marker vertex. Then, there exists a natural correspondence between the neighbors of t in J and those in K. Specifically, for each neighbor u of t in J, there exists a unique neighbor of t in K, denoted K(u), such that, in G, either u Å K(u) or uK(u) √ E; for a neighbor £ of t in K, J( £ ) is defined analogously. 0757 0 otherwise; set LJ :Å {lJ (s, u)Ésu √ EJ , s √ TJ } < {l Jm (s, u)Ésu √ EJ , s √ TJ }. STEP 4. Apply Algorithm MLCP to the loaded graph J; let CJ be the output and let HJ be a hit set of CJ such that lJ (CJ ) Å lJ (CJ , HJ ). If lK (CM ) ° lJ (CJ ), then output CM and stop. If CJ does not contain t, then output CJ and stop. If CJ contains t, then let tu √ EJ W: Networks 0757 156 COULLARD, GARDNER, AND WAGNER be the edge incident to t not in CJ ; output (CJ < CK (u ) ) 0 M if t √ HJ and (CJ < C Km (u ) ) 0 M if t √ HJ ; stop. j 5. COMPLEXITY OF ALGORITHM MLCP This section contains the derivation of the complexity of the algorithm. Specifically, it is first shown that given a decomposition of a 3-connected graph, the members of which belong to a nice class, the algorithm runs in polynomial time. Then, it is shown that for all the classes of graphs introduced in Section 2 the algorithm runs in O(ÉV É2 ) time. Moreover, if a decomposition is given, the time is reduced to O(ÉV É). The first result below bounds the number of members in any decomposition of a 3connected graph G Å (V, E). Let D be a decomposition of G. It is straightforward to show, using the fact that a marker vertex has degree 3, that a given marker vertex is in exactly two members of D. Moreover, the graph having vertex set D with two vertices being adjacent if and only if the two members share a marker vertex is a tree, called the decomposition tree of D. The decomposition tree ‘‘displays’’ several cyclic 3-separations of G as follows: Let {D1 , D2 } be the partition of D induced by deleting one particular edge of the decomposition tree, let E1 be the subset of edges of G that are contained in some member of D1 , and let E2 :Å E 0 E1 . Then, {E1 , E2 } is a cyclic 3-separation of G. (This follows from Lemma 3.3 of Coullard et al. [6].) Moreover, if {G1 , G2 } is the associated simple decomposition, then Di is a decomposition of Gi for i √ {1, 2}. (This follows from Theorem 3.8 of Coullard et al. [6].) A decomposition tree is a star if it has at most one vertex of degree greater than one. Lemma 5.1. If G Å (V, E) is a 3-connected graph, then any decomposition of G has at most max{1,2ÉEÉ 0 12} members. Proof. Let D be a decomposition of G. First, consider the case when the decomposition tree T of D is a star. Observe that any member of D that has degree one in T contains at least three edges from G such that each is in no other member of D. Consequently, the number of members of D is bounded above by É EÉ/3 / 1. If É EÉ/ 3 / 1 ¢ 2É EÉ 0 12, then É EÉ ° 7. The result now follows since any decomposition of a 3-connected graph with seven or fewer edges has exactly one member. Now, consider the case that T is not a star. Then, É EÉ ¢ 8. Choose an edge of T not incident to a degree-one vertex, and let {D1 , D2 } be the resulting partition of D. Then, Di is a decomposition of a graph Gi , for i √ {1, 2}, where {G1 , G2 } is a simple decomposition of G with É E(G1 )É, É E(G2 )É ° É EÉ 0 1. By induction, É Di É 0757 / 8u0f$$0757 03-17-97 20:44:01 netwa ° max{1, 2É E(Gi )É 0 12} for i √ {1, 2}. Observe that É E(G1 )É / É E(G2 )É ° É EÉ / 6. Using the fact that É DÉ Å É D1É / É D2É, the result now follows. j In the case that G is a wye-delta or planar (which includes delta-wye) graph, the above lemma implies an O(ÉV É) bound on the number of members, since, in these cases, it is well known that É EÉ Å O(ÉV É). Also, if G is minimally 3-connected, then it is straightforward to prove by induction that É EÉ Å O(ÉV É). Observe that the main work in the algorithm is in finding the simple decomposition in Step 1 and in computing the minimum-load cycles in Steps 1 and 2. Consider the latter. Each minimum-load-cycle computation in Step 2 is a variation of the ‘‘pure’’ minimum-load-cycle problem on K. But it is not too hard to see that each of these variations can be reduced to a pure minimum-load-cycle problem on K by adjusting the weights on the edges incident to t and the load function lK (t, £ ). For example, to compute the cycle C £m , make the weight of edge t£ relatively large and the load function lK (t, £ ) relatively small. Since K is assumed to belong to a nice class, these computations can be done in polynomial time. Now, consider the problem of finding the simple decomposition in Step 1. By assumption, the input graph G has a decomposition D, the members of which belong to a nice class. Given D, the required simple decomposition can be found as follows: Let K be a member of D that has degree one in the decomposition tree. Then, {D 0 {K}, K} is a partition of D. The corresponding simple decomposition is {J, K} for an appropriate J. Note, for the purposes of the algorithm, it is not necessary to actually compute J; it suffices to have a decomposition of J, the members of which belong to a nice class. Evidently, such a decomposition is given by D 0 {K}. Consequently, the following has been proved: Theorem 5.2. Given a decomposition of G, the members of which belong to a nice class, Algorithm MLCP runs j in polynomial time. The remainder of the section is devoted to determining a time bound for the algorithm if the G is one of the graphs discussed in Section 2, namely, delta-wye, wyedelta, and minimally 3-connected twirl–wheel graphs. In this context, again consider the problem of finding the simple decomposition of G required in Step 1. The following lemma solves the problem; for wye-delta graphs, the lemma is essentially a combination of results from Matoušek and Thomas [15] and del Greco and Gardner [7]. Lemma 5.3. If is a 3-connected delta-wye graph, a 3- W: Networks 0757 MINIMUM WEIGHT CYCLES IN 3-SEPARABLE GRAPHS connected wye-delta graph, or a minimally 3-connected twirl–wheel graph, and G has more than eight vertices, then G has a simple decomposition {J, K} such that J is the same type of graph as G (i.e., delta-wye, wye-delta, or minimally 3-connected twirl–wheel) with ÉE(J) É õ ÉEÉ and ÉV ( K) É ° 8. Moreover, this simple decomposition can be found in O(ÉVÉ) time. Proof. The first statement of the lemma is proved first; then the complexity is determined. Suppose that G is a delta-wye graph. Then, Politof [16] (also El-Mallah and Colbourn [8]) showed that G has a cyclic 3-separation {E1 , E2 } such that G[E2 ] is either the graph in Figures 3(b) or (d) with A(G, E2 ) Å {x, y, z}. Letting {J, K} be the corresponding simple decomposition, then, evidently, ÉV ( K)É ° 8. Moreover, J can be seen to be a minor of K with É E(J)É õ É EÉ, and since delta-wye graphs are known to be closed under minors (see, e.g., El-Mallah and Colbourn [8]), J is also a 3-connected delta-wye graph. The argument in the case that G is a wye-delta graph is exactly the same with the exception that G[E2 ] is one of the graphs in Figures 3(a) – (c) with A(G, E2 ) Å {x, y, z}; in this case, the existence of the appropriate cyclic 3-separation {E1 , E2 } is a result of Arnborg and Proskurowski [1]. Now, suppose that G is a minimally 3-connected twirl– wheel graph. The first step is to show that G has a cyclic 3-separation {E1 , E2 } such that G[E2 ] is one of the graphs in Figures 3(a) or (e) with A(G, E2 ) Å {x, y, z}. By definition, G has a decomposition, every member of which is a twirl or wheel. Since a twirl has a decomposition, every member of which is a K3,3 , and a wheel has a decomposition, every member of which is a K4 , G has a decomposition D, every member of which is either a K3,3 or a K4 . Let K be a member of D that has degree one in the decomposition tree, and let {F1 , F2 } be the cyclic 3-separation of G corresponding to the partition {D 0 {K}, K} of D. Since K is a K3,3 or a K4 , G has a cyclic 3-separation {F *1 , F *2 }, where F *2 ⊆ F2 , such that G[F *2 ] is one of the graphs in Figures 3(a), (b), or (e) with A(G, F *2 ) Å {x, y, z}. If G[F *2 ] is the graph in Figure 3(b), then by Theorem 10.54 of Tutte [19], x (say) has degree three in G. (Theorem 10.54 of Tutte [19] says, among other things, that a 3-cycle in a minimally 3- connected graph has at least two vertices of degree three.) This implies that G has a cyclic 3-separation {E1 , E2 } such that G[E2 ] is the graph of Figure 3(a) or (e). The second step is to show that if {J, K} is the simple decomposition associated with the cyclic 3-separation {E1 , E2 } of G then J is a minimally 3-connected twirl– wheel graph with É E(J)É õ É EÉ. The facts that J is minimally 3-connected and É E(J)É õ É EÉ follow directly from Lemmas 2.5 and 2.6, respectively, of Coullard et al. [6]. To see that J is a twirl–wheel graph, suppose otherwise. By Theorem 2.1, J has a decomposition D, every member of which is either cyclically 4-connected, a twirl, or a wheel. Since J is not a twirl–wheel graph, D has a member, say H, that not a twirl or a wheel. From Lemma 2.6 of Coullard et al. [6], it follows that H is a minor of G. From the definition of a simple decomposition and the fact that H is cyclically 4-connected, any decomposition of G must have a member that has a graph isomorphic to H as a minor. In particular, by considering the decomposition of G, every member of which is a K3,3 or a K4 , it follows that H is, in fact, a K3,3 or a K4 , a contradiction. Now, consider the time complexity of finding the desired simple decomposition. At the heart of finding this simple decomposition is finding a subgraph of G that is one of the graphs depicted in Figure 3 with the indicated vertices of attachment. If G has as a subgraph the graph of Figure 3(a), then such a subgraph can be found in O(ÉV É) time using the algorithm for this purpose given in Matous̆ek and Thomas [15]. If G has as a subgraph one of the graphs of Figures 3(c) – (e), then such a subgraph can be found in time O(ÉV É) by first finding all of the degree-three and degree-four vertices of G and then examining each such vertex to see whether it is in one of the prescribed subgraphs. Note that examining a given vertex requires constant time since, in each of the prescribed subgraphs, each edge is incident to either the given vertex or a neighbor of the given vertex that also has degree three or four. Finally, consider the graph of Figure 3(b). To search for this graph as a subgraph of G, it is assumed that G does not have any of the graphs of Figures 3(a), (c), (d), or (e) as subgraphs. Observe, in this case, that G is a delta-wye or a wye-delta graph. Under the above Fig. 3. 0757 / 8u0f$$0757 03-17-97 20:44:01 netwa 157 W: Networks 0757 158 COULLARD, GARDNER, AND WAGNER assumption, it is claimed that G has as a subgraph the graph of Figure 3(b) with vertex x (say) having at most four neighbors other than y. This claim is proved by induction on the number of edges. Since G does not have any of the graphs of Figures 3(a), (c), or (d) as subgraphs, by Politof [16] or Arnborg and Proskurowski [1], it must have the graph of Figure 3(b) as a subgraph with the indicated vertices of attachment. In G, delete the edge joining vertices x and y, and call the resulting graph G *. Note that G * is still a 3-connected delta-wye or a wyedelta graph and, therefore, has one of the graphs of Figures 3(a) – (d) as a subgraph. If G * has any of the graphs of Figure 3(a), (c), (d), or (e) as a subgraph (call this subgraph H), then the claim follows since, in this case, one of the vertices x or y [of the Fig. 3(b) subgraph] must be a vertex of H that is not a vertex of attachment of H. On the other hand, if G * does not have any of the graphs of Figure 3(a), (c), (d), or (e) as a subgraph, then the claim follows by induction. Given the claim, a subgraph as in Figure 3(b) can be found, if one exists, by examining all degree-three vertices of G and for each one determining if it has two adjacent neighbors. Because of the claim, this determination can be done in constant time. j O(ÉV É) for some or all of these classes of graphs. (iii) It is worth a word of explanation as to why Theorem 5.4 is restricted to minimally 3-connected twirl–wheel graphs as opposed to 3-connected twirl–wheel graphs in general. The problem is that, unlike minimally 3-connected twirl– wheel graphs, not every decomposition of a 3-connected twirl–wheel graph consists of only twirls and wheels. As an example consider the 3-connected graph in Figure 4. It is a twirl–wheel graph since it has a decomposition that consists of four K4’s. But it also has a decomposition that consists of a K4 and a cube. As observed in (ii), if one is given a decomposition of 3-connected twirl–wheel graph that consists of just K4’s and K3,3’s, then the minimum-weight-cycle problem can be solved in linear time. (v) Wye-delta graphs, delta-wye graphs, and minimally 3-connected twirl–wheel graphs all can be recognized in polynomial time. Moreover, it is not hard to modify that algorithm so it accepts any 3-connected graph as input and as output either produces a minimum-weight cycle or the conclusion that the input graph is not one of the prescribed types. Lemma 5.3 implies that solving the required minimumload-cycle problems on K in Step 2 can be done in constant time. Thus, Theorem 5.1 and Lemma 5.3 imply the following result: This section contains the proof of correctness of the algorithm. Theorem 5.4. If G is a 3-connected delta-wye graph, a 3connected wye-delta graph, or a minimally 3-connected twirl–wheel graph, then Algorithm MLCP runs in O( ÉVÉ2 ) time. j Proof. The proof is by induction on the number of recursive calls to Algorithm MLCP; if the number is zero, which happens only if the original input graph G belongs to a nice class, then, clearly, the algorithm outputs a correct answer. Thus, assume that the algorithm makes at least one recursive call. Let J denote the input graph for the first recursive call to the algorithm. (For convenience, the notation established in the statement of the algorithm is used here.) By induction, CJ is a minimum-load cycle of the loaded graph J. Let C denote the output from Step 4 in the case that lK (CM ) ú lJ (CJ ), i.e., C is equal to CJ , (CJ < CK (u ) ) 0 M, or (CJ < C Km (u ) ) 0 M. It is straightforward to verify that C is indeed a cycle of G. The next step is to show that C has the same load in G as CJ does in J. Some remarks are in order: (i) It seems likely that by doing things a bit more carefully the bound in Theorem 5.4 can be improved to O(ÉV É). Specifically, from the above analysis, it is the computation of the simple decomposition in Step 1 that requires the most work throughout the course of the algorithm. The above analysis does not assume that any information (e.g., the list of degree-three and degree-four vertices) is passed on from one execution of Step 1 to the next. Clearly, by doing so, savings can be achieved. (ii) For the classes of graphs given in Lemma 5.3, a variation of Algorithm MLCP is to first compute a decomposition of the input graph into graphs having a small number of vertices (using the algorithm given in the lemma, or, perhaps, a different algorithm) and then generate the simple decompositions required in Step 1 by ‘‘pulling off ’’ degree-one vertices of the decomposition tree. The complexity of this approach is O(ÉV É) plus the time required to find the decomposition. By Lemma 5.3, the time required to find the decomposition is O(ÉV É2 ), but perhaps it can be improved to 0757 / 8u0f$$0757 03-17-97 20:44:01 netwa 6. CORRECTNESS OF ALGORITHM MLCP Theorem 6.1. Algorithm MLCP is correct. Fig. 4. W: Networks 0757 MINIMUM WEIGHT CYCLES IN 3-SEPARABLE GRAPHS Claim 1. There exists a hit set H of C in G such that l(C, H) Å lJ (CJ ). Proof of Claim 1. CASE (a). CJ does not contain t. In this case, it is shown that H :Å HJ satisfies the claim. Since the cycle C( ÅCJ ) does not contain t, its vertex set is the same in G as in J. Moreover, any edge joining two vertices of C in G also does so in J. Similarly, if vertices {x, y} ⊆ T > V (C) are both joined via edges m and n to a third vertex z in G, then, since x and y have degree three in G, x and y are joined via edges m and n to z in J. Therefore, a critical vertex of C in G is also a critical vertex of C in J and an incompatible pair of C in G is an incompatible pair of C in J. It follows that H is a hit set of C in G. Finally, the definitions of the load functions for G and J in Step 3 directly imply that l(C, H) Å lJ (CJ ). CASE (b). CJ contains t. Let tu be the edge of J incident to t not in CJ , and let £ :Å K(u). Let H£ be a hit set of C£ such that lK (C£ , H£ ) Å lK (C£ ). Define CK :Å C£ if t √ HJ and CK :Å C £m if t √ / HJ . Define HK :Å H£ / HJ (where H £m is defined if t √ HJ and HK :Å H £m if t √ in Step 2). Define H :Å (HJ < HK ) 0 {t}. It is now shown that H satisfies the claim. Let x be a critical vertex of C in G. Then, x √ T > V (C) and there exists an edge m √ M 0 C that joins x to a vertex y √ V (C) 0 T. Since x √ T, it has / VJ > VK . Supdegree three in G, and, therefore, x √ pose that x √ VK ; the argument for x √ VJ is similar. Since x √ VK 0 VJ , it follows that x √ TK > V (CK ). If y √ V (CK ), then x is a critical vertex of CK in K, implying that x √ / HK , and, therefore, x √ H, as required. Thus, assume that y √ / V (CK ). Then, it must be that either u Å £ Å y, or u Å y and £ Å x. In either case, observe that t is critical (with respect to CJ ) in J since it is joined to y by an edge of MJ and y √ V (CJ ) 0 TJ [since y √ V (C) 0 T]. This implies that HK :Å H £m , and it follows from Step 2 that t √ HK . Now, if u Å £ Å y, then x and t are incompatible in K (with respect to CK ) since they are both joined to y by edges of MK . Thus, x √ / HK , which implies / H, as required. On the other hand, if £ Å x, that x √ then, again, x and t are incompatible in K since they are joined by the edge m, which is in MK . So, again, / H, as required. x √ Now, consider an incompatible pair of vertices, x and y, of C in G. First, suppose that x and y are joined by an edge m √ M 0 C. By definition, both x and y have degree three in G, and, therefore, neither is in VJ > VK . First, suppose that x √ VJ and y √ VK . Then, x Å u and y Å £. It follows that x and t are incompatible (with respect to CJ ) in J, and y and t are incompatible 0757 / 8u0f$$0757 03-17-97 20:44:01 netwa 159 (with respect to CK ) in K. Observing that either t √ HJ or t √ HK , it follows that at most one of x and y is in H, as required. Now, suppose that {x, y} ⊆ VK ; the argument for {x, y} ⊆ VJ is similar. Then, m √ MK , which implies that x and y are incompatible (with respect to CK ) in K. Thus, at most one of x and y is in HK and, therefore, H. Now, suppose that x and y are joined, in G, to a third vertex z √ T < V (C) via edges m √ M and n √ M, respectively. By definition, both x and y have degree three in G, and, therefore, neither is in VJ > VK . First, suppose that x √ VJ and y √ VK . Then, z Å u Å £, x Å u, or y Å £. In each case, it is easily checked that x and t are incompatible (with respect to CJ ) in J, and y and t are incompatible (with respect to CK ) in K. Observing that either t √ HJ or t √ HK , it follows that at most one of x and y is in H, as required. Finally, suppose that {x, y} ⊆ VK ; the argument for {x, y} ⊆ VJ is similar. Then, {m, n} ⊆ EK and z √ VK . It follows that x and y are incompatible (with respect to CK ) in K. Thus, at most, one of x and y is in HK and, therefore, H. Finally, l(C, H) Å lJ (CJ ) / lK (CK , HK ) 0 lJ (t, u) if t √ HJ and l(C, H) Å lJ (CJ ) / lK (CK , HK ) 0 l Jm (t, u) if t √ HJ . From Steps 2 and 3, the last two terms sum to zero in both equations, and so l(C, H) Å lJ (CJ ), as required. End of Claim 1. The next goal is to show that either C or CM is a minimum-load cycle of G. Let C * be an arbitrary cycle of G that meets EJ , and let H * be a hit set of C * such that l(C * ) Å l(C *, H * ). Then, Claims 1 and 2 (below), together with the induction hypothesis that CJ is a minimum-load cycle of J, imply that l(C) ° l(C * ). Claim 2. There exists a cycle C 9 of J and a hit set H 9 of C 9 in J such that lJ (C 9, H 9 ) ° l(C * ). Proof of Claim 2. CASE (a). C * is a cycle of J. Define C 9 :Å C * and H 9 :Å H *. Note that C 9 does not contain t. Thus, TJ > V (C 9 ) Å T > V (C 9 ), from which it follows that H 9 ⊆ TJ > V (C 9 ). Since C 9 does not contain t, any edge joining two vertices of C 9 in J also does so in G. Similarly, if vertices {x, y} ⊆ TJ > V (C 9 ) are both joined via edges m and n to a third vertex z √ / TJ < V (C 9 ) in J, then x and y are both joined via edges m and n to z √ / T < V (C * ) in G. Therefore, a critical vertex of C 9 in J is also a critical vertex of C * in G, and an incompatible pair of C 9 in J is an incompatible pair of C * in G. It follows that H 9 is a hit set of C 9 in J. Finally, the definitions of the load functions for G and J in Step 3 directly imply that lJ (C 9, H 9 ) Å l(C * ). W: Networks 0757 160 COULLARD, GARDNER, AND WAGNER CASE (b). C * has nonempty intersection with both EJ and EK . Define C 9 to be the unique cycle of J that consists of C * > EJ together with two edges of J incident to t. Consider the set H * > V (C 9 ). Observe that t √ / H * > V (C 9 ) and H * > V (C 9 ) ⊆ TJ > V (C 9 ). Note that any edge joining two vertices of H * > V (C 9 ) in J also does so in G. Similarly, if vertices {x, y} ⊆ H * > V (C 9 ) are both joined via edges m and n to a third vertex z √ / TJ < V (C 9 ) in J, then x and y are joined via edges m and n to z √ / T < V (C * ) in G. Therefore, a critical vertex of C 9 in J is also a critical vertex of C * in G, and an incompatible pair of C 9 in J is an incompatible pair of C * in G. It follows that H * > V (C 9 ) is a hit set of C 9 in J. Now, if (H * > V (C 9 )) < {t} is also a hit set of C 9 in J, then set H 9 :Å (H * > V (C 9 )) < {t}; otherwise, set H 9 :Å H * > V (C 9 ). Define C - to be the unique cycle of K that consists of C * > EK together with two edges of K incident to t. Then, C * Å (C 9 < C - ) 0 M. Let tu be the unique edge of J incident to t not in C 9. Now, verifying that lJ (C 9, H 9 ) ° l(C * ) reduces to showing lJ (t, u) ° lK (C - ) if t √ H 9 and l Jm (t, u) ° lK (C - ) if t √ / H 9. By Steps 2 and 3, the first of these inequalities is true. Similarly, the second is true so long as C - has a hit set that contains t. So, it suffices to show that if t √ / H 9, then H - :Å (H * > V (C - )) < {t} is a hit set of C -. By an argument analogous to the one above that showed that H * > V (C 9 ) is a hit set of C 9 in J, H * > V (C - ) is a hit set of C - in K. Now, using the facts that H 9 and H * > V (C - ) are hit sets, but that (H * > V (C 9 )) < {t} is not, it is straightforward to verify that H - is a hit set of C - in J. End of Claim 2. Finally, let C * be an arbitrary cycle of G that has empty intersection with EJ , and let H * be a hit set of C * in G such that l(C *, H * ) Å l(C * ). Let HM be a hit set of CM in K such that lK (CM ) Å lK (CM , HM ). Then, C * is also a cycle of K that does not contain t. Analogous to Claim 2, Case (a), H * is a hit set of C * in K with lK (C *, H * ) Å l(C * ), and so lK (CM ) ° l(C * ). Analogous to Claim 1, Case (a), HM is a hit set of CM in G with l(CM , HM ) Å lK (CM ). Therefore, l(CM ) ° l(C * ). The theorem follows. j [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [10] [11] [12] [13] [14] [15] [16] [17] We thank Dave Hartvigsen for several helpful discussions. REFERENCES [1] 0757 [18] S. Arnborg and A. Proskurowski, Characterization and recognition of partial 3-trees. SIAM J. Alg. Discr. Methods 7 (1986) 305–314. / 8u0f$$0757 03-17-97 20:44:01 netwa [19] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications, North Holland, New York (1976). S. Chopra and E. L. Johnson, Octahedron and cube free planar graphs. Unpublished (1989). G. Cornuéjols, D. Naddef, and W. R. Pulleyblank, Halin graphs and the travelling salesman problem. Math. Program. 26 (1983) 287–294. C. R. Coullard and W. R. Pulleyblank, On cycle cones and polyhedra. Linear Alg. Appl. 114/15 (1989) 613– 640. C. R. Coullard, L. L. Gardner, and D. K. Wagner, Decomposition of 3-connected graphs. Combinatorica 13 (1993) 7–30. J. G. del Greco and L. L. Gardner, A note on D 0 Y and Y 0 D graphs. Submitted. E. S. El-Mallah and C. J. Colbourn, On two dual classes of planar graphs. Discr. Math. 80 (1990) 21–40. G. V. Epifanov, Reduction of a plane graph to an edge by a star-triangle transformation. Doklady 166 (1966) 13–17. L. L. Gardner, Studies in 3-connected graphs: a decomposition theory and a decomposition-based optimization algorithm. PhD. Thesis, Purdue University, West Lafayette, IN (1989). R. Halin, Studies on minimally n-connected graphs. Combinatorial Mathematics and Its Applications (D. J. A. Welsh, Ed.). Academic Press, New York (1971) 129–136. D. Hartvigsen and W. R. Pulleyblank, Outer-facial graphs and the traveling salesman problem. SIAM J. Optim. 4 (1994) 676–689. D. Hartvigsen and W. R. Pulleyblank, Outer-facial graphs and the traveling salesman problem: Algorithm and polyhedron. Research Report, Center for Research in Business, University of Notre Dame, Notre Dame, IN (1994). J. E. Hopcroft and R. E. Tarjan, Dividing a graph into triconnected components. SIAM J. Comput. 2 (1973) 135–158. J. Matoušek and R. Thomas, Algorithms finding treedecompositions of graphs. J. Algor. 12 (1991) 1–22. T. Politof, A characterization and efficient reliability computation of D –Y reducible networks. PhD. Thesis, University of California, Berkeley, CA (1983). M. Syslo and A. Proskurowski, On Halin graphs. Graph Theory Lagów 1981, Lecture Notes in Mathematics, Vol. 1018, Springer-Verlag, Berlin, Heidelberg (1981) 248– 256. K. Truemper, On the delta-wye reduction for planar graphs. J. Graph Theory 13 (1989) 141–148. W. T. Tutte, Connectivity in Graphs. University of Toronto Press, Toronto, Ontario (1966). W: Networks 0757

1/--страниц