The Windy Postman Problem on Series-Parallel Graphs
Francisco Javier Zaragoza Mart´ınez
†Universidad Aut´onoma Metropolitana Azcapotzalco, Departamento de Sistemas, Av. San Pablo 180, Mexico City.
Thewindy postman problemis the NP-hard problem of finding the minimum cost of a tour traversing all edges of an undirected graph, where the cost of traversal of an edge depends on the direction. Given an undirected graphG, we consider the polyhedronO(G)induced by the linear programming relaxation of a well-known integer programming formulation of the problem. We say thatGiswindy postman perfectifO(G)is integral. There exists a polynomial- time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. Eulerian graphs and trees are windy postman perfect. By considering a family of polyhedra related to O(G), we prove that series-parallel graphs are windy postman perfect, therefore solving a conjecture of Win (1987).
Keywords:windy postman problem, series-parallel graphs, integral polyhedra
Contents
1 Preliminaries 161
2 The Windy Postman Problem 162
3 Windy Postman Ideal Graphs 163
4 Conclusions 165
1 Preliminaries
LetG = (V, E)be an undirected graph, which may contain loops and parallel edges. Theassociated directed graphofGis the directed graphG~ = (V, E+∪E−)obtained fromGby replacing each edge e∈Eby two oppositely oriented arcse+ ∈E+ande− ∈E−. ForS⊆V we defineδG(S)to be the set of edges inGwith one end inSand the other end inS, and¯ ~δG(S)to be the set of arcs inG~ with tails in Sand heads inS. We say that¯ e∈EcrossesSife∈δG(S). We say thatGisevenif|δG(v)|is even for allv ∈V. A closed walkW ofG~ is awindy postman tourofGifW contains all vertices inV and, for everye∈E,W contains at least one ofe+ore−. IfT is a set,x∈RT, andS ⊆T thenx(S)denotes the sumP
s∈Sxs.
†Partially supported by Universidad Aut´onoma Metropolitana Azcapotzalco grant 2270313 and CONACyT grant 69234.
1365–8050 c2005 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France
2 The Windy Postman Problem
Given an undirected graphGwith nonnegative costscon the arcs ofG, the~ windy postman problemcon- sists of finding the minimum cost of a windy postman tour ofG. This problem was proposed by Minieka (1979) and its decision version was shown to be NP-complete, even for planar inputs, by Guan (1984).
An integer programming formulation for the windy postman problem due to Win (1987, 1989) is:
WPP(G, c) = minc>x (1)
subject to
x(~δG(¯v))−x(~δG(v)) = 0for allv∈V (2)
xe++xe− ≥ 1for alle∈E (3)
xe+, xe− ≥ 0for alle∈E (4)
xe+, xe− integral for alle∈E. (5) LetP(G)be the convex hull of the feasible solutions to the integer program above, and letQ(G)be the set of feasible solutions to its linear programming relaxation. Win (1987, 1989) proved that:
Theorem 1 (Win) Every extreme point xof the polyhedron Q(G) has components whose values are either12 or a nonnegative integer. Furthermore,Q(G)is integral if and only ifGis even.
We can strengthen the linear programming relaxation of the windy postman problem by addingodd-cut constraints. LetS⊆V be such that|δG(S)|is odd. Then, in any windy postman tour ofG, at least one element ofδG(S)must be used more than once. Therefore, the inequalities
x(~δG(S)) +x(~δG( ¯S))≥ |δG(S)|+ 1for all oddS ⊆V (6) are valid forP(G). LetO(G)be the subset ofQ(G)that satisfies the odd-cut constraints (6).
We say thatGiswindy postman perfectif the polyhedronO(G)is integral. Equivalently,Gis windy postman perfect ifO(G) = P(G). Windy postman perfect graphs were studied extensively by Win (1987, 1989). Gr¨otschel and Win (1992) proved that there exists a polynomial-time algorithm, based on the ellipsoid method, to solve the windy postman problem for the class of windy postman perfect graphs. This is a consequence of the equivalence of optimization and separation theorem and the fact that all the constraints (2), (3), (4), and (6) can be separated in polynomial time. By Theorem 1, even graphs are windy postman perfect. Win (1987) also proved that forests are windy postman perfect. Windy postman perfection is not closed under taking graph minors:K5is windy postman perfect, butO(K4)has fractional extreme points. Nevertheless, Win (1987) proposed operations that preserve windy postman perfection.
Theorem 2 (Win) LetG, G1, G2be windy postman perfect graphs. Then:
1. Any subdivision ofGis windy postman perfect.
2. Ife∈E(G), thenG / eis windy postman perfect.
3. Ife, f ∈E(G)are parallel, thenG\ {e, f}is windy postman perfect.
4. Ifv1∈V(G1)andv2∈V(G2), then the undirected graphG3obtained by identifying the vertices v1andv2is windy postman perfect.
We observe that the class of even undirected graphs is closed under each of these four operations, and that the same is true for the class of undirected forests. Another class of undirected graphs that has this property is the class of series-parallel undirected graphs. Win (1987) conjectured that these are also windy postman perfect. In what follows, we prove a statement stronger than Win’s conjecture.
3 Windy Postman Ideal Graphs
LetG= (V, E)be an undirected graph, letl∈ZE+, and letb∈ZV withb(V) = 0. We say thatS⊆V is anodd setifb(S) +l(δG(S))is odd. LetG~ = (V, E+∪E−)be the associated directed graph ofG, and letO(G, l, b)be the set of feasible solutions to the system
x(~δG(¯v))−x(~δG(v)) = bvfor allv∈V (7)
xe++xe− ≥ lefor alle∈E (8)
x(~δG(S)) +x(~δG( ¯S)) ≥ l(δG(S)) + 1for all oddS⊆V (9)
xe+, xe− ≥ 0for alle∈E. (10)
We say thatGiswindy postman idealif the polyhedronO(G, l, b)is integral for all possible choices ofl andb. Observe that windy postman ideal graphs are windy postman perfect. We prove that windy postman ideal graphs are precisely the series-parallel graphs, proving Win’s conjecture as a consequence.
In contrast to windy postman perfection, windy postman ideality is closed under taking graph minors.
Theorem 3 LetG= (V, E)be a windy postman ideal undirected graph, and lete∈E. ThenG\eand G / eare also windy postman ideal.
Proof. Letu, v be the ends ofe. Letl0 ∈ZE\e+ , and letb0 ∈ ZV(G / e)withb0(V(G / e)) = 0. Let l∈ZE+andb∈ZV be defined bylf =l0ffor allf ∈E\eandle= 0, andbw=b0wfor allw∈V\{u, v}, bu =b0e, andbv = 0. SinceGis windy postman ideal,O(G, l, b)is integral. SinceO(G / e, l0, b0)is the projection ofO(G, l, b)ontoxe+ = 0andxe− = 0, it is also integral. Hence,G / eis windy postman ideal.
Letl0 ∈ZE\e+ , and letb0∈ZV withb0(V) = 0. Definel∈ZE+bylf =l0ffor allf ∈E\eandle= 0.
SinceGis windy postman ideal,O(G, l, b0)is integral. SinceO(G\e, l0, b0)is a face ofO(G, l, b0), it is
also integral. Hence,G\eis windy postman ideal. 2
Letx∈O(G, l, b), and lete∈ E. We say thateisintegralif bothxe+ andxe− are integral, and we say thateisfractionalotherwise. We say thateistightifxe++xe− =le.
Lemma 4 LetG= (V, E)be a minor minimal, non windy postman ideal undirected graph. Letb∈ZV andl ∈ ZE+ be such thatO(G, l, b)is not integral, and letxbe one of its fractional extreme points. If e∈Eis integral, thenxe++xe− =le+ 1.
The following two lemmas imply that we only need to consider2-vertex-connected undirected graphs.
Lemma 5 LetG= (V, E)be an undirected graph, and letG1, . . . , Gkbe its connected components. Let b∈ZV andl∈ZE+. For every1≤i≤k, letbiandlibe the restrictions ofbandltoGi. IfO(Gi, li, bi) is integral for all1≤i≤k, thenO(G, l, b)is also integral. Hence,Gis windy postman ideal if and only ifGiis windy postman ideal for all1≤i≤k.
Lemma 6 LetG = (V, E)be an undirected graph with a cut vertex v, and let G1 = (V1, E1)and G2= (V2, E2)be the partition ofGinduced byv. Letb∈ZV andl∈ZE+. Fori∈ {1,2}, letbiandli be the restrictions ofbandltoGi, exceptb1v=b(V2)andb2v =b(V1). ThenO(G, l, b)is integral if and only ifO(G1, l1, b1)andO(G2, l2, b2)are integral. Hence,Gis windy postman ideal if and only ifG1
andG2are also windy postman ideal.
Now we state our characterization of windy postman ideal graphs.
Theorem 7 An undirected graphGis windy postman ideal if and only ifGis series-parallel.
Sketch of proof. Since O(K4)is not integral, it follows that windy postman ideal graphs must be series-parallel. LetG= (V, E)be a minor minimal, non windy postman ideal series-parallel graph. By Lemmas 5 and 6, we can assume thatGis2-vertex-connected. We can verify that all series-parallel graphs with at most two vertices are windy postman ideal. Hence, we can assume thatGhas two edges in parallel or two edges in series. LetG~ = (V, E+∪E+)be the associated directed graph ofG, letl∈ZE+, and let b∈ZV withb(V) = 0. For a contradiction, assume thatxis a fractional extreme point ofO(G, l, b).
Parallel case.Assume first thatGhas twoparalleledgeseandf, with endsuandv. LetH = (V, F) be the undirected graph obtained fromGby replacing edges eandf by a single edgeg, and letH~ = (V, F+∪F−)be its associated directed graph. We can assume thate+,f+, andg+ are oriented from utov, thate−,f−, andg− are oriented from vtou, and that all other arcs ofG~ andH~ are oriented consistently. Definel0∈ZF+byl0h=lhifh6=g, andl0g=le+lf. Note that(G, l, b)and(H, l0, b)have the same odd sets.
Definex0 ∈QF
+∪F−
+ byx0a =xa ifa /∈ {g+, g−},x0g+ =x0e++x0f+, andx0g− =x0e−+x0f−, and observe thatx0 ∈ O(H, l0, b). Assume first thatx0 is integral. In each of the two casesxe− is integral andxe− is fractional we can construct vectorsy 6= z such thaty, z ∈ O(G, l, b)andx = 12(y+z), contradicting the choice ofx.
It follows that x0 is fractional. Since H is a minor ofG, O(H, l0, b)is integral. Hence, there exist distinct vectorsy0, z0 ∈O(H, l0, b)such thatx0 = 12(y0+z0). We may choosey0, z0so thatky0−z0kis arbitrarily small. In each of the cases (a) neitherenorfis tight and (b)eis tight, we can construct vectors y6=z(usingy0andz0) such thaty, z∈O(G, l, b)andx=12(y+z), contradicting the choice ofx.
Series case. Now assume thatGhas two edgeseandf inseries, with endsuandv, andvandw, respectively. Using Lemma 4 and thatGis2-edge-connected, we can prove that there are fractional edges inE\ {e, f}. LetSebe the set of all odd sets crossed bye, and let
se= min{x(~δG(S)) +x(~δG( ¯S))−l(δG(S))−1 : S∈Se}. (11) Define Sf andsf in a similar way. As above, by considering the minors G /{e, f} and G / e, we can show that se = sf = 0. Using Lemma 4 we can show that{v} must be an odd set. Lettv = xe++xe−+xf++xf−−le−lf−1. LetTebe the set of all odd sets crossed bye, except for{v}and its complement, let
te= min{x(~δG(T)) +x(~δG( ¯T))−l(δG(T))−1 : T ∈Te}, (12)
and letTe ∈Teachieve this minimum. DefineTf,tf, andTf in a similar way. Sincese=sf = 0, it follows that eithertv = 0, ortv >0andte=tf = 0. As above, we can deal with these last two cases
considering the minorsG / eandG /{e, f}, respectively. 2
4 Conclusions
Recall that ifG= (V, E)is not series-parallel, then it contains a subdivisionK= (W, F)ofK4. Define the vectorl ∈ZE+byle= 1ife∈F, andle= 0otherwise. SinceO(K4)is not an integral polyhedron, it follows thatO(G, l,0)is also not an integral polyhedron.
Corollary 8 LetG= (V, E)be an undirected graph. ThenGis series-parallel if and only if the polyhe- dronO(G, l,0)is integral for alll∈ {0,1}E.
We also obtain Win’s conjecture as an easy corollary.
Corollary 9 IfGis an undirected series-parallel graph, thenGis windy postman perfect.
Since themixed postman problemcan be seen as a special case of the windy postman problem, it also has a polynomial-time algorithm for the class of series-parallel graphs, a result of Fernandes et al. (2003).
It is possible to verify thatK3,3is windy postman perfect. Using Theorems 1, 2, and 7, we can extend the class of undirected graphs known to be windy postman perfect.
Theorem 10 All graphs in the classFconstructed as follows are windy postman perfect: (a) All graphs whose connected components are even, series-parallel, orK3,3are inF, and (b) any graph obtained from graphs inF by performing any of the operations described in the statement of Theorem 2 is inF.
Agraftis a pair(G, T)whereG = (V, E)is an undirected graph andT ⊆ V with|T|even. Let l∈ZE+and letb∈ZV withb(V) = 0. We say that the pair(l, b)isvalidfor(G, T)if for everyv∈V, bv+l(δG(v))is odd if and only ifv ∈T. We say that(G, T)iswindy postman perfectifO(G, l, b)is integral for each valid pair(l, b). We have proved that windy postman perfection of grafts is closed under takinggraft minors, therefore generalizing Theorem 3, and we have found twoexcluded minorsfor this property. We believe that these are the only two excluded minors for windy postman perfection of grafts.
A proof of this statement would give rise to a common generalization of Theorems 1 and 7.
Acknowledgements
I would like to thank Bill Cunningham, Joseph Cheriyan, Bertrand Guenin, and Jim Geelen for their insightful comments and for their encouragement during my stay at the University of Waterloo.
References
C. Fernandes, O. Lee, and Y. Wakabayashi. The minimum cycle cover and the chinese postman problems on mixed graphs with bounded tree width. Available athttp://www.ime.usp.br/˜yw/, 2003.
M. Gr¨otschel and Z. Win. A cutting plane algorithm for the windy postman problem.Math. Programming, 55(3, Ser. A):339–358, 1992.
M. G. Guan. On the windy postman problem.Discrete Appl. Math., 9(1):41–46, 1984.
E. Minieka. The Chinese postman problem for mixed networks.Management Sci., 25(7):643–648, 1979.
Z. Win. Contributions to Routing Problems. PhD thesis, Universit¨at Augsburg, Germany, 1987.
Z. Win. On the windy postman problem on Eulerian graphs.Math. Programming, 44(1, (Ser. A)):97–112, 1989.
