Lecture Notes in Computer Science
Lecture Notes in Computer Science
13
Series Editors
Gerhard Goos, Karlsruhe University, Germany
Juris Hartmanis, Cornell University, NY, USA
Jan van Leeuwen, Utrecht University, The Netherlands
Volume Editors
Robert E. Bixby
Department of Computational and Applied Mathematics, Rice University
6020 Annapolis, Houston, TX 77005, USA
E-mail: [email protected]
E. Andrew Boyd
PROS Strategic Solutions
3223 Smith Street, Houston, TX 77006, USA
E-mail: [email protected]
Roger Z. Rı́os-Mercado
Department of Industrial, Engineering,Texas A&M University
1000 Country Place Dr. Apt. 69, Houston, TX 77079, USA
E-mail: [email protected]
ISSN 0302-9743
ISBN 3-540-64590-X Springer-Verlag Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,
reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication
or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,
in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are
liable for prosecution under the German Copyright Law.
c Springer-Verlag Berlin Heidelberg 1998
Printed in Germany
Typesetting: Camera-ready by author
SPIN 10637207 06/3142 – 5 4 3 2 1 0 Printed on acid-free paper
Preface
This volume contains the papers selected for presentation at IPCO VI, the Sixth
International Conference on Integer Programming and Combinatorial Optimiza-
tion, held in Houston, Texas, USA, June 22–24, 1998. The IPCO series of confer-
ences highlights recent developments in theory, computation, and applications
of integer programming and combinatorial optimization.
These conferences are sponsored by the Mathematical Programming Society,
and are held in the years in which no International Symosium on Mathemati-
cal Programming takes place. Earlier IPCO conferences were held in Waterloo
(Canada) in May 1990; Pittsburgh (USA) in May 1992; Erice (Italy) in April
1993; Copenhagen (Denmark) in May 1995; and Vancouver (Canada) in June
1996.
The proceedings of IPCO IV (edited by Egon Balas and Jens Clausen in
1995) and IPCO V (edited by William Cunningham, Thomas McCormick, and
Maurice Queyranne in 1996), were published by Springer-Verlag in the series
Lecture Notes in Computer Science as Volumes 920 and 1084, respectively. The
proceedings of the first three IPCO conferences were published by organizing
institutions.
A total of 77 extended abstracts, mostly of an excellent quality, were initially
submitted. Following the IPCO policy of having only one stream of sessions over
a three day span, the Program Committee selected 32 papers. As a result, many
outstanding papers could not be selected.
The papers included in this volume have not been refereed. It is expected
that revised versions of these works will appear in scientific journals.
The Program Committee thanks all the authors of submitted extended ab-
stracts and papers for their support of the IPCO conferences.
Bipartite Designs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
G. Gasparyan
A Theorem of Truemper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
M. Conforti and A. Kapoor
Edge Connectivity
Edge-Splitting and Edge-Connectivity Augmentation in Planar Graphs . . . 96
H. Nagamochi and P. Eades
Algorithms
Multicuts in Unweighted Graphs with Bounded Degree and Bounded
Tree-Width . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
G. Călinescu, C. G. Fernandes, and B. Reed
Network Flows
Building Chain and Cactus Representations of All Minimum Cuts from
Hao-Orlin in the Same Asymptotic Run Time . . . . . . . . . . . . . . . . . . . . . . . . . 294
L. Fleischer
Scheduling
Non-approximability Results for Scheduling Problems with Minsum
Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
J. A. Hoogeveen, P. Schuurman, and G. J. Woeginger
Approximation Bounds for a General Class of Precedence Constrained
Parallel Machine Scheduling Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
A. Munier, M. Queyranne, and A. S. Schulz
An Efficient Approximation Algorithm for Minimizing Makespan on
Uniformly Related Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
C. Chekuri and M. Bender
On the Relationship between Combinatorial and LP-Based Approaches to
NP-Hard Scheduling Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394
R. N. Uma and J. Wein
1 Introduction
A clutter C is a pair (V (C), E(C)), where V (C) is a finite set and E(C) =
{S1 , . . . , Sm } is a family of subsets of V (C) with the property that Si ⊆ Sj
implies Si = Sj . The elements of V (C) are the vertices of C and those of E(C)
are the edges. A transversal of C is a minimal subset of vertices that intersects
all the edges. Let τ (C) denote the cardinality of a smallest transversal. A clutter
C packs if there exist τ (C) pairwise disjoint edges.
For j ∈ V (C), the contraction C/j and deletion C \ j are clutters defined as
follows: both have V (C)−{j} as vertex set, E(C/j) is the set of minimal elements
of {S − {j} : S ∈ E(C)} and E(C \ j) = {S : j 6∈ S ∈ E(C)}. Contractions and
deletions of distinct vertices can be performed sequentially, and it is well known
that the result does not depend on the order. A clutter D obtained from C by
deleting Id ⊆ V (C) and contracting Ic ⊆ V (C), where Ic ∩ Id = ∅ and Ic ∪ Id 6= ∅,
is a minor of C and is denoted by C \ Id /Ic .
We say that a clutter C has the packing property if it packs and all its minors
pack. A clutter is minimally non packing (mnp) if it does not pack but all its
minors do. In this paper, we study mnp clutters.
?
This work was supported in part by NSF grants DMI-9424348, DMS-9509581, ONR
grant N00014-9710196, a William Larimer Mellon Fellowship, and the Swiss National
Research Fund (FNRS).
X
n
min xj : Ax ≥ e, x ∈ {0, 1}n
1
X
m
= max yi : yA ≤ e, y ∈ {0, 1}m , (1)
1
X
n
max xj : Ax ≤ e, x ∈ {0, 1}n
1
X
m
= min yi : yA ≥ e, y ∈ {0, 1}m .
1
The 0,1 matrix A has the Max-Flow Min-Cut property (or simply MFMC
property) if the linear system Ax ≥ e, x ≥ 0 is totally dual integral (Seymour
[16]). Specifically, let
τ (A, w) = min wx : Ax ≥ e, x ∈ {0, 1}n ,
Xm
ν(A, w) = max yi : yA ≤ w, y ∈ {0, 1}m .
1
Conjecture 1. A clutter has the packing property if and only if it has the MFMC
property.
This conjecture for the packing property is the analog of the following version of
Lovász’s theorem [11]: A 0, 1 matrix A is perfect if and only if the linear system
Ax ≤ e, x ≥ 0 is totally dual integral.
In this paper, our first result is that this conjecture holds for diadic clutters.
A clutter is diadic if its edges intersect its transversals in at most two vertices
(Ding [6]). In fact, we show the stronger result:
Theorem 2. A diadic clutter is ideal if and only if it has the MFMC property.
A clutter is said to be minimally non ideal (mni) if it is not ideal but all
its minors are ideal. Theorem 1 is equivalent to saying that mni clutters do not
pack. Therefore mnp clutters fall into two distinct classes namely:
Next we consider ideal mnp clutters. Seymour [16] showed that Q6 is the only
ideal mnp clutter which is binary (a clutter is binary if its edges have an odd
intersection with its transversals). Aside from Q6 , only one ideal mnp clutter
was known prior to this work, due to Schrijver [14]. We construct an infinite
family of such mnp clutters (see Appendix). The clutter Q6 , Schrijver’s example
and those in our infinite class all satisfy τ (C) = 2. Our next result is that all
ideal mnp clutters with τ (C) = 2 share strong structural properties with Q6 .
Theorem 3. Every ideal mnp clutter C with τ (C) = 2 has the Q6 property, i.e.
A(C) has 4 rows such that every column restricted to this set of rows contains
two 0’s and two 1’s and, furthermore, each of the 6 such possible 0,1 vectors
occurs at least once.
We make the following conjecture and we prove later that it implies Conjecture 1.
The blocker b(C) of a clutter C is the clutter with V (C) as vertex set and the
transversals of C as edge set. For Id , Ic ⊆ V (C) with Id ∩ Ic = ∅, it is well known
and easy to derive that b(C \ Id /Ic ) = b(C)/Id \ Ic .
We now consider minimally non ideal mnp clutters. The clutter Jt , for t ≥ 2
integer, is given by V (Jt ) = {0, . . . , t} and E(Jt ) = {1, . . . , t}, {0, 1}, {0, 2}, . . . ,
{0, t}. Given a mni matrix A, let x̃ be any vertex of {x ≥ 0 : Ax ≥ e} with
fractional components. A maximal row submatrix Ā of A for which Āx̃ = e is
called a core of A. The next result is due to Lehman [10] (see also Padberg [13],
Seymour [17]).
Theorem 4. Let A be a mni matrix, B = b(A), r = τ (B) and s = τ (A). Then
(i) A (resp. B) has a unique core Ā (resp. B̄).
(ii) Ā, B̄ are square matrices.
Moreover, either A = A(Jt ), t ≥ 2, or the rows and columns of Ā can be
permuted so that
(iii) ĀB̄ T = J + (rs − n)I.
Here J denotes a square matrix filled with ones and I the identity matrix. Only
three cores with rs = n + 2 are known and none with rs ≥ n + 3. Nevertheless
Cornuéjols and Novick [5] have constructed more than one thousand mni matri-
ces from a single core with rs = n + 2. An odd hole Ck2 is a clutter with k ≥ 3
odd, V (Ck2 ) = {1, . . . k} and E(Ck2 ) = {{1, 2}, {2, 3}, . . . , {k − 1, k}, {k, 1}}. Odd
holes and their blockers are mni with rs = n + 1 and Luetolf and Margot [12]
give dozens of additional examples of cores with rs = n + 1 and n ≤ 17. We
prove the following theorem.
Theorem 5. Let A 6= A(Jt ) be a mni matrix. If A is minimally non packing,
then rs = n + 1.
We conjecture that the condition rs = n + 1 is also sufficient.
Conjecture 3. Let A 6= A(Jt ) be a mni matrix. Then A is minimally non packing
if and only if rs = n + 1.
Using a computer program, we were able to verify this conjecture for all known
mni matrices with n ≤ 14.
A clutter is minimally non MFMC if it does not have the MFMC property
but all its minors do. Conjecture 1 states that these are exactly the mnp clutters.
Although we cannot prove this conjecture, the next proposition shows that a
tight link exists between minimally non MFMC and mnp clutters. The clutter
D obtained by replicating element j ∈ V (C) of C is defined as follows: V (D) =
V (C) ∪ {j 0 } where j 0 6∈ V (C), and
Proof. Let w ∈ Z+ n
be chosen such that τ (C, w) > ν(C, w) and τ (C, w0 ) = ν(C, w0 )
for all w ∈ Z+ with w0 ≤ w and wj0 < wj for at least one j. Note that wj > 0
0 n
for all j, since otherwise some deletion minor of C does not have the MFMC
property. Construct D by replicating wj − 1 times every element j ∈ V (C). By
Remark 2, D does not pack. Let D0 = D \ Id /Ic be any minor of D. If j or one of
its replicates is in Ic then we can assume that j and all its replicates are in Ic .
Then D0 is a replication of a minor C 0 of C/j. Since C 0 has the MFMC property,
D0 packs by Remark 2. Thus we can assume Ic = ∅. By the choice of w and
Remark 2, if Id 6= ∅ then D0 packs. t
u
Proposition 1 can be used to show that if every ideal mnp clutter C satisfies
τ (C) = 2 then the packing property and the MFMC property are the same.
Proposition 2. Conjecture 2 implies Conjecture 1.
Proof. Suppose there is a minimally non MFMC clutter C that packs. By The-
orem 1, C is ideal. Then by Proposition 1, there is a mnp clutter D with a
replicated element j. Furthermore, D is ideal. Using Conjecture 2, 2 = τ (D) ≤
τ (D/j). Since D/j packs, there are sets S1 , S2 ∈ E(D) with S1 ∩ S2 = {j}.
Because j is replicated in D, we have a set S10 = S1 ∪ {j 0 } − {j}. Remark that
j 0 6∈ S2 . But then S10 ∩ S2 = ∅, hence D packs, a contradiction. t
u
Finally, we introduce a new class of clutters called weakly binary. They can
be viewed as a generalization of binary and of balanced clutters. (A 0,1 matrix
is balanced if it does not have A(Ck2 ) as a submatrix, k ≥ 3 odd, where as above
Ck2 denotes an odd hole. See [4] for a survey of balanced matrices). We say that
a clutter C has an odd hole Ck2 if A(Ck2 ) is a submatrix of A(C). An odd hole Ck2
of C is said to have a non intersecting set if ∃S ∈ E(C) such that S ∩ V (Ck2 ) = ∅.
A clutter is weakly binary if, in C and all its minors, all odd holes have non
intersecting sets.
Theorem 6. Let C be weakly binary and minimally non MFMC. Then C is
ideal.
Note that, when C is binary, this theorem is an easy consequence of Seymour’s
theorem saying that a binary clutter has the MFMC property if and only if it
does not have Q6 as a minor [16]. Observe also that Theorem 6 together with
Conjecture 2, Proposition 2, and Theorem 3, would imply that a weakly binary
clutter has the MFMC property if and only if it does not contain a minor with
the Q6 property.
6 Gérard Cornuéjols et al.
References
1. C. Berge. Färbung von Graphen deren sämtliche bzw. deren ungerade Kreize starr
sind (Zusammenfassung), Wisenschaftliche Zeitschritch, Martin Luther Universität
Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe, 114–115, 1960.
2. W. G. Bridges and H. J. Ryser. Combinatorial designs and related systems. J.
Algebra, 13:432–446, 1969.
3. M. Conforti and G. Cornuéjols. Clutters that pack and the max-flow min-cut prop-
erty: A conjecture. In W. R. Pulleyblank and F. B. Shepherd, editors, The Fourth
Bellairs Workshop on Combinatorial Optimization, 1993.
4. M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković. Balanced matrices. In
J. R. Birge and K. G Murty, editors, Math. Programming, State of the Art 1994,
pages 1–33, 1994.
5. G. Cornuéjols and B. Novick. Ideal 0, 1 matrices. J. Comb. Theory Ser. B, 60:145–
157, 1994.
6. G. Ding. Clutters with τ2 = 2τ . Discrete Math., 115:141–152, 1993.
7. J. Edmonds and R. Giles. A min-max relation for submodular functions on graphs.
Annals of Discrete Math., 1:185–204, 1977.
8. B. Guenin. Packing and covering problems. Thesis proposal, GSIA, Carnegie Mel-
lon University, 1997.
9. A. Lehman. On the width-length inequality. Mathematical Programming, 17:403–
417, 1979.
10. A. Lehman. On the width-length inequality and degenerate projective planes. In
W. Cook and P.D. Seymour, editors, Polyhedral Combinatorics, DIMACS Series
in Discrete Math. and Theoretical Computer Science, Vol. 1, pages 101–105, 1990.
11. L. Lovász. Normal hypergraphs and the perfect graph conjecture. Discrete Math.
2:253–267, 1972.
12. C. Luetolf and F. Margot. A catalog of minimally nonideal matrices. Mathematical
Methods of Operations Research, 1998. To appear.
13. M. W. Padberg. Lehman’s forbidden minor characterization of ideal 0−1 matrices.
Discrete Math., 111:409–420, 1993.
14. A. Schrijver. A counterexample to a conjecture of Edmonds and Giles. Discrete
Math., 32:213–214, 1980.
15. A. Schrijver. Theory of Linear and Integer Programming, Wiley, 1986.
16. P. D. Seymour. The matroids with the max-flow min-cut property. J. Comb. Theory
Ser. B, 23:189–222, 1977.
17. P. D. Seymour. On Lehman’s width-length characterization. In W. Cook and P. D.
Seymour, editors, Polyhedral Combinatorics, DIMACS Series in Discrete Math.
and Theoretical Computer Science, Vol. 1, pages 107–117, 1990.
Appendix
S1 = I1 ∪ I3 ∪ I5 , S2 = I1 ∪ I4 ∪ I6 ,
S3 = I2 ∪ I4 ∪ I5 , S4 = I2 ∪ I3 ∪ I6 .
The Packing Property 7
Without loss of generality we can reorder the vertices in V (C) so that elements
in Ik preceed elements in Ip when k < p.
Given a set P of p elements, let Hp denote the ((2p − 1) × p) matrix whose
rows are the characteristic vectors of the nonempty subsets of P, and let Hp∗ be
its complement, i.e. Hp + Hp∗ = J.
For each r, t ≥ 1 let |I1 | = |I2 | = r, |I3 | = |I4 | = t and |I5 | = |I6 | = 1. We
call Qr,t the clutter corresponding to the matrix
I1 I2 I3 I4 I5 I6
Hr Hr∗ J 0 1 0
A(Qr,t ) = Hr∗ Hr 0 J 1 0
J 0 Ht∗ Ht 0 1
0 J Ht Ht∗ 0 1
where J denotes a matrix filled with ones. The rows are partitioned into four
sets that we denote respectively by T (3, 5), T (4, 5), T (1, 6), T (2, 6). The indices
k, l for a given family indicate that the set Ik ∪ Il is contained is every element of
the family. Note that the edge S1 occurs in T (3, 5), S2 in T (1, 6), S3 in T (4, 5)
and S4 in T (2, 6).
Since H1 contains only one row, we have Q1,1 = Q6 and Q2,1 is given by
1 1 0 0 1 0 1 0
1 0 0 1 1 0 1 0 T (3, 5)
0 1 1 0 1 0 1 0
0 0 1 1 0 1 1 0
A(Q2,1 ) = 1 0 0 1 0 1 1 0
T (4, 5)
0 1 1 0 0 1 1 0
1 1 0 0 0 1 0 1 T (1, 6)
0 0 1 1 1 0 0 1 T (2, 6)
Proposition 3. For all r, t ≥ 1, the clutter Qr,t is ideal and minimally non
packing.
The clutter D obtained by duplicating element j ∈ V (C) of C is defined by:
V (D) = V (C)∪{j 0 } where j 0 6∈ V (C) and E(D) = {S : j 6∈ S ∈ E(C)}∪{S ∪{j 0 } :
j ∈ S ∈ E(C)}. Let α(k) be the mapping defined by: α(1) = 2, α(2) = 1, α(3) =
4, α(4) = 3, α(5) = 6, α(6) = 5.
Suppose that, for k ∈ {1, .., 6}, we have that Ik contains a single element
j ∈ V (C). Then j belongs to exactly two of S1 , . . . , S4 . These two edges are of
the form {j} ∪ Ir ∪ It and {j} ∪ Iα(r) ∪ Iα(t) . We can construct a new clutter
C ⊗ j by duplicating element j in C and including in E(C ⊗ j) the edges:
{j} ∪ Iα(j) ∪ Ir ∪ It ,
(2)
{j 0 } ∪ Iα(j) ∪ Iα(r) ∪ Iα(t) .
8 Gérard Cornuéjols et al.
Bertrand Guenin
1 Introduction
Let G = (V, E) be a graph and Σ ⊆ E. Edges in Σ are called odd and edges in
E −Σ are called even. The pair (G, Σ) is called a labeled graph. Given a subgraph
H of G, V (H) denotes the set of vertices of H, and E(H) the set of edges of H.
A subset L ⊆ E(G) is odd (resp. even) if |L ∩ Σ| is odd (resp. even). A cycle of
G is a connected subgraph of G with all degrees equal to two.
A labeled graph (G, Σ) is said to be weakly bipartite if the following polyhe-
dron Q is integral (i.e. all its extreme points are integral):
n o
|E| P
Q = x ∈ <+ : i∈C xi ≥ 1, for all odd cycles C of (G, Σ) (1)
See Gerards [7] for a recent survey on weakly bipartite graphs and connexions
with multicommodity flows. Particularly interesting is the case where Σ = E(G).
Let x̂ be any 0, 1 extreme point of Q. Then x̂ is the incidence vector of a set of
edges which intersect every odd cycle of G. In other words e − x̂ is the incidence
|E|
vector of a bipartite subgraph of G. Let w ∈ <+ be weights for the edges of G
and let x̄ be a solution to
min wx : x ∈ Q ∩ {0, 1}|E| . (2)
Remark 1. (G, Σ) and (G, Σ 4 δ(U )) have the same set of odd cycles.
(H, θ) is called a proper minor of (G, Σ) if it is a minor of (G, Σ) and |E(H)| <
|E(G)|. An odd K5 , denoted by K f5 , is the complete graph on 5 vertices where
all edges are labeled odd. For the polyhedron Q associated with K f5 , the 10
constraints corresponding to the triangles (the odd cycles of length three) de-
fine a fractional point ( 13 , . . . , 13 ) of Q. Thus K f5 is not weakly bipartite. Sey-
mour [18],[19] predicted, as part of a more general conjecture on binary clutters
(see Sec. 2.3) that:
f5 minor.
Conjecture 1. (G, Σ) is weakly bipartite if and only if it has no K
f5 .
Theorem 1. Every minimally non weakly bipartite graph is a relabeling of K
2 Clutters
A clutter A is said to be binary if for any three sets S1 , S2 , S3 ∈ Ω(A), the set
S1 4S2 4S3 contains a set of Ω(A). Lehman [11] showed (see also Seymour [17]):
Thus in particular if A is binary then so is its blocker. The following is easy, see
for example [6].
Proposition 1. Let (G, Σ) be a labeled graph. Then the clutter of odd cycles of
(G, Σ) is binary.
Note that the blocker of Jt is Jt itself. We therefore have {1, 2} ∈ E(Jt ) and
{1, 2} ∈ E (b(Jt )). It follows by Theorem 4 that Jt is not binary. The clutter F7
is defined as follows: E(F7 ) = {1, . . . , 7} and
Ω(F7 ) = {{1, 3, 5}, {1, 4, 6}, {2, 4, 5}, {2, 3, 6}, {1, 2, 7}, {3, 4, 7}, {5, 6, 7}} .
Since we can readily check that F7 and b(OK5 ) are not clutters of odd cycles this
conjecture implies Conjecture 1. Next are two results on mni binary clutters.
Case 1: |C| = r.
By Remark 5, we have C ∈ Ω(Ā). Let U be the mate of C and q = |C ∩ U | ≥
2. By Theorem 4, q is odd so in particular q ≥ 3. Since C ⊆ C1 ∪ C2 , we
must have |U ∩ C1 | > 1 or |U ∩ C2 | > 1. This implies that U is the mate of
C1 or C2 , i.e. that C = C1 or C = C2 .
Case 2: |C| > r.
Let t = |C1 ∩ C2 ∩ C|. Since C ⊆ C1 ∪ C2 , it follows that
For T = C1 4 C2 4 C, we have
|T | = |(C1 ∩ C2 ∩ C) ∪ [(C1 4 C2 ) − C]| , C ⊆ C1 ∪ C2
= |C1 ∩ C2 ∩ C| + |C1 4 C2 | − |(C1 4 C2 ) ∩ C|
= t + |C1 4 C2 | − (|C| − t), by (3)
= 2t + |C1 | + |C2 | − 2|C1 ∩ C2 | − |C|
≤ |C1 | + |C2 | − |C|, t ≤ |C1 ∩ C2 |
≤ 2r − (r + 1), C1 , C2 ∈ Ω(Ā)
Since A is binary we have that T is equal to, or contains an element of Ω(A).
But |T | ≤ r − 1 which contradicts Theorem 3(i) and Remark 5. t
u
Notice that for OK5 the previous theorem simply says that given two triangles
C1 , C2 there is no odd cycle (distinct from C1 and C2 ) which is contained in the
union of C1 and C2 . It is worth mentioning that this is a property of mni binary
clutters only. Indeed the property does not hold for odd holes or more generally
for any circulant matrix with the consecutive one property. For a description of
many classes of mni clutters see [4] and [14].
Proposition 3. Let A be a mni binary clutter and B its blocker. For any e ∈
E(A) there exist C1 , C2 , C3 ∈ Ω(Ā) and U1 , U2 , U3 ∈ Ω(B̄) such that
(i) C1 ∩ C2 = C1 ∩ C3 = C2 ∩ C3 = {e}
(ii) U1 ∩ U2 = U1 ∩ U3 = U2 ∩ U3 = {e}
(iii) For all i, j ∈ {1, 2, 3} we have:
Ci ∩ Uj = {e} if i 6= j, and |Ci ∩ Uj | = q ≥ 3, if i = j.
and
Lemma 2. Let (G, Σ) be a minimally non weakly bipartite graph with a partition
of its edges as given in (4)-(5).
CR
w1 odd w2
e
CB CG
Fig. 1. Lemma 2. Bold solid lines represent paths in R ∪ W−e, dashed lines paths in
B ∪ W−e, and thin solid lines paths in G ∪ W−e.
Q
w1
P
t
P’
w2
Q’
Lemma 3. Let (G, Σ) be a minimally non weakly bipartite graph with a partition
of its edges as given in (4)-(5). Suppose we also have odd cycles CR , CB and CG
as defined in Lemma 2 where e is the only odd edge in CR ∪ CB ∪ CG .
(i) There is an odd path PR (resp. PB , PG ) between a vertex vBR (resp.
vRB , vBG ) of CB (resp. CR , CB ) distinct from w1 , w2 , and a vertex vGR
(resp. vGB , vRG ) of CG (resp. CG , CR ) distinct from w1 , w2 .
(ii) PR ⊆ R ∪ W−e, PB ⊆ B ∪ W−e and PG ⊆ G ∪ W−e.
vRG vRB
CR
PG PB
odd odd
w1 odd w2
e
vBG vGB
CB CG
PR
vBR vGR
odd
Fig. 3. Lemma 3.
Proof (of Lemma 3). By symmetry it is sufficient to show the result for path
0
PR . Since |CR ∩ R| ≥ 2 there is an edge eB = (vBR , vBR ) ∈ B of CB such that
vBR is distinct from w1 , w2 and CB −e(w1 , vBR ) contains exactly one edge in B
0
namely eB . Similarly, we have edge eG = (vGR , vGR ) ∈ CG with vGR distinct
from w1 , w2 and CG −e(w1 , vGR ) ∩ G = {eG }.
By property (P2) there is an odd cycle C such that C ∩ B = {eB } and
C ∩ G = {eG }. The cycle C can be written as {eB , eG } ∪ PR ∪ PR0 where PR and
PR0 are paths included in R ∪ W−e. Since C is odd we can assume w.l.o.g. that
PR is odd and PR0 is even.
18 Bertrand Guenin
0 0
Case 1: The endpoints of PR are vBR , vGR (resp. vBR , vGR ).
0
Then let S = [CB−e(w1 , vBR ), PR , CG−e(vGR , w1 )]. By Lemma 1, E(S) con-
tains an odd cycle but e 6∈ E(S) and E(S) ∩ B = ∅, a contradiction to
(P1).
0 0
Case 2: The endpoints of PR are vBR , vGR .
0 0
Then let S = [CB−e(w1 , vBR ), PR , CG−e(vGR , w1 )]. By Lemma 1, E(S) con-
tains an odd cycle but e 6∈ E(S) and E(S) ∩ B = E(S) ∩ G = ∅, a contra-
diction to (P1).
Thus PR has endpoints vBR , vGR . t
u
Remark 7. Let (G, Σ) be a labeled graph with an odd path P where all internal
vertices of P have degree two (in G). Then there is a sequence of relabeling
and contractions that will replace P by a single odd edge, without changing the
remainder of the graph.
(iii) PR0 and PB0 (resp. PG0 ) share an internal vertex tRB (resp. tRG ).
(iv) PB0 (tRB , vGB
0
) and PG0 share an internal vertex tBG .
0 0 0
(v) PB and PG (tRG , vBG ) share an internal vertex t0BG .
(vi) Paths PR (vBR , tRB ) and PR0 (vGR , tRG ) consist of a single edge.
0
(vii) PB0 (resp. PG0 ) has exactly one odd edge which is incident to vGB 0
0
(resp. vBG ).
(viii) PR0 (vBR , tRB ), PR0 (vGR , tRG ) are even and PR0 (tRB , tRG ) is odd.
(ix) No vertex is common to all three paths PR , PB and PG .
t RB odd t RG
P’R
v RB CR vRG P’B
P’G
w1 odd w2
e
vBR vGR
odd odd
v’BG CB CG v’GB
We did not represent vertices tBG (and t0BG ) in the previous figure. Let q denote
the first vertex of PG0 , starting from vRG , which is also a vertex of PB0 (tRB , vGB
0
)
0
(see Fig. 4). By Lemma 5(iv) there exist such a vertex. Let q be the first vertex
of PG0 (q, vRG ), starting from q, which is either a vertex of PB0 or equal to vRG .
By Lemma 5(ix) q, q 0 are distinct from tRB .
Definition 2. (K, ΣK ) is the graph (see Fig. 5) obtained by deleting every edge
of (H, ΣH ) which is not an edge of CR , CB , CG or PR0 (vBR , tRB ), PB0 and PG0 (q, q 0 ).
From Lemma 5 we can readily obtain the following properties:
Remark 9.
(i) There are exactly two odd edges in (K, ΣK ), namely e and the edge of PB0
0
incident to vGB .
0
(ii) Let S be the set of vertices {w1 , w2 , vBR , vRB , vGB , tRB , q, q 0 } shown in
0
Fig. 5. vRB and q may denote the same vertex but all other vertices of S
are distinct.
(iii) S is the set of all vertices of (K, ΣK ) which have degree greater than two.
20 Bertrand Guenin
t RB q
t’RB
t RB q q’
t’RB
w1 odd w2 w1 odd w2
odd odd
vBR vBR
v’GB v’GB
CB CG CB CG
Lemma 6. Let (H, ΣH ) be the graph defined in Lemma 5. There are three dis-
tinct odd paths F1 , F2 , F3 from tRB to t0RB .
Proof. Suppose for a contradiction this is not the case and we have Fi with
no internal vertices in common with (K, ΣK ), see Fig. 6. Consider the graph
obtained from (H, ΣH ) by deleting ē = (tRB , t0RB ) and all edges which are not
f5 :
edges of (K, ΣK ) or edges of Fi . The following sequence of operations yields K
t RB q
Fi
odd
e
t’RB
CR
vRB vRG = q’ P’B
w1 odd w2
odd
vBR v’GB
CB CG
Let (H̄, ΣH̄ ) be the graph obtained by deleting from (H, ΣH ) all the edges
which are not edges of CR , CB , CG and not edges of PR0 , PB0 and PG0 . Because of
Lemma 7 we can define fi , for i = 1, 2, 3, to be the first internal vertex of Fi ,
starting from tRB , which is also a vertex of (H̄, ΣH̄ ). By symmetry (see Fig. 4)
there is a vertex a vertex t0RG of PG0 (tRG , vRG ) which is incident to tRG and there
are odd paths F10 , F20 , F30 between tRG and t0RG . As previously we can define fi0 ,
for i = 1, 2, 3, to be the first internal vertex of Fi0 , starting from tRG , which is
also a vertex of (H̄, ΣH̄ ).
The remainder of the proof is a case analysis which shows that for each
possible set of vertices f1 , f2 , f3 and f10 , f20 , f30 the graph (H, ΣH ) contains a
f5 minor. In order to prove Lemma 5 and to make the case analysis tractable
K
we first establish general results for labeled graphs with properties (P1) and (P2).
References
Grigor Gasparyan
1 Introduction
Suppose we are given two n × n {0, 1} matrices A and B, and a full support
vector d. Let us call the pair of matrices (A, B) a (bipartite) d-design if
AT B = J + diag(d),
where J is the matrix filled with ones. It seems difficult to say anything about
the structure of the matrices A and B in such a general setting. But if d > 0
then a surprising result of Lehman [7] asserts that either
01
A=B∼ = DPP ≡
1I
(then we call the pair (A, B) a DPP-design), or for some r and s:
AJ = JA = rJ; BJ = JB = sJ; AT B = BAT = J + (rs − n)I
(then we call the pair (A, B) an (r, s)-design). This result generalizes the earlier
results of de Bruijn and Erdős [2] and Ryser [12], and it is one of the main
arguments in the proof of Lehman’s theorem on minimally non-ideal polyhedra
[8].
In this paper we would like to investigate the d-designs a bit more generally.
Our main goal is to find sufficient conditions which force a d-design to become
an (r, s)-design. The following theorem summarizes our results in that direction:
Pn
Definition 3. Let (A, B) be a d-design. If 1 + i=1 d−1 i = 0 then we call such a
design singular. The ith row of A (B) we call a d-row if ai. d−1 = 0 (bi. d−1 = 0).
Let P be a polyhedron. We say that P is vertex {0, 1} if all its vertices are
{0, 1} vectors. We say that P is facet {0, 1} if it can be given with the help
of {0, 1} constraints. We call P a {0, 1}-polyhedron if it is both vertex {0, 1}
and facet {0, 1}. P/j denotes the orthogonal projection of P on the hyperplane
xj = 0, and P \j denotes the intersection of P with the hyperplane xj = 0. The
first operation is called contraction and the second one deletion of the coordinate
j. A polyhedron P 0 is called a minor of P if it can be obtained from P by
successively deletion or contraction one or several coordinates.
For an m × n {0, 1} matrix A, we denote by P≤ (A) = {x ∈ Rn : Ax ≤
1; x ≥ 0} the set packing polytope (SP-polytope) and by P≥ (A) = {x ∈ Rn :
Ax ≥ 1; x ≥ 0} the set covering polyhedron (SC-polyhedron) associated with A.
A {0, 1} SP-polytope is called perfect, and a {0, 1} SC-polyhedron is called
ideal. A SP-polytope P is called minimally imperfect if it is not perfect, but all
its minors are perfect. A minimally non-ideal polyhedron is defined similarly.
It is easy to see that P≥ (DPP) is a minimally non-ideal polyhedron.
For more information on polyhedral combinatorics we refer to Schrijver [13].
If G = (V, E) is a graph, then n = n(G) denotes the number of vertices of G;
ω = ω(G) denotes the cardinality of a maximum clique of G; α = α(G) denotes
the cardinality of a maximum stable set; and χ = χ(G) denotes the chromatic
number of G. A k-clique or k-stable set will mean a clique or stable set of size
26 Grigor Gasparyan
There are several ways to associate a combinatorial structure to a d-design (A, B).
A straightforward way to do it is to take two set systems A = {A1 , . . . , An } and
B = {B1 , . . . , Bn } on some ground set V = {v1 , . . . , vn } such that the matri-
ces A and B are (point-set) incidence matrices of A and B, respectively. Then
the pair of set systems (A, B) have the following property: for each 1 ≤ i, j ≤
n, |Ai ∩ Bj | = 1 + eij di . We call such a pair of set systems a d-design. In par-
ticular, it was proved by Padberg [11] (see also [3]) that the pair of set systems
of ω-cliques and α-stable sets of an (α, ω)-graph is an (α, ω)-design. Another
interesting special case is when A = B. It was proved by de Bruijn and Erdős
[2] that (A, A) is a d-design iff AT is a (may by degenerated) projective plane.
A d-design can be characterized with the help of just one set system AT .
Then the ith column of B can be interpreted as an incidence vector of a set
subsystem of AT , which contains all the points except Ai by exactly once and Ai
by exactly di +1 times. We call such a set system a d-hypergraph. A d-hypergraph
corresponding to a (r, s)-design we call an (r, s)-hypergraph. In particular, −1-
hypergraph is a hypergraph having equal number of edges and vertices such
that for each vertex v, V \v can be partitioned with the help of its edges. We
will show that a −1-hypergraph is an (α, ω)-hypergraph, which corresponds to
the ω-clique hypergraph of some (α, ω)-graph.
An interesting special case is when AT is 2-uniform, i.e. it is a graph. A
nonsingular d-design (A, B) we call a G-design, if A is 2-regular. A graph G we
call a d-graph if there exists a G-design (A, B) such that A is the (edge-vertex)
incidence matrix of G. If G is an odd cycle, then we call (A, B) a C-design.
Let G be a d-graph. Then it is not difficult to show that, for each 1 ≤ i ≤ n,
di = ±1 (see Lemma 9). Denote by G\v (G/v) the graph obtained from G after
deleting (duplicating) the vertex v. It is easy to see that, for each vertex v, either
G\v or G/v has a perfect matching. Call such a graph matchable. The following
lemma characterizes d-graphs:
Bipartite Designs 27
Proof. We will prove by induction on the number of vertices. Suppose the theo-
rem is true for the graphs having less than n vertices and G is a d -graph with n
vertices. Then, clearly, G is connected, has equal number of edges and vertices,
and odd number of vertices. Hence G has exactly one cycle, which is odd, as the
(edge-vertex) incidence matrix of G is nonsingular. Furthermore, if v1 is a leaf of
G, and v1 v2 ∈ E(G), then G\{v1 ; v2 } is matchable. Indeed, for each v 6= v1 , v2 ,
the perfect matching of G\v (or G/v) must contain the edge v1 v2 . Hence after
deleting the edge v1 v2 from the matching, it will be a perfect matching for G\v
(or G/v). It follows that either v2 has degree 2, or it is a vertex of the cycle and
has degree 3.
Let v3 6= v1 such that v3 v2 ∈ E. Now if v2 has degree two then G\{v1 ; v2 } is a
d-graph. Hence by induction hypothesis, the distance from each not degree two
vertex v 6= v1 ; v3 to the cycle is even. If v1 is the unique leaf of G nonadjacent
to the cycle, then the degree of v3 in G\{v1 ; v2 } is one, hence the distances from
v1 and v3 to the cycle are also even. If v4 6= v1 is a leaf nonadjacent to the cycle
and v4 v5 ∈ E then, by induction hypothesis, G\{v4 ; v5 } and G\{v1 ; v2 ; v4 ; v5 }
are a d-graphs, hence the distances from v1 and v3 to the cycle are again even.
If G has no leafs then it is an odd cycle and we have nothing to prove. Suppose
G has leafs, but all of them are adjacent to the cycle. Then it is easy to see that G
has exactly two leafs, the neighbors of which are adjacent vertices in the cycle.
Denote by V1 the set of vertices of G such that G\v has a perfect matching
and by V2 = V \V1 . Then it is easy to see that G/v has a perfect matching iff
v ∈ V2 and |V1 | = |V2 | + 1. Now if (A, B) is a d-design corresponding to G, then
d−1 · 1 =|V1 | − |V2 | = −1, a contradiction.
The sufficiency of the condition is proved by similar arguments.
4 De Bruijn-Erdős’s Matrices
In this section we summarize the information about DE-matrices, which we use
in this paper.
Proof. Delete all one rows and columns and apply Lemma 2.
Lemma 4. Let A and A0 be DE-matrices, where a.1 6=a0 .1 and a.j = a0 .j , 1 <
j ≤ n. Then either A or A0 has an all one column.
Proof. Indeed, if say ai1 = 1 and a0i1 = 0, then ai. = 1T . Hence by Lemma 3, A
has also an all 1 column.
Proof. If (1 − b.i ) · (1 − b.j ) 6= 0, then there exists an index k such that bki =
bkj = 0, hence 1 · b.j = bk. 1 = 1 · b.i . As J − B is connected, it follows that
JB = sJ, for some integer s. Since B has no all 1 column, and it is a DE-matrix,
it cannot have an all 1 row. Hence B is totally s-regular.
The following result, which has been extracted by Sebő [14] from Lehman [8]
(see also [15] and [10]), is one of our key arguments in the proof of Theorem 13.
Denote by A∗ the set of all the solutions of AT x = 1, and by A01 the set of all
{0, 1} vectors in A∗ .
then A is a DE-matrix.
Bipartite Designs 29
Proof. Let Bi ⊆ (A/i)01 be a matrix such that the equation Bi y = x/i has a
unique solution. As x/i has full support, Bi has no all zero row.
Suppose aij = 0, L = {l : alj = 1} and Bi0 is the submatrix of Bi induced by
the rows L. Then all the columns of Bi0 have exactly one 1. Thus we have:
The next important result of Lehman [8] will be used to prove Theorem 12.
Theorem 4 ([8]). Let A be an n × m {0, 1} matrix having full row rank and
no all one or all zero or equal columns. If the vector x ∈ A∗ has full support,
and for each i, affine hull (A/i) can be given with the help of {0, 1} constraints,
then A is a DE-matrix.
5 A Lemma on Matrices
The following lemma contains our main argument from linear algebra. Though
we need just a very special case of the lemma, we would like to state it in general
form, for the sake of possible other applications.
Suppose A, B, D ∈ R n×n ; U, W ∈ R n×m , where D is nonsingular and U
(or W ) has full column rank.
AT B = D + U W T ⇔ BD−1 AT = I + X∆−1 Y T ,
Proof. Denote by
∆T U T −∆ −W T −∆ 0
F = ;E = ; D0 = ;
Y A X B 0 D
Notice that if the inverse of the matrix D is easy to compute, then Lemma
6 reduces the singularity test of the n × n matrix D + U W T to the singularity
test of an m × m matrix ∆.
Taking m = 1, U = W = 1 and D = diag(d) we get:
It follows that Pn if ai. is a−1d-row of a nonsingular d-design (A, B), then for
each k ≤ n, j=1 aij bkj dj = eik . On the other hand, if for some i and
Pn −1
k, j=1 a ij b kj dj = e ik , or, in particular, i 6= k and ai. · bk. = 0, then ei-
ther ai. or bk. is a d-row.
The following simple lemma will also be useful in the sequel.
Proof. If one of the sets has λ elements, then all the other sets contain this one
and are disjoint otherwise. It follows that m ≤ n. Hence we may suppose that
di = |Ai | − λ > 0. Then AT A =diag(d) + λJ. Since λd−1 · 1 6= −1, m ≤ rk
A ≤ n.
The following interesting fact also can be easily deduced from Lemma 6.
Theorem 7 ([12]). In any square design, there exists a set incident to each
given pair of points.
The following theorem completely characterizes the d-designs (A, B), where J −
A is disconnected (the proof is omitted).
1.
100 100
(A, B) ∼
= 1 1 0 , 1 0 1 ;
101 110
2.
1 eT1 1 0
(A, B) ∼
= , ;
1J −I e1 I
3.
0 1 1 101
(A, B) ∼
= 1 J − I J , 0 I 0 ;
1 0 I 00I
4.
1011 1100
0 0 1 1 0 0 0 1
(A, B) ∼
=
1 1 0 0 , 1 0 0 0 .
1101 0011
32 Grigor Gasparyan
Proof. Suppose (A, B) is not an (r, s)-design. Then by Lemma 9 and Theorem
9, for each j, either dj = −1 or dj ≥ r − 1, and by Theorem 9, either A or B
has a d-row. Consider two cases:
Case 1: a1. is a d-row. Now, it follows from Lemma 7 that for each i 6= 1,
either a1. · bi. = 0 or a1. ≤ bi. . As B has no equal columns, it follows that r = 2,
dj = ±1, hence (A, B) is a G-design.
Case 2: b1. is a d-row having maximum number of ones.
Suppose b1. = (1 . . . 1, 0 . . . 0), where b1. 1 = k. Then we have that for each
i 6= 1, either ai. · b1. = 0 or ai. · b1. = r. Moreover, a1. · b1. = r − 1. It follows
that r ≤ k < n. Suppose ai. · b1. = r if 1 < i ≤ l, ai. · b1. = 0 if i ≥ l, and
a1k+1 = 1. Denote by A1 = A[l+1 . . . n; k+1 . . . n], B1 = B[l+1 . . . n; k+1 . . . n].
As A isPnonsingular, l P ≥ k. On the other hand, AT1 B1 =diag(dk+1 . . . dn ) + J,
where j=k+1 dj = j=1 d−1
−1
n n
j 6= −1, hence k ≥ l. It follows that k = l and
A1 is nonsingular. Hence the equation AT1 x = 1 − e1 has a unique solution.
As all the columns of B 0 = B[k + 1 . . . n; 1 . . . k] satisfy that equation, B 0 has
an all
Pnone row. Suppose bp. is the row of B corresponding to that row of B 0 .
−1
As j=1 a2j bpj dj = 0, bp. is a d-row having more ones than b1. , which is a
contradiction.
Notice that only Lemma 8 and Theorem 8 yet contain some information
about the structure of singular designs. The characterization of singular designs
seems to be a more difficult problem, as Lemma 6 cannot be applied directly.
In particular, it would be interesting to check whether there exist singular d-
designs (A, B), where A is r-regular, and r > 2. A partial answer to this question
is given in [14]. Here is another result on that direction. The prove is similar to
the proof of Theorem 10.
In this section we apply Theorem 9 to get some new, smaller sets of conditions
characterizing (α, ω)-graphs. It is not difficult to deduce from Theorem 9 (see
[3]) that G is an (α, ω)-graph iff it has a family of n cliques A and a family
of n stable sets B such that AT B = J − I. The following reformulation of this
statement is a strengthening of a similar result of Hougardy and Gurvich [6].
Theorem 11 ([4]). G is an (α, ω)-graph iff it has an α-stable set A1 such that
for each vertex s ∈ A1 and stable set S ⊂ V ; χ(G\s) = ω = ω(G\S).
34 Grigor Gasparyan
Notice that Theorem 11 immediately implies Theorem 2 and all the proper-
ties of minimal imperfect graphs shown by Padberg [11].
From the proof of Theorem 11 we get:
Proof. Let B be the matrix the ith column of which is the incidence vector of a
q-clique disjoint from the stable set corresponding to the ith column of A. Then
1T AT B1 ≥ pqn, hence n = pq + 1 and AT B = J − I.
The following two theorems contain both Padberg’s theorem on minimally im-
perfect polytopes [11] and Lehman’s theorem on minimally non-ideal polyhedra
[8], and the second one also contains the part of Sebő [14], which corresponds to
nonsingular matrix equations. In the proofs we mainly use the ideas of Lehman
[8], Padberg [10], several results on d-designs of the present work and the follow-
ing simple but surprising fact communicated by Sebő [14]: if P is a facet {0, 1}
polyhedron such that, for each i ≤ n, both P \i and P/i are {0, 1}-polyhedra then
P is full dimensional.
(A, B) the d-design corresponding to F , then the following cases are possible:
1. Either (A, B) is a DPP-design or
∼ 01 11
(A, B) = , ;
1I 0I
References
1. R. S. Bose. A note on Fisher’s inequality for balanced incomplete block design.
Ann. Math. Stat., 20:619–620, 1949.
2. N. G. de Bruijn and P. Erdős. On a combinatorial problem. Indag. Math., 10:421–
423, 1948.
3. V. Chvátal, R. L. Graham, A. F. Perold, and S. H. Whitesides. Combinatorial
designs related to the strong perfect graph conjecture. Discrete Math., 26:83–92,
1979.
4. G. S. Gasparyan. Minimal imperfect graphs: A simple approach. Combinatorica,
16(2):209–212, 1996.
5. G. S. Gasparyan and A. Sebő. Matrix equations in polyhedral combinatorics. In
preparation.
6. S. Hougardy and V. Gurvich. Partitionable Graphs. Working paper.
7. A. Lehman. No the width-length inequality. Math. Programming, 17:403–413, 1979.
36 Grigor Gasparyan
?
András Sebő
1 Introduction
This paper is organized as follows: Section 2 states the main result, its corollaries,
and reformulations. The proof of the main result is provided in sections 3 and
4. Section 5 is devoted to some more examples and other comments.
2 Results
When this does not cause missunderstanding, we will occasionnally use the
shorter notations P ≤ := P ≤ (A≤ ), P ≥ := P ≥ (A≥ ), P := P (A≤ , A≥ ) = P ≤ ∩P ≥ .
≤ ≥
Recall that the polyhedra P ≤ (A0 ) := P ≤ \ I/J and P ≥ (A0 ) := P ≥ \ I/J,
(I, J ⊆ V := {1, . . . , n}, I ∩ J = ∅) are called corresponding minors, and
≤ ≥
(A0 , A0 ) =: (A≤ , A≥ ) \ I/J is a minor of (A≤ , A≥ ). (Note that two minors are
corresponding if and only if the two I ∪ J are the same, since for set-packing
polyhedra deletion is the same as contraction.) Furthermore, if for all such I, J
the polyhedron (P ≤ (A≤ ) \ I/J) ∩ (P ≥ (A≥ ) \ I/J) is integer, then the system
(A≤ , A≥ ) will be called fully integer.
≤
– A0 is a minimal nongraph clutter, or it is partitionable with µ = 0, moreover
≤ ≥
in either case the regular vertex of P ≤ (A0 ) is in P ≥ (A0 ), and it is the
≤ 0≤ ≥ 0≥
unique packing type fractional vertex of P (A ) ∩ P (A ).
– A0 ≥ is a degenerate projective plane, or it is partitionable with µ ≥ 2, more-
≥ ≤
over in either case the regular vertex of P ≥ (A0 ) is in P ≤ (A0 ), and it is
≤ ≥
the unique covering type fractional vertex of P ≤ (A0 ) ∩ P ≥ (A0 ).
0≤ 0≥
– (A , A ) is a mixed odd circuit.
Lovász’s NP-characterization of imperfect graphs [8] (with the additional
properties proved by Padberg[10]), follow:
Corollary 1. Let A≤ be a 0–1-matrix with n columns. Then A≤ is imperfect
≤
if and only if it has either a minimal nongraph or a partitionable minor A0 ,
≤
moreover P (A0 ) has a unique fractional vertex.
Specializing Theorem 1 to set-covering polyhedra one gets Lehman’s celebrated
result [6], see also Seymour [12]:
Corollary 2. Let A≥ be a 0–1-matrix with n columns. Then A≥ is nonideal if
and only if it has either a degenerate projective plane or a partitionable minor
≥ ≥
A0 , moreover P (A0 ) has a unique fractional vertex.
The following two consequences are stated in a form helpful for coNP char-
acterization theorems (see Section 5):
Corollary 3. Let A≤ and A≥ be 0–1-matrices with n columns. Then (A≤ , A≥ )
is not fully integer if and only if at least one of the following statements holds:
– A≤ has a minimal nongraph or a partitionable, furthermore minimal imper-
fect minor with its regular vertex in the corresponding minor of P ≥ (A≥ ),
– A≥ has a degenerate projective plane or a partitionable minor with its regular
≤ ≤
vertex in the corresponding minor P ≤ (A0 ) of P ≤ (A≤ ), where A0 is perfect.
– (A≤ , A≥ ) has a mixed odd circuit minor.
If we concentrate on the structural properties of the matrices A≤ and A≥ implied
by the existence of a fractional vertex we get the following.This statement is not
reversible: if A≤ consists of the maximal stable-sets of an odd antihole, and A≥
of one maximal but not maximum stable-set, then (A≤ , A≥ ) is fully integer,
although A≤ is minimal imperfect !
Note the asymmetry between ‘minimal imperfect’ in the first, and ‘partitionable’
in the second case (for an explanation see 5.2).
The results certainly provide a coNP characterization in the following case:
Characterizing Noninteger Polyhedra with 0–1 Constraints 43
– P is noninteger, and
– P ∩ {x ∈ IRn : xi = 0}(= P ≤ ∩ {x ∈ IRn : xi = 0} ∩ P ≥ ∩ {x ∈ IRn : xi = 0})
is an integer polyhedron for all i ∈ V , and
– P has the sandwich property.
44 András Sebő
Note that Theorem 2 sharpens Theorem 1 in two directions: first, the con-
straint of Theorem 2 does not speak about all minors, but only about the dele-
tion and contraction of elements; second, the integrality after the contraction of
elements is replaced by the sandwich property.
The corollaries about combinatorial and polyhedral minimal nonintegrality
satisfy the condition of Theorem 2 for two distinct reasons. In the combinatorial
case simplicity does not necessarily hold, but deleting the certain equalities from
A≥ , the system remains combinatorially minimal noninteger (see 5.2).
Corollary 6. If (A≤ , A≥ ) is combinatorially minimal noninteger, then at least
one of the following statements holds:
– A≤ is a minimal nongraph or a partitionable clutter with µ = 0, furthermore
it is minimal imperfect, and the regular vertex of P ≤ (A≤ ) is the unique
packing type fractional vertex of P ≤ (A≤ ) ∩ P ≥ (A≥ ).
– A≥ is a degenerate projective plane, or a partitionable clutter with µ ≥ 2,
while A≤ is perfect, and the regular vertex of P ≥ (A≥ ) is in P ≤ (A≤ ).
– (A≤ , A≥ ) is a mixed odd circuit, and 1/21 is its unique fractional vertex.
This easily implies Theorem 1 and its corollaries using the following remark.
(it is particularly close to Corollary 3), while the next corollary does not have
similar consequences. This relies on the following:
– If P is noninteger, (A≤ , A≥ ) does contain a combinatorially minimal nonin-
teger minor. (Proof: In both P ≤ and P ≥ delete and contract elements so that
the intersection is still noninteger. Since the result has still 0–1 constraints
this can be applied successively until arriving at a combinatorially minimal
noninteger system.)
– If P is noninteger, one does not necessarily arrive at a polyhedrally minimal
noninteger polyhedron with deletions and restrictions of variables. (Coun-
terexample: Example 1.)
Gasparyan [4] has deduced this statement by proving that in the polyhedral
minimal case the matrices involved in the matrix equations are nonsingular (see
comments concerning nonsingularity in Example 1).
The main frame of the present paper tries to mix (the polar of) Lehman’s
polyhedral and Padberg’s matricial approaches so as to arrive at the simplest
possible proof. Lemmas 1–4 and Lemma 7 are more polyhedral, Lemma 5,
Lemma 6 and Lemma 8 are matricial and combinatorial. When specializing
these to ideal clutters, their most difficult parts fall out and quite short variants
of proofs of Lehman’s or Padberg’s theorem are at hand.
Remark 2. Compare Lemma 1 with Fonlupt, Sebő [2]: a graph is perfect if and
only if the linear rank of the maximum cliques (as vertex-sets) in every induced
subgraph is at most n − ω + 1 where ω is the size of the maximum clique in the
subgraph; the equality holds if and only if the subgraph is uniquely colorable.
We note and use in the sequel without reference that if P is minimal non-
integer, then w > 0 for all fractional vertices w of P (wi = 0 would imply that
(P ≤ \ i) ∩ (P ≥ \ i) is also noninteger).
In sections 3 and 4 I will denote the identity matrix, J the all 1 matrix
of appropriate dimensions;
A is called r-regular, if 1A = r1, and r-uniform if
A1 = r1; Ac := V \ A : A ∈ A . A is said to be connected if V cannot be
partitioned into two nonempty classes so that every A ∈ A is a subset of one of
the two classes. There is a unique way of partitioning A and V into the connected
components of A.
Lemma 2. If (A≤ , A≥ ) is minimal noninteger, w is a fractional vertex of P :=
P (A≤ , A≥ ), and A ⊆ Aw is a set of n linearly independent members of Aw ,
then every connected component K of Ac is n − rK -regular and n − rK -uniform
(rK ∈ IN), and r(A − v) = n − dA (v).
Proof. Recall that w > 0. If P is minimal noninteger, then for arbitrary i ∈ V the
i
sandwich property provides us Qi ⊆ IRV \{v} , wi ∈ P ≤ (A≤ )∩P ≥ (A≥ ) ⊆ Qi ⊆
i i
P ≤ (A≤ ) ∩ P ≥ (A≥ ) , that is, wi ∈ Qi and wi > 0. Applying the inequality in
Lemma 1 to Qi and wi , and using the trivialbut crucial fact that Awi (Qi ) ⊇ A−i,
we get the inequality r(A − i) ≤ n − max |A| : A ∈ A − i .
On the other hand, r(A) = n by assumption. One can now finish in a few
lines like Conway proves de Bruijn and Erdős’s theorem [7], which is actually
the same as Seymour [12, Lemma 3.2]:
Let H := Ac for the simplicity of the notation. What we have proved so far
translates as dH (v) ≤ |H| for all v ∈ H ∈ H. But then,
X X X X X X X
n= 1= 1/|H| = 1/|H| = dH (v)/|H| ≤ 1,
H∈H H∈H v∈H v∈V H∈H,v∈H v∈V v∈V
Remark 3. The situation of the above proof will be still repeated several times:
when applying Lemma 1, the 0–1 vectors that have an important auxiliary role
for bounding the rank of some sets are in Bw (Qi ), and are not necessarily vertices
Characterizing Noninteger Polyhedra with 0–1 Constraints 47
of P . The reader can check on mixed odd circuits that the neighbors B =
{B1 , . . . , Bn } of 1/21 are not suitable for the same task (unlike in the special
cases): the combinatorial ways that use B had to be replaced by this more general
polyhedral argument. Watch for the same technique in Lemma 7 !
The next lemma synthesizes two similar proofs occurring in the special cases:
The following lemma extracts and adapts to our needs well-known statements
from Lehman’s, Seymour’s and Padberg’s works, and reorganizes these into one
statement. It can also be deduced by combining results of Gasparyan [4], which
investigate combinatorial properties implied by matrix equations. For instance
the connectivity property of Lemma 6 below is stated in [4] in a general self-
contained combinatorial setting.
Lemma 6. If P is minimal noninteger, and w ∈ P is a fractional vertex of P ,
then A = A(w) is nonsingular and connected , moreover,
Proof. (Sketch) If Ac has at least two components, then any two sets whose
complements are in different components cover V . This, and the matrix equation
of Lemma 5 determine a degenerate combinatorial structure. (For instance one
can immediately see that the associate of a third set has cardinality at most two,
and it follows that all but at most one members of B have at most two elements.)
If Ac has one component,then the uniformity and regularity of Ac claimed
by Lemma 2 implies that of A. t
u
Check the statement for the mixed C7 of Example 1 ! (It can also be instructive
to follow the proof on this example. )
5 Comments
5.1 Further Examples
A system (A≤ , A≥ ) for which a P (A≤ , A≥ ) ⊆ IR5 is integer, but (A≤ , A≥ ) is
not fully integer: the rows of A≤ are (1, 1, 0, 0, 0), (0, 1, 1, 0, 0), (1, 0, 1, 0, 0) and
(0, 0, 1, 1, 1); A≥ consists of only one row, (0, 0, 0, 1, 1).
We mention that a class of minimal noninteger simple systems (A≤ , A≥ ) with
the property that (A≤ , A≥ ) \ i (i ∈ V ) defines an integer, but not always fully
integer polyhedron, can be defined with the help of ‘circular’ minimal imperfect
and minimal nonideal systems (see Cornuéjols and Novick [1]): define A≤ := Cnr ,
A≥ := Cns , where r ≤ s and A≤ is minimal imperfect, A≥ is minimal nonideal.
Such examples do not have mixed vertices, so they also show that the first
two cases of our results can both occur in the same polyhedron.
Acknowledgments
I am thankful to Grigor Gasparyan and Myriam Preissmann for many valuable
comments. Furthermore, I feel lucky to have learnt Lehman’s results and espe-
cially to have heard the main ideas of Padberg’s work from Grigor Gasparyan.
I would like to thank András Frank for comparing a lemma in [12] concerning
ideal matrices to Erdős and de Bruijn’s theorem: this helped me getting closer
to ideal matrices and strengthened my belief in a common generalization (a
particular case of Fisher’s inequality is implicit in proofs for minimal imperfect
graphs as well, see [3]).
Last but not least I am indebted to Kazuo and Tomo Murota for their mirac-
ulous help of various nature: due to them, it was possible to convert an extended
abstract to a paper during five jet-lag-days.
References
1. G. Cornuéjols and B. Novick. Ideal 0–1 matrices. J. of Comb. Theory B, 60(1):145–
157, 1994.
2. J. Fonlupt and A. Sebő. The clique rank and the coloration of perfect graphs. In
R. Kannan and W. Pulleyblank, editors, Integer Programming and Combinatorial
Optimization I. University of Waterloo Press, 1990.
3. G. Gasparyan. Minimal imperfect graphs: A simple approach. Combinatorica,
16(2):209–212, 1996.
4. G. Gasparyan. Bipartite designs. In R. E. Bixby, E. A. Boyd, and R. Z. Rı́os-
Mercado, editors, Integer Programming and Combinatorial Optimization: Proceed-
ings of the 6th International Conference on Integer Programming and Combinato-
rial Optimization, LNCS, Vol. 1412, pages 23–35. Springer, 1998. This volume.
5. G. Gasparyan and A. Sebő. Matrix equations in polyhedral combinatorics. 1998.
In preparation.
6. A. Lehman. The width-length inequality and degenerate projective planes. In
W. Cook and P. D. Seymour, editors, Polyhedral Combinatorics, DIMACS, Vol. 1,
pages 101–105, 1990.
7. J. H. van Lint and R. M. Wilson. A Course in Combinatorics. Cambridge Univer-
sity Press, 1992.
8. L. Lovász. A characterization of perfect graphs. J. of Comb. Theory B, 13:95–98,
1972.
9. M. Padberg. Perfect zero-one matrices. Math. Programming, 6:180–196, 1974.
10. M. Padberg. Lehman’s forbidden minor characterization of ideal 0–1 matrices.
Discrete Mathematics, 111:409–420, 1993.
11. A. Schrijver. Theory of Linear and Integer Programming. Wiley, 1986.
12. P. D. Seymour. On Lehman’s width-length characterization. In Polyhedral Combi-
natorics, DIMACS, Vol. 1, pages 107–117, 1990.
A Theorem of Truemper
?
Michele Conforti and Ajai Kapoor
1 Truemper’s Theorem
Let β be a 0,1 vector indexed by the chordless cycles of an undirected graph
G = (V, E). G is β-balanceable if its edges can be labelled with labels 0 and 1
such that l(C) ≡ βC mod 2Pfor every chordless cycle C of G, where l(e) is the
label of edge e and l(C) = e∈E(C) l(e).
We denote by β H the restriction of the vector β to the chordless cycles of an
induced subgraph H of G.
In [14] Truemper showed the following theorem:
Theorem 1. A graph G is β-balanceable if and only if every induced subgraph
H of type (a), (b), (c) and (d) (Figure 1) is β H -balanceable.
Graphs of type (a), (b) or (c) are referred to as 3-path configurations (3P C’s).
A graph of type (a) is called a 3P C(x, y) where node x and node y are connected
by three internally disjoint paths P1 , P2 and P3 . A graph of type (b) is called
a 3P C(xyz, u), where xyz is a triangle and P1 , P2 and P3 are three internally
disjoint paths with endnodes x, y and z respectively and a common endnode
u. A graph of type (c) is called a 3P C(xyz, uvw), consists of two node disjoint
triangles xyz and uvw and disjoint paths P1 , P2 and P3 with endnodes x and
u, y and v and z and w respectively. In all three cases the nodes of Pi ∪ Pj
i 6= j induce a chordless cycle. This implies that all paths P1 , P2 , P3 of (a) have
length greater than one. Graphs of type (d) are wheels (H, x). These consist of a
chordless cycle H called the rim together with a node x called the center, that
has at least three neighbors on the cycle. Note that a graph of type (b) may also
be a wheel.
?
Supported in part by a grant from Gruppo Nazionale Delle Ricerche-CNR.
Assume G is connected and contains a clique cutset Kl with l nodes and let
G01 , G02 , . . . , G0n be the components of the subgraph induced by V (G) \ Kl . The
blocks of G are the subgraphs Gi induced by V (G0i ) ∪ Kl , i = 1, . . . , n.
Proof: The ”only if” part is obvious. We prove the ”if” statement when G has
a K2 cutset {u, v}, since the other case is again immediate. All blocks have a
β-balancing in which edge uv has the same label, since all blocks Gi are β Gi -
balanceable and we can always scale on a cut of Gi separating u and v. The
A Theorem of Truemper 55
in T and vi is chosen so that amongst all nodes in N (v) \ {v0 , . . . , vi−1 } the
path between nodes v and vi is shortest in the subgraph of G with edge set
E(Gv ) ∪ {vv0 , . . . , vvi−1 }. Now place first the edges of T , then the other edges
of Gv in a consistent ordering with respect to T \ {v}, then vv1 , . . . , vvk . This
ordering is a consistent ordering for G and the signing algorithm can be applied
to produce from the β-balancing of Gv , a β-balancing of G. 2
Proof: Let G00 be the subgraph of G0 , induced by V (G0 ) \ V (C). If G00 is a single
node, say u, and u has only two neighbors ci and cj in C, then ci and cj are
nonadjacent and G0 is a 3P C(ci , cj ). Otherwise G0 is a wheel with u as center.
If G00 contains more than one node, by 3) we have that G00 is connected and
that:
4) Every node of G00 has at most two neighbors in C and these two neighbors
are adjacent.
5) G00 contains at most one pair of nodes, say x1 and xn such that both x1 and
xn have neighbors in C and (N (x1 ) ∪ N (xn )) ∩ V (C) either contains at least
three nodes or two nonadjacent nodes.
(Indeed by 3), we have that G00 is connected. So if G00 contains more that one
such pair, let x1 , xn be chosen satisfying 5) and closest in G00 . Let P = x1 , . . . , xn
be a shortest path in G00 connecting them. The subgraph G∗ of G, induced by
V (C) ∪ V (P ) satisfies 1) and 2). Then if more that one such pair exists, G∗ is a
proper subgraph of G0 and this contradicts 3).)
Let C = c1 , . . . , cm and assume first that G00 contains one pair of nodes, x1 ,
xn satisfying 5). Then by 3), G00 is a path P = x1 , . . . , xn . If a node of C, say
ci , is adjacent to a node xi , 1 < i < n of P , then by 3) and 4), x1 is adjacent to
ci−1 , possibly to ci and no other node of C. Node xn is adjacent to ci+1 , possibly
to ci (indices modm) and no other node of C. Therefore no other node of C is
adjacent to an intermediate node of P . In this case, G0 is a wheel with center ci .
If no node of C is adjacent to an intermediate node of P , then by 4) we can
assume w.l.o.g. that x1 is adjacent to ci−1 and possibly ci and xn is adjacent to
cj+1 and possibly cj . If x1 or xn has two neighbors in C and i = j, then G0 is a
wheel with center ci . In the remaining cases G0 is a 3-path configuration.
If G00 contains no pair of nodes satisfying 5), by 1) and 4) we have that C is
a triangle c1 , c2 , c3 , all three nodes of C have neighbors in G00 and no node of G00
has more than one neighbor in C. If G00 is a chordless path P = x1 , . . . , xn with
A Theorem of Truemper 57
x1 adjacent to, say c1 and xn adjacent to c2 , then c3 has some neighbor in P and
G0 is a wheel with center c3 . Otherwise let P12 be a shortest path connecting c1
and c2 and whose intermediate nodes are in G00 . If c3 has a neighbor in P12 we
have a wheel with center c3 . Otherwise let P3 be a shortest path connecting c3
and V (P12 ) \ {c1 , c2 } and whose intermediate nodes are in G00 . By 3), G0 is made
up by C, together with P12 and P3 , furthermore P3 meets P12 either in a node
x or in two adjacent nodes t1 , t2 . In the first case, we have a 3P C(c1 c2 c3 , x),
otherwise we have a 3P C(c1 c2 c3 , t1 t2 t3 ). 2
For e ∈ E(G), Ge denotes the graph whose node set represents the chordless
cycles of G containing e and whose edges are the pairs C1 , C2 in V (Ge ), such
that C1 and C2 belong to a 3-path configuration or a wheel.
Proof: Assume not. Let Ge1 and Ge2 be two components of Ge . Let Gi be the
subgraph of G induced by the node set ∪C∈Gei V (C), for i = 1, 2.
Assume first that {u, v} is a K2 cutset separating G1 from G2 in the graph
induced by V (G1 ) ∪ V (G2 ). Pick C1 ∈ Ge1 and C2 ∈ Ge2 and a path P in G such
that in the subgraph G0 of G induced by V (C1 ) ∪ V (C2 ) ∪ V (P ), {u, v} is not
a K2 cutset and C1 , C2 and P are chosen so that |P | is minimized. (Note that
P exists since {u, v} is not a K2 cutset of G). Then by the minimality of P , no
node of P is contained in a chordless cycle containing edge e. By Lemma 6, C1
is a chordless cycle in a 3-path configuration or wheel H, contained in G0 . Since
any edge in a 3-path configuration or wheel is contained in two chordless cycles,
V (C1 ) ∪ V (C2 ) ⊆ V (H). But then C1 C2 is an edge of Ge , a contradiction.
So {u, v} is not a K2 cutset in the graph induced by V (G1 ) ∪ V (G2 ). Let
C2 ∈ Ge2 , such that for some C ∈ Ge1 , {u, v} is not a K2 cutset in the graph
induced by V (C) ∪ V (C2 ). Let C2 be u = v1 , . . . , vm = v. Let v C be the node of
lowest index in V (C2 ) \ V (C) and let SC be the component of the graph induced
by V (C2 )\V (C) containing node v C . Amongst all C ∈ Ge1 such that {u, v} is not
a K2 cutset in the graph induced by V (C) ∪ V (C2 ), let C1 be the chordless cycle
for which the node v C1 has the highest index and with respect to that |SC1 | is
smallest possible. By Lemma 6, C1 is a chordless cycle of a 3-path configuration
or wheel H contained in V (C1 ) ∪ V (SC1 ). Let C3 be the chordless cycle of H
distinct from C1 containing edge e. We show that C3 contradicts the choice of
C1 . Since H contains C1 and C3 , C3 ∈ Ge1 . Also C2 and C3 have a common node
which is distinct from u or v and so uv is not a K2 cutset in the subgraph of G,
induced by V (C3 ) ∪ V (C2 ). If v C1 is contained in V (C3 ) then v C3 has an index
higher than i, a contradiction, otherwise since SC3 ⊆ SC1 and some node of SC1
belongs to C3 , |SC3 | < |SC1 |, a contradiction. 2
Proof of Theorem 1: The necessity of the condition is obvious. We prove the
sufficiency by contradiction. Assume that G and β are chosen so that G is a
counterexample to the theorem with respect to β and V (G) is minimal. Then G
is connected and by Remark 5 G contains no K1 or K2 cutset.
58 Michele Conforti and Ajai Kapoor
Clearly triangulated graphs i.e. graphs that do not contain a hole are universally
signable. In [5] these graphs are shown to generalize many of the structural prop-
erties of triangulated graphs. Here we show a decomposition theorem that follows
easily from the co-NP characterization of these graphs as given by Theorem 1.
Theorem 11. A connected universally signable graph that is not a hole and is
not a triangulated graph contains a K1 or K2 cutset.
It was the above decomposition theorem that prompted us to look for a new
proof for Theorem 1.
Now Theorem 11 and the following result of Hajnal and Suranyi [11] can be
used to decompose with clique cutsets a universally signable graph into holes
and cliques.
Theorem 12. A triangulated graph that is not a clique contains a clique cutset.
Theorem 13. A graph is α-balanceable if and only if αC is even for all even
length chordless cycles C and odd otherwise and every subgraph H of G of type
(a), (b), (c) or (d) is αH -balanceable.
To see that the two theorems are equivalent note that an α-balancing of G
with labels of 1 and −1, is implied by a β-balancing with β = ( αC −|E(C)|
2 ) mod 2,
by replacing the 0’s by −1’s. Similarly the β-balancing of G with labels of 0 and
1 is implied by an α-balancing with αC = (2βC + |E(C)|) mod 4, by replacing
the −1’s by 0’s.
A Theorem of Truemper 61
The bipartite graph G(A) of a matrix A has the row and column sets of A as
color classes and for all entries aij 6= 0, G(A) has an edge ij of label aij .
A 0, ±1 matrix A is balanced if G(A) is α-balanced for the vector α of all
zeroes. A 0, 1 matrix A is balanceable if G(A) is α-balanceable for the vector α
of all zeroes. (From now on, signing consists of replacing some of the 10 s with
−10 s).
Note that the same signing algorithm of Section 1, applied to G(A), can be
used to obtain a balanced matrix from A, when A is balanceable. Here signing
the edges of G(A) means assigning labels ±1.
We can now derive from Theorem 13 a co-NP characterization of balanceable
matrices:
Proof: By Theorem 13 we only need to find in G(A) the subgraphs of type (a),
(b), (c) or (d) that are not balanceable. Since G(A) is bipartite it cannot contain
graphs of type (b) or (c). Graphs of type (a) with both endnodes in the same
side of the bipartition are seen to be balanceable by signing the edges so that the
three paths have the same length mod 4. When the two nodes of degree 3 belong
to opposite sides of the bipartition then since two of the paths have the same
length mod4, either 1 mod 4 or 3 mod 4 there exists a chordless cycle signed
incorrectly with respect to α of all zeroes.
For a wheel (H, x), let C1 , . . . , Ck be the chordless cycles of (H, x) containing
x. Obtain a signing
P of the graphP so that C1 , . . . , Ck are signed correctly.
Pk For F ⊆
k
E, let l(F ) = e∈F l(e). Then i=1 l(Ci ) ≡ 0 mod 4. But l(H) = i=1 l(Ci ) −
2l(S) where S consists of all edges with one endpoint the center node of the
wheel. Since 2l(S) ≡ 2|S| mod 4, clearly l(H) ≡ 0 mod 4 if and only if k = |S|
is even. 2
In [8], [2], a polynomial algorithm is given, to recognize if a matrix is balance-
able or balanced. Balanced 0, ±1 matrices have interesting polyhedral properties
and have been recently the subject of several investigations, see [7] for a survey.
length 6 (and the center node has obviously three neighbors in the rim). We will
see this later in this section.
To state the theorem of Tutte characterizing regular matrices, we need to
introduce the notion of pivoting in a matrix. Pivoting
on an entry
6= 0 of a
yT − yT
matrix A = , we obtain the matrix B = .
x D x D − xy T
Remark 15. Let B be obtained from A by pivoting on the nonzero entry aij .
Then:
– A can be obtained from B by pivoting on the same entry.
– Let aij be the pivot element. Then bij = −aij . For l 6= j, bil = ail and for
k 6= i, bkj = akj . For l 6= j and k 6= i, bkl = akl − aij ail akj
– det(A) = ±det(D − xy T ) and det(B) = ±det(D).
We are interested in performing the pivot operations on A both over the reals
(R-pivoting) and over GF 2 (GF 2-pivoting). Let B be a matrix obtained from
A by performing a GF 2-pivot or an R-pivot. We next show how to obtain G(B)
from G(A).
Remark 16. Let B be the 0, 1 matrix obtained from a 0, 1 matrix A by GF 2-
pivoting on aij = 1. Then G(B) is obtained from G(A) as follows:
Remark 17. Let B̃ be the matrix obtained from a weakly balanced 0, ±1 matrix
à by R-pivoting on a non-zero entry aij = . Then B̃ is a 0, ±1 matrix and
G(B̃) is obtained from G(Ã) as follows:
Proof: 1) is trivial. By Remark 15, for k 6= i and l 6= j, bkl = akl − akj ail .
Note that 2 = 1. So bkl is the value of the determinant of the 2 × 2 submatrix
of à with rows i, k and columns j, l. Since à is weakly balanced, bkl and bkl ,
have values in 0, ±1. For 2), note that all 2 × 2 submatrices of à with all four
entries non-zero have determinant 0. Finally since the 2 × 2 submatrix of B̃ has
determinant 0, part 3) follows. 2
A Theorem of Truemper 63
To prove the above result, we need the following three lemmas (the first is
well known):
Lemma 20. A 0, 1 matrix A is regular if and only if any matrix obtained from
A by GF 2-pivoting is regular.
Proof: We show that G(B̃) can be obtained from G(B) by applying the signing
algorithm. Let T be any tree in G(B̃), chosen to contain all edges in {ij} ∪
{ix : x ∈ N (i)} ∪ {jy : y ∈ N (j)}. Then T is also a tree of G(Ã). Let
S = t1 , . . . , t|T |−1 , e1 , . . . , el be a consistent ordering of the edges of G(B̃), where
ti are edges in T . We show that the signing of G(B̃) can be obtained by the
signing algorithm with sequence S, where the edges of T are labeled as in G(B̃).
Let ek be an edge of S and Cek be a chordless cycle of G(B) containing ek and
edges in S \ ek+1 , . . . , em , such that Cek has the largest possible intersection
with {i, j} and, subject to this, Cek is shortest. We show that Cek forces ek to
be signed as in G(B̃).
Remark 17 shows that if Cek contains both nodes i and j and has length 4,
then Cek forces ek to be signed as in G(B̃).
All other edges ek are labeled the same in G(B̃) and G(Ã). We show that
Cek forces this signing of edge ek .
If Cek contains both nodes i and j and has length bigger than 4, then in
G(Ã) the nodes of Cek induce a cycle with unique chord i1 j1 , where i1 and j1
are the neighbors of i and j in Cek . By Remark 17, the sum of the labels on
the edges i1 i, ij, jj1 in G(B̃) is equivalent modulo 4 to the label of edge i1 j1 , in
G(Ã). Thus the cycle Ce0 k of G(Ã) induced by V (Cek ) \ {i, j} and the cycle Cek
of G(B̃) force ek to be signed the same.
If Cek contains one of {i, j}, say i, then by choice of Cek , node j has i as
unique neighbor in Cek . For, if not, ek either belongs to a chordless cycle of G(B̃)
of to a chordless cycle that is shorter that Cek and contains node j (this happens
when (Cek , j) is the rim of a wheel with center j and no hole of (Cek , j) contains
i, j and ek ), a contradiction to our assumption.
64 Michele Conforti and Ajai Kapoor
But then Cek is also a chordless cycle of G(Ã) and forces ek to be signed as
in G(B̃).
If Cek contains neither i nor j and at most one neighbor of i or j then Cek is
also a chordless cycle of G(Ã) and forces ek to be signed as in G(B̃). Otherwise
by the choice of Cek , node i has a unique neighbor i0 in Cek , node j has a unique
neighbor j 0 in Cek and i0 , j 0 are adjacent. So, by Remark 17, G(Ã) contains a
hole Ce0 k , whose node set is V (Cek ) ∪ {i, j}. This hole Ce0 k and the hole Cek of
G(B̃) force ek to be signed the same. 2
Lemma 22. From every 0, 1 matrix A that is not regular, we can obtain a 0, 1
matrix that is not balanceable by a sequence of GF 2-pivots.
Proof: Let A be the smallest 0, 1 matrix (in terms of the sum of the number of
rows and columns) that is not regular but cannot be pivoted to a matrix that
is not balanceable. Since A is obviously balanceable, let à be a corresponding
balanced 0, ±1 matrix. By minimality, we can assume that à is square and
|det(Ã)| ≥ 2. By Remark 15, we can R-pivot on any nonzero entry of à to
obtain a 0, ±1 matrix B̃ which contains a proper submatrix C̃ with the same
determinant value as Ã. Since à is weakly balanced, by Remark 17, B̃, and
hence C̃, is a 0, ±1 matrix. Let B be the 0, 1 matrix with the same support as B̃
and C the submatrix of B corresponding to C̃. By Corollary 18, B is obtained
from A with a GF 2-pivot on the same element. Assume B̃ is balanced. Then C̃
would be a balanced matrix which is not TU. However, this implies that C is
not regular (this was already known to Camion [1]): Indeed, C̃ is a signing of C
which is balanced but not TU: So C̃ can be obtained by applying the signing
algorithm on G(C), starting with a tree T of G(C). Assume C has a TU signing
C̃ 0 . Since C̃ 0 is also a balanced matrix, then G(C̃ 0 ) can be obtained through the
signing algorithm by signing T as in G(C̃ 0 ). So G(C̃) and G(C̃ 0 ) differ on some
fundamental cuts of T . So C̃ can be transformed in C̃ 0 by multiplying by −1 the
rows and columns corresponding to the nodes in on shore of this cut. However
this operation preserves the TU property.
So B̃ is not balanced and by Lemma 21, B is not balanceable. 2
Proof of Theorem 19: By Lemma 20, regular matrices are closed under GF 2-
pivoting and if A is a 0, 1 matrix such that G(A) contains a wheel G(W ) whose
rim has length 6, then W (hence A) is obviously not regular.
For the sufficiency part, if A is a 0, 1 matrix which is not regular, then by
Lemma 22, we can obtain by GF 2-pivots a 0, 1 matrix B which is not bal-
anceable. By Theorem 14, G(B) contains a 3P C(x, y) where x and y belong to
distinct color classes, or a wheel with rim H and center v and v has an odd
number, greater than one, of neighbors in H.
If G(B) contains a 3P C(x, y), Remark 16 shows that we can GF 2-pivot on
B so that all of its paths have length three and by doing a last GF 2-pivot on an
entry corresponding to an edge incident to x, we obtain a wheel whose rim has
length 6.
A Theorem of Truemper 65
5 Decomposition
The co-NP characterizations obtained in Theorems 8, 9 and 14 are used in [3],
[4], [8], [2] to obtain the decomposition results for graphs without even holes,
cap-free graphs and balanceable matrices. However the proofs of these theorems
are long and technical. We have seen how Theorem 1 can be used to decompose
universally signable graphs with K1 and K2 cutsets into holes and triangulated
graphs. Here we further illustrate in two easy cases the use of a co-NP character-
ization to obtain decomposition results and polynomial recognition algorithms.
Proof: Let G0 be the bipartite graph obtained from G(A) by replacing each edge
with a path of length 3 and A0 be the 0, 1 matrix such that G0 = G(A0 ). Then
there is a correspondence between the cycles of G(A) and the holes of G0 . So
A is signable to be RU if and only if G0 is α-balanceable for the vector α of all
66 Michele Conforti and Ajai Kapoor
Proof: We prove the first statement. Let x and y be two attachments of a bridge
B of a cycle C. If x and y belong to distinct color classes of G(A), then G(A)
contains a heterogeneous W 3P C(x, y) where P1 , P2 are the two xy-subpaths of
C and P3 is any xy-path in B. The proof of the second statement is similar. 2
Proof: To prove the first statement, assume B1 and B2 are homogeneous bridges
of C having attachments x1 , y1 of B1 and x2 , y2 of B2 , appearing in the order
x1 , x2 , y1 , y2 when traversing C. If x1 , y1 and x2 , y2 are in distinct color classes
of G(A), we have a heterogeneous W 3P C(x1 , x2 ), where P1 is the subpath of
C, connecting x1 , x2 and not containing y1 . P2 and P3 contain respectively a
x1 , y1 -path in B1 and a x2 , y2 -path in B2 . The proof of the second part is similar.
2
Proof: By Lemma 24, x and y are the only two attachments of B. Let P1 , P2 be
the two subpaths of C, connecting x and y. By Lemma 25, no bridge of C has
an attachments in both P1 \ {x, y} and P2 \ {x, y}. So no two of B, P1 and P2
are in the same component of G(A) \ {x, y} and, since at least two of them are
not edges, G(A) \ {x, y} contains at least two components. 2
Theorem 27 ([18]). Let A be 0, 1 matrix that is signable to be RU and C
any cycle of G(A) containing homogeneous bridges B1 and B2 with attachments
in distinct color classes of G(A). Then C contains two edges whose removal
disconnects G(A) and separates B1 and B2 .
Proof: Assume that the attachments of B1 and B2 belong to the ”red” and
”blue” sides of the bipartition of G(A). Let P1 be be minimal subpath of C with
the following property:
P1 contains all the attachments of B1 and no bridge of C with red attachments
has all its attachments either in P1 or outside P1
The subpath P2 is similarly defined, with respect to B2 and the bridges with
blue attachments. By Lemma 25 P1 and P2 can be chosen to be nonoverlapping.
Furthermore by minimality of P1 and P2 , the endnodes a1 , b1 of P1 are red nodes
and the endnodes a2 , b2 of P2 are blue nodes. Let C = a1 , P1 , b1 , Pb1 b2 , b2 , P2 , a2 ,
Pa2 a1 , let b be any edge of Pb1 b2 and a any edge of Pa1 a2 . By Lemma 25 and the
construction of P1 and P2 , P1 ∪ B1 and P2 ∪ B2 belong to distinct components
of G \ {a, b}. 2
Clearly to test if A is signable to be RU, we can assume that G(A) is bicon-
nected, otherwise we work on the biconnected components.
If G(A) is biconnected and contains no cycle with homogeneous bridges with
attachments in distinct color classes of G(A), then A has two ones per row or per
column. (This is easy from network flows). In this case A is obviously RU: Sign A
so that each row or column contains a 1 and a −1 to obtain a network matrix (or
its transpose). From this fact and the above theorem yield in a straightforward
way a polytime algorithm to test if a 0, 1 is signable to be RU. This algorithm,
combined with the signing algorithm of Section 1, gives a procedure to test if a
0, ±1 matrix is RU.
In a similar manner, see [9], Theorem 26 and the signing algorithm give
procedures to test if a 0, 1 matrix is signable to be TO and to test if a 0, ±1
matrix is TO.
References
1. P. Camion. Caractérisation des matrices totalement unimodulaires. Cahiers Centre
Études Rech. Op., 5:181–190, 1963.
2. M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković. Balanced 0, ±1 matrices,
Parts I–II. 1994. Submitted for publication.
3. M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković. Even-hole-free graphs,
Parts I–II. Preprints, Carnegie Mellon University, 1997.
68 Michele Conforti and Ajai Kapoor
1 Introduction
Let G = (V, E) be an undirected graph. A subset S of V is called a stable
set if any two elements of S are nonadjacent. Given a weight vector P
w ∈ <V ,
a maximum weight stable set is a stable set S maximizing w(S) = i∈S wi .
The problem of finding a maximum weight stable set is called the maximum
weight stable set problem (MWSSP). It is well known that the problem can be
formulated as the following integer programming problem:
In this paper, we consider the problem generalized as follows: for a given finite
set V and for given P, N, I ⊆ V × V ,
Here we call this problem the generalized stable set problem (GSSP). We note
that the GSSP is equivalent to the generalized set packing problem discussed in
[1,2]. To deal with the GSSP, a ‘bidirected’ graph is useful. A bidirected graph
G = (V, E) has a set of vertices V and a set of edges E, in which each edge
e ∈ E has two vertices i, j ∈ V as its endpoints and two associated signs (plus
or minus) at i and j. The edges are classified into three types: the (+, +)-edges
with two plus signs at their endpoints, the (−, −)-edges with two minus signs,
and the (+, −)-edges (and the (−, +)-edges) with one plus and one minus sign.
Given an instance of the GSSP, we obtain a bidirected graph by making (+, +)-
edges, (−, −)-edges and (+, −)-edges for vertex-pairs of P, N and I respectively.
Conversely, for a given bidirected graph with a weight vector on the vertices, by
associating a variable xi with each vertex, we may consider the GSSP. We call
a 0−1-vector satisfying the inequality system arising from a bidirected graph G
a solution of G. We also call a subset of vertices a solution of G if its incidence
vector is a solution of G. The GSSP is an optimization problem over the solutions
of a bidirected graph.
Since several distinct bidirected graphs may have the same set of solutions,
we deal with some kind of ‘standard’ bidirected graphs. A bidirected graph is
said to be transitive, if whenever there are edges e1 = (i, j) and e2 = (j, k) with
opposite signs at j, then there is also an edge e3 = (i, k) whose signs at i and k
agree with those of e1 and e2 . Obviously, any bidirected graph and its transitive
closure have the same solutions. A bidirected graph is said to be simple if it has
no loop and if it has at most one edge for each pair of distinct vertices. Johnson
and Padberg [3] showed that any transitive bidirected graph can be reduced to
simple one without essentially changing the set of solutions, or determined to
have no solution. We note that a transitive bidirected graph has no solution if
and only if it has a vertex with both a (+, +)-loop and a (−, −)-loop. For any
bidirected graph, the associated simple and transitive bidirected graph can be
constructed in time polynomial in the number of vertices.
Given a bidirected graph G, its underlying graph, denoted by G, is defined as
the undirected graph obtained from G by changing all the edges to (+, +)-edges.
A bidirected graph is said to be claw-free if it is simple and transitive and if its
underlying graph is claw-free (i.e., does not contain a vertex-induced subgraph
which is isomorphic to the complete bipartite graph K1,3 ).
It is well known that the MWSSP is NP-hard for general undirected graphs
(and hence, the GSSP is also NP-hard). However, for several classes of undirected
graphs, the MWSSP is polynomially solvable. For example, Minty [4] proposed a
polynomial time algorithm for the MWSSP for claw-free undirected graphs. On
the other hand, there are several polynomial transformations from the GSSP to
the MWSSP (see [5,6]). Unfortunately, we cannot easily derive the polynomial
solvability of the GSSP for claw-free bidirected graphs by using these transfor-
mations, because these do not preserve claw-freeness. Our aim in this paper is
to verify that the GSSP for claw-free bidirected graphs is polynomially solvable.
In this section, we will give several definitions and discuss basic properties of
solutions of bidirected graphs. Let G = (V, E) be a simple and transitive bidi-
The Stable Set Problem for Claw-Free Bidirected Graphs 71
We say that a vertex is positive (or negative) if all edges incident have plus
(or minus) signs at it, and that a vertex is mixed if it is neither positive nor
negative. If a bidirected graph has no (−, −)-edge, it is said to be pure. We say
that a bidirected graph is canonical if it is simple, transitive and pure and it has
no negative vertex. For any instance (G, w) of the GSSP, we can transform it to
equivalent one whose bidirected graph is canonical as follows. From the previous
section, we can assume that G is simple and transitive. Johnson and Padberg [3]
proved that G has at least one solution U ⊆ V . From Lemma 1, G:U has the
solution U 4 U = ∅, that is, G:U must be pure. Let W be the set of negative
vertices of G:U . Then G:U :W has no negative vertex, and furthermore, it is pure
because any edge (v, w) of G:U with w ∈ W must be a (+, −)-edge. Since this
transformation is done in polynomial time, we assume that a given bidirected
graph of the GSSP is canonical in the sequel.
For any solution X of a canonical bidirected graph G, we partition X into
two parts:
−+ −+
XB = {i ∈ X | NG (i) ∩ X = ∅} and XI = {i ∈ X | NG (i) ∩ X 6= ∅},
−+
where NG (i) denotes the set of vertices adjacent to i by a (−, +)-edge incident
+−
to i with a minus sign, NG (i) is defined analogously. Here we call XB a base
of X. Let
+−
ex(XB ) = XB ∪ {i ∈ V | i ∈ NG (x) for some x ∈ XB }.
Proof. Suppose to the contrary that there exists a mixed vertex v such that
−+
NG (v) contains two vertices u and w of distinct connected components Hi and
Hj . Since X is a stable set, u, w ∈ YB . Let x be a vertex of X adjacent to v.
From the transitivity, x must be adjacent to both u and w. This contradicts the
fact that Hi and Hj are distinct connected components of G[XB 4 YB ]. t
u
The Stable Set Problem for Claw-Free Bidirected Graphs 73
Si∗ = {X ∈ Si | w(X) = wi }.
Suppose that N denotes the smallest number j with wj = maxi wi . Minty [4]
showed that if a given undirected graph is claw-free, then w0 < · · · < wN . More
precisely, (0, w0 ), . . . , (N, wN ) lie on an increasing concave curve. Minty’s algo-
rithm for solving the MWSSP for claw-free undirected graphs finds an optimal
solution by tracing (i, wi ) one by one. However, even if a given bidirected graph
is claw-free, this fact does not hold as an example in Figure 1 where (+, +)-
edges are drawn by lines and (+, −)-edges by arrows whose heads mean minus
signs. Thus, it seems to be difficult to trace (i, wi ) one by one for the GSSP.
3 5 4
a b c
i wi solution
0 5 {e}
2
1 10 {b, e}
d e f −4
2 14 {b, e, h}
5
3 13 {b, e, f, g, i}
4 15 {a, c, e, f, g, i}
g h i
3 4 4
Fig. 1.
(N, wN )
(6, w6 )
(4, w4 )
(3, w3 )
(1, w1 )
(0, w0 )
0 1 2 3 4 6 N
Fig. 2.
74 Daishin Nakamura and Akihisa Tamura
We will use a technique of the fractional programming. Let us consider the up-
per envelope of the convex hull of the set of pairs (0, w0 ), (1, w1 ), . . . , (N, wN )
as in Figure 2. We call (i, wi ) a Pareto-optimal pair if it lies on the envelope,
and their solutions Pareto-optimal solutions. Obviously, (0, w0 ) and (N, wN ) are
always Pareto-optimal. In Figure 2, (0, w0 ), (1, w1 ), (3, w3 ), (4, w4 ), (6, w6 ) and
(N, wN ) are Pareto-optimal.
Let X i be a Pareto-optimal solution with X i ∈ Si . Suppose that F is a subset
of all the solutions of G such that X i ∈ F and F is defined independently to
the weight vector w. Let us also consider the Pareto-optimal solutions for the
restriction on F . Obviously, X i is also Pareto-optimal in F . We consider the
following two problems
[MAXδ] max δ(Y ) = w(Y ) − w(X i ) , and
Y ∈F
δ(Y )
[MAXρ] max ρ(Y ) = | δ(Y ) > 0 ,
Y ∈F ν(Y )
where ν(Y ) denotes the difference of the numbers of all the positive vertices of
Y and X i . We denote ρ(·) and δ(·) for a weight vector w̄ by ρw̄ (·) and δw̄ (·)
explicitly. Suppose that X i is not optimal in F . Let Y 1 be an optimal solution
of the MAXδ for w̄0 = w. We set r = ρw̄0 (Y 1 ) and consider the new weight
vector w̄1 defined by
0
w̄i − r if i is a positive vertex,
w̄i1 = (1)
w̄i0 otherwise.
in Figure 2.) In addition, if X 0 ∈ S0∗ can be found in polynomial time, the GSSP
for (G, w) can be solved in polynomial time. In fact, this initialization is not so
difficult if we can apply the above technique for any vertex-induced subgraph of
G, because it is sufficient to solve the GSSP for the bidirected graph obtained
from the current one by deleting all the positive vertices, recursively.
Finally we introduce a tool in order to trace Pareto-optimal pairs. Let X i
be a Pareto-optimal solution with i < N . Without loss of generality, we assume
that X i and G satisfy the conditions of Lemma 6. We say that H ⊆ V is an
alternating set for X i if H is connected in G and if X i 4 H is a stable set of
G. We define the weight δ(H) of an alternating set H with respect to w by
w(ex(X i 4 H)) − w(X i ).
Lemma 8. Let (j, wj ) be the next Pareto-optimal pair of (i, wi ). Then, for any
X j ∈ Sj∗ , there exists a connected component H of G[XB i
4 XB j
] such that
ex(XB 4 H) is a Pareto-optimal solution with more positive vertices than X i .
i
only alternating cycles and free alternating paths in order to find a next Pareto-
optimal solution. An alternating cycle or a free alternating path is called an
augmenting cycle or an augmenting path respectively if it has a positive weight.
For two distinct black vertices x and y, let W denote the set of all the bounded
vertices adjacent to both x and y. If W is not empty, W is called a wing adjacent
to x (and y). A black vertex is called regular if it is adjacent to three or more
wings, irregular if it is adjacent to exactly two wings, and otherwise useless.
An alternating cycle is said to be small if it has at most two regular vertices;
otherwise large. Here we call C1 , . . . , Ck a large augmenting cycle family if each
Ci is a large augmenting cycle and each vertex in Ci is adjacent to no vertex in
Cj for 1 ≤ i < j ≤ k. From Lemma 7, δ(C1 ∪ · · · ∪ Ck ) = δ(C1 ) + · · · + δ(Ck )
holds.
Our algorithm for finding a next Pareto-optimal solution is described by
using the technique discussed in the previous section:
(0) w0 ← w and i ← 0 ;
(1) Find a small augmenting cycle Ai+1 of the maximum weight for wi if it
exists, otherwise go to (2) ;
Construct the new weight wi+1 by applying (1), i ← i + 1 and repeat (1) ;
(2) Find a large augmenting cycle family Ai+1 of the maximum weight for wi
if it exists, otherwise go to (3) ;
Construct the new weight wi+1 by applying (1), i ← i + 1 and repeat (2) ;
(3) Find an augmenting path Ai+1 of the maximum weight for wi if it exists,
otherwise go to (4) ;
Construct the new weight wi+1 by applying (1), i ← i + 1 and repeat (3) ;
(4) If i = 0 then X is optimal, otherwise ex(X 4 Ai ) is a next Pareto-optimal
solution.
Note that in (2) there is no small augmenting cycle since these are eliminated
in (1), and that in (3) there is no augmenting cycle since these are eliminated in
(1) and (2). These facts are important in the following sense.
Theorem 10. The GSSP for claw-free bidirected graphs is polynomially solv-
able.
The Stable Set Problem for Claw-Free Bidirected Graphs 77
In the rest of the section, we briefly explain a proof of Theorem 9. Our ap-
proach is an extension of Minty’s algorithm for undirected claw-free graphs. This,
however, does not seem a straightforward extension because we must overcome
several problems. A significant problem is how to deal with ‘induced weights’.
Let A be an alternating cycle or a free alternating path. Then its weight is
expressed as
P −+
δX (A) = w(A−X) − w(X∩A) + {w(v) | v is mixed, NG (v) ∩ (A−X) 6= ∅}.
P
We call the term the induced weight, which appears in the bidirected case but
not in the undirected case.
We first consider cycles. Let x1 , . . . , xk with k ≥ 3 be distinct black vertices
and W1 , . . . , Wk , Wk+1 = W1 be wings such that xi is adjacent to Wi and Wi+1
for i = 1, . . . , k. Then (W1 , x1 , W2 , . . . , Wk , xk , W1 ) is called a cycle of wings. It
is easy to show the following:
−+
Lemma 12. Let v be a mixed vertex such that NG (v) has a bounded vertex
but is not included in a wing. Then there uniquely exists a black vertex x such
−+
that [x = v or x is adjacent to v] and all the vertices in NG (v) are adjacent to
x.
−+
Let v be a mixed vertex such that NG (v) ∩ (W1 ∪ · · · ∪ Wk ) 6= ∅. From
−+
Lemma 12, there uniquely exists i ∈ {1, . . . , k} such that NG (v) ∩ Wi−1 =
−+ −+
∅ and NG (v) ∩ Wi 6= ∅. Moreover from Lemma 12 again, for such i, NG (v) ∩
((W1 ∪ · · · ∪ Wk ) − (Wi ∪ Wi+1 )) = ∅. Hence the mapping conserves weights. A
maximum weight directed cycle of red edges can be found in polynomial time
by the breadth first search. t
u
Lemma 14. A maximum weight small augmenting cycle can be found in poly-
nomial time.
• v1 ∼v2 means that v1 and v2 are adjacent, and v1 6∼v2 means v1 and v2 are
not adjacent.
+−
• v1 ∼ v2 says there is an edge having plus and minus sings at v1 and v2
+−
respectively, and v1 6∼ v2 is its negation.
+ ++ +− +
• v1 ∼ v2 denotes either v1 ∼ v2 or v1 ∼ v2 , and v1 6∼ v2 is the negation of
+
v1 ∼ v2 .
• v1 v2 says that v1 and v2 are contained in the same wing, and v1 6 v2 is its
negation.
Lemma 15 ([4]). Given a regular vertex x, let B(x) = {v| v∼x and v is
bounded}. Then there exists a partition of B(x), namely [N 1 (x), N 2 (x)], such
that for any v1 , v2 ∈ B(x) with v1 6 v2 ,
This is the key lemma of Minty’s algorithm. If a large alternating cycle or a free
alternating path passes through v1 ∈ N 1 (v) and a regular vertex v, then it must
The Stable Set Problem for Claw-Free Bidirected Graphs 79
pass through a vertex v2 such that v2 ∈ N 2 (v) and v2 6 v1 . From this property
Minty showed that by constructing a graph called the “Edmonds’ graph” and by
finding a maximum weight perfect matching of it, a maximum weight augmenting
path for any Pareto-optimal stable set can be found in polynomial time. To
deal with induced weights, we require an additional property of the partition of
vertices adjacent to a regular vertex.
Lemma 16. For a regular vertex x and a vertex v such that v = x or v∼x, we
define
def +− +−
N 1 (x) v N 2 (x) ⇐⇒ ∃a∈N 1 (x), ∃b∈N 2 (x) such that a6∼b, a ∼ v and b 6∼ v,
def +− +−
N 2 (x) v N 1 (x) ⇐⇒ ∃c∈N 2 (x), ∃d∈N 1 (x) such that c6∼d, c ∼ v and d 6∼ v.
Then at most one of N 1 (x) v N 2 (x) and N 2 (x) v N 1 (x) holds.
+− +
Proof. Let us consider the case v = x. If b 6∼ x, then b ∼ x because b∼x. In
+− +
addition, if a ∼ x, then a ∼ b. Hence neither N 1 (x) x N 2 (x) nor N 2 (x) x
N 1 (x) holds.
Suppose to the contrary that v∼x, N 1 (x) v N 2 (x) and N 2 (x) v N 1 (x).
+− +−
There exist a, d ∈ N 1 (x) and b, c ∈ N 2 (x) such that a6∼b, c6∼d, a ∼ v, b 6∼ v,
+− +−
c ∼ v and d 6∼ v. Note that b, d and v are mutually distinct. Assume to the con-
+ +− +− + +
trary that b∼v. Then b ∼ v because b 6∼ v. But a ∼ v and v ∼ b induce a ∼ b,
contradicting a6∼b. Hence b6∼v and similarly d6∼v. Now b∼d since otherwise
{x, b, d, v} induces a claw. Thus b d from Lemma 15.
Suppose that a c. Because x is regular, i.e., x is adjacent to at least three
wings, there exists e ∈ N (x) such that e 6 a c and e 6 b d. Suppose that e ∈
+−
N 1 (x). Then e6∼b and e6∼c from Lemma 15. If e 6∼ v, then replace d by e, and from
+−
the above discussion, b e, a contradiction. Hence e ∼ v, and we can replace a by
e. Similarly if e ∈/ N 1 (x), i.e., e ∈ N 2 (x), then we can replace c by e. Henceforth
we assume that a 6 c.
Suppose to the contrary that a 6 d. From Lemma 15, a∼d. Since a is bounded,
a is adjacent to two black vertices: x and namely y. Then d6∼y, since otherwise
d∼x and d∼y imply a d, a contradiction. Now v∼y since otherwise {a, d, v, y}
+ −+
induces a claw. Note that v ∼ y since otherwise v ∼ y, contradicting the fact
+− + +
that y is black and v is white. Thus c ∼ v and v ∼ y induce c ∼ y. However, c∼x
and c∼y imply a c, a contradiction. Hence a d and similarly c b. Since a d,
d b and b c, a c holds. However, this contradicts the assumption a 6 c. t
u
We add the induced weight of an alternating cycle or a free alternating path
to weights of appropriate vertices in it. We define w̃ : (V ∪ (V × V )) → < by the
following procedure: let w̃ ← 0 and for each mixed vertex v,
−+
• if B −+ (v) = {u | u is bounded, v ∼ u} is empty or included in a wing,
w̃(u) ← w̃(u) + w(v) for each u ∈ B −+ (v),
80 Daishin Nakamura and Akihisa Tamura
If there is no small augmenting cycle, by using Lemma 17, we can construct the
Edmonds’ graph Ĝ such that
1. each edge of Ĝ is colored black or white, and it has a weight ŵ,
2. all the black edges form a perfect matching M of Ĝ,
3. if M is a maximum weight perfect matching of Ĝ then there is no large
augmenting cycle family in G and
4. if ŵ(M ) < ŵ(M ∗ ) for a maximum weight perfect matching M ∗ of Ĝ, let
Ĉ1 , . . . , Ĉk be all the augmenting cycles in M ∗ 4 M ; then Ĉ1 , . . . , Ĉk cor-
respond to a maximum weight large augmenting cycle family C1 , . . . , Ck in
G.
In the next section, we show that the Edmonds’ graph can be constructed in
polynomial time. Hence the step (2) in our algorithm can be done in polynomial
time. Analogously, if there is no augmenting cycle, for any pair of vertices a and
b, we can find a maximum weight augmenting path whose endpoints are a and
b, if it exists, by constructing the Edmonds’ graph and by finding a maximum
weight perfect matching in it. Now we can find a maximum weight augmenting
path by trying all the pairs of vertices a and b.
Lemma 20. If N 1 (xj ) ⊆ W (xi , xj ), then any large alternating cycle in G passes
through neither P12 nor P22 . That is, we can delete the edges (x1i , x2j ) and (x2i , x2j )
from GEd . Similarly if N 2 (xj ) ⊆ W (xi , xj ), we can delete (x1i , x1j ) and (x2i , x1j ). If
N 1 (xi ) ⊆ W (xi , xj ), we can delete (x2i , x1j ) and (x2i , x2j ). If N 2 (xi ) ⊆ W (xi , xj ),
we can delete (x1i , x1j ) and (x1i , x2j ).
Proof. Suppose that a large alternating cycle C passes xi , P12 (or P22 ) and xj .
Before xj , it passes a vertex in N 2 (xj ). Hence after xj , it must pass a vertex
v ∈ N 1 (xj ) ⊆ W (xi , xj ). Hence C contains exactly two regular vertices xi and
xj , contradicting to that C is large. t
u
In the sequel, we suppose that none of N 1 (xi ), N 2 (xi ), N 1 (xj ) nor N 2 (xj )
is contained in W (xi , xj ).
Lemma 21. There exists k such that yk1 = yk2 and 2 ≤ k ≤ ` − 1, or there exists
k such that yk1 ∼yk2 and 1 ≤ k ≤ `.
Proof. Suppose that this lemma does not hold, i.e. yk1 6= yk2 and yk1 6∼yk2 for all
k = 1, . . . , ` (Note that y11 6= y12 and y`1 6= y`2 since B 1 (xi ) ∩ B 2 (xi ) = B 1 (xj ) ∩
B 2 (xj ) = ∅). Let z0 = xi , z` = xj and Ck = (yk1 , zk , yk2 , zk−1 , yk1 ) (k = 1, . . . , `).
P` Ck is a small alternating cycle for all k = 1, . . . , `. We can show that
Then
k=1 δX (Ck ) = δ̃X (P11 ) + δ̃X (P22 ) − w(xi ) − w(xj )(> 0). (The proof is slightly
complicated because we must consider about the induced weight w̃.) Hence at
least one Ck is a small augmenting cycle, a contradiction. t
u
Now we can show the next two lemmas, but proofs are omitted.
Lemma 22. If ` = 1, any large alternating cycle passes through neither P11 nor
P22 . Hence we can delete the edges (x1i , x1j ) and (x2i , x2j ) from GEd .
0 0
and let P12 = (P11i , zk , P22j ) and P21 = (P22i , zk , P11j ).
0 0 0
Then δ̃X (P12 ) + δ̃X (P21 ) = δ̃X (P11 ) + δ̃X (P22 ), P12 is an IWAP between
B (xi ) and B (xj ), and P21 is an IWAP between B 2 (xi ) and B 1 (xj ).
1 2 0
1. Delete four edges (x1i , x1j ), (x2i , x2j ), (x1i , x2j ) and (x2i , x1j ) (Lemma 23 guaran-
tees the existence of these four edges),
2. Add two new vertices zki and zkj , join zki and zkj by a black edge and assign
its weight ŵ((zki , zkj )) to be 0, where k satisfies the conditions of Lemma 23,
3. Add four white edges (x1i , zki ), (x2i , zki ), (x1j , zkj ) and (x2j , zkj ), and assign their
weights to be ŵ((x1i , zki )) = δ̃X (P11 ), ŵ((x2i , zki )) = δ̃X (P22 ), ŵ((x1j , zkj )) = 0
and ŵ((x2j , zkj )) = δ̃X (P12 ) − δ̃X (P11 )(= δ̃X (P22 ) − δ̃X (P21 )).
All large alternating cycles through black edges (x1i , x2i ) and (x1j , x2j ) can
be preserved by our revision, because (xpi , xqj ) in the original Edmonds’ graph
(p, q ∈ {1, 2}) is interpreted by the path (xpi , zki , zkj , xqj ) in the revised Edmonds’
graph. Furthermore, Lemma 23 guarantees that weights of these four edges are
equal to those of such four paths, respectively.
Lemma 24. A maximum weight large alternating cycle family can be found in
polynomial time if there is no small augmenting cycle.
Proof. Make the Edmonds’ graph. Then eliminate all the augmenting cycles of
a form (x1i , x1j , x2j , x2i , x1i ) or (x1i , x2j , x1j , x2i , x1i ). Let G0Ed be the modified graph
and M 0 be the set of its black edges. Note that M 0 is perfect. Let M ∗ be a
maximum weight perfect matching andSĈ1 , . . . , Ĉk be all the augmenting cycle in
M 0 4 M ∗ (k may be zero). Note that ( i=1 Ĉi ) is a maximum weight alternating
k
cycle family of G0Ed . Then each Ĉi has length at least 6 because we eliminate all
augmenting cycles of length 4, and hence Ĉi corresponds to a large augmenting
cycle Ci of X such that δX (Ci ) = δM 0 (Ĉi ). Moreover C1 , . . . , Ck are disjoint
because Ĉ1 , . . . , Ĉk are vertex-disjoint. Now fromSconstruction and modification
k
of the Edmonds’ graph, we can conclude that ( i=1 Ci ) is a maximum weight
large alternating cycle family of X. t
u
References
1. E. Boros and O. C̆epek, O. On perfect 0, ±1 matrices. Discrete Math., 165/166:81–
100, 1997.
2. M. Conforti, G. Cornuéjols, and C. De Francesco. Perfect 0, ±1 matrices. Linear
Algebra Appl., 253:299–309, 1997.
3. E. L. Johnson and M. W. Padberg. Degree-two inequalities, clique facets, and
biperfect graphs. Ann. Discrete Math., 16:169–187, 1982.
4. G. J. Minty. On maximal independent sets of vertices in claw-free graphs. J.
Combin. Theory Ser. B, 28:284–304, 1980.
5. E. C. Sewell. Binary integer programs with two variables per inequality. Math.
Programming, 75:467–476, 1996.
6. A. Tamura. The generalized stable set problem for perfect bidirected graphs. J.
Oper. Res. Soc. Japan, 40:401–414, 1997.
On a Min-max Theorem of Cacti
?
Zoltán Szigeti
1 Introduction
The graph matching problem and the matroid intersection problem are two well-
solved problems in Combinatorial Theory in the sense of min-max theorems and
polynomial algorithms for finding an optimal solution. The matroid parity prob-
lem, a common generalization of them, turned out to be much more difficult. For
the general problem there does not exist polynomial algorithm [2], [3]. Moreover,
it contains NP-hard problems. On the other hand, for linear matroids Lovász
[3] provided a min-max formula and a polynomial algorithm. There are several
earlier results which can be derived from Lovász’ theorem, e.g. Tutte’s result
on f -factors [9], a result of Mader on openly disjoint A-paths [5], a result of
Nebesky concerning maximum genus of graphs [6]. Another application which
can be found in the book of Lovász and Plummer [4] is the problem of cacti. It
is mentioned there that ”a direct proof would be desirable.” Our aim is to fill
in this gap, that is to provide a simpler proof for this problem. We remark here
that we shall apply the matroid intersection theorem twice. We refer the reader
to [7] for basic concepts of matroids.
A graph K is called cactus if each block (maximal 2-connected subgraph) of
K is a triangle (cycle of length three). The size of a cactus K is the number
of its blocks. Lovász derived a min-max theorem for the maximum size of a
cactus contained in a given graph G from his general min-max theorem on linear
matroid parity problem. Here we shall give a simple proof for this result on cacti.
The proof follows the line of Gallai’s (independently Anderson’s [1]) proof for
Tutte’s theorem on the existence of perfect matchings.
In fact, we shall solve the graphic matroid parity problem in the special case
when for each pair the two edges have exactly one vertex in common. The graphic
?
This work was done while the author visited Laboratoire LEIBNIZ, Institut IMAG,
Grenoble.
matroid parity problem is the following. Given a graph G and a partition of its
edge set into pairs, what is the maximum size of a forest which consists of pairs,
in other words, what is the maximum number of pairs whose union is a forest.
A pair of edges is called v-pair if these two edges have exactly one vertex in
common and they are not loops. If G is an arbitrary graph and V is a partition
of the edge set of G into v-pairs then (G, V) is called v-graph. From now on a
cactus of (G, V) is a forest of G consisting of v-pairs in V. The size of a cactus
is the number of v-pairs contained in it. The v-graphic matroid parity problem
consists of finding the maximum size β(G, V) of a cactus in a v-graph (G, V).
The original cactus problem can be formulated as a v-graphic matroid parity
problem as follows. Let (G0 , V) be the following v-graph. The vertex set of G0
is the same as of G. We define the edge set of G0 and the partition V of the
edge set into v-pairs as follows. For each triangle T of G we introduce a v-pair
in (G0 , V): choose any two edges of T, add them to the edge set of G0 and add
this v-pair to V. (G0 will contain lots of parallel edges. In fact, G0 is obtained
from G by multiplying edges.) Obviously, there is a one to one correspondence
between the cacti of G and the forests of G0 being the union of v-pairs. Thus
the problem is indeed a v-graphic matroid parity problem.
To state the theorem on cacti we need some definitions. Let (G, V) be a v-
graph. Let P := {V1 , V2 , ..., Vl } be a partition of the vertex set V (G). Let VP ⊆ V
(SP ⊆ V) be the set of those v-pairs whose end vertices belong to three (two)
different members of P. Let Q := {H1 , H2 , ..., Hk } be a partition of VP ∪ SP .
Let us denote by p(Hi ) the number of Vj ’s for which there exists at least one
v-pair in Hi with a vertex in Vj . We say that (P, Q) is a cover of (G, V). The
value val(P, Q) of a cover is defined as follows.
X p(Hi ) − 1
val(P, Q) := n − l + b c,
2
Hi ∈Q
Let (P, Q) be a cover of a v-graph (G, V). The elements Hi ∈ Q are called
components of the cover. G/P will denote the graph obtained from G by con-
tracting each set Vi in P into one vertex. We identify the edge sets of G and
G/P. (GP , VP ) is the v-graph, where VP is defined as above, it contains those
v-pairs of V which remain v-pairs after the contraction, the vertex set of GP is
the same as of G/P and the edge set of GP is the set of edges of the v-pairs in
VP , that is, GP is obtained from G/P by deleting the edges which do not belong
to any v-pair in VP . For Hi ∈ Q, (GP [Hi ], Hi ) will denote the v-graph for which
the edge set of GP [Hi ] is the set of edges of the v-pairs in Hi and the vertex set
of GP [Hi ] contains those vertices of GP for which at least one v-pair of Hi is
incident. Then p(Hi ) is the number of vertices of GP [Hi ]. (Note that if Hi ∈ SP ,
then (GP [Hi ], Hi ) contains two edges which are parallel or one of them is a loop,
that is it is not really a v-graph. However, we shall need this type of ”v-graphs”
in the proof.) If F is a subset of edges of a v-graph (G, V) then the number of
v-pairs of V contained in F is denoted by vV (F ).
For a graph G on n vertices and with c connected components, a forest of G
containing n − c edges is called spanning. For a connected graph G, a forest F of
G containing n − 2 edges (that is, F has exactly two connected components) is
called almost spanning. A v-graph will be called (cactus)-critical if by identifying
any two vertices the v-graph obtained has a perfect cactus. Especially, this means
that in a critical v-graph there exists a cactus which is almost perfect, that is,
it is an almost spanning tree consisting of v-pairs. Critical v-graphs will play an
important role in the proof, like factor-critical graphs play the key role in the
proof of Tutte’s theorem. A component Hi ∈ Q is said to be critical in (G, V) if
the v-graph (GP [Hi ], Hi ) is critical. If Hi ∈ SP , then (GP [Hi ], Hi ) is considered
to be critical.
We say that the partition P of V is the trivial partition if l := |P| = n := |V |.
The cover (P, Q) is the trivial cover if l = n and k := |Q| = 1. Let P 0 =
{V11 , ..., V1r1 , V21 , ..., V2r2 , ..., Vl1 , ..., Vlrl }, where ∪j Vij = Vi for all i, then the
partition P 0 is called a refinement of the partition P. If P 0 is a refinement of P
so that |P 0 | = |P| + 1, then we say it is an elementary refinement. If Vi ∈ P then
the partition obtained from P by replacing Vi by its singletons will be denoted
by P ÷ {Vi }. If P 0 is a refinement of P, then we shall use p0 (Hi ) instead of p(Hi ).
We shall need later two auxiliary graphs B and D. These graphs will depend
on a v-graph (G, V) and a cover (P, Q) of this v-graph. We suppose that for
each component Hi , p(Hi ) is even. First we define the graph B = (V (G), E(B)).
e = uv will be an edge of B if and only if there exist u, v ∈ Vj ∈ P, Hi ∈ Q and
a cactus K in (GP÷{Vj } [Hi ], Hi ) consisting of p(Hi )/2 v-pairs so that exactly
two vertices u and v of Vj are connected in K, not necessarily by an edge but by
a path in K, that is u and v are in the same connected component of K. (Note
that K contains a cactus of size (p(Hi ) − 2)/2 in (GP [Hi ], Hi ). We mention that
(by Lemma 2, see later) (GP [Hi ], Hi ) will always contain a cactus consisting of
(p(Hi ) − 2)/2 v-pairs of V.) We call this edge e an augmenting edge for Hi . In
other words, the trace of the cactus K in P is the edge e. We will call the edges
of B as augmenting edges. Note that an edge of B may be augmenting for more
On a Min-max Theorem of Cacti 87
The existence of a forest with (a) and (b) can be proved, using (ii), by a
matroid partition theorem (for a graphic matroid and a truncated partitional
matroid). We shall see in Lemma 5 that if for all such forests we consider the
components where the corresponding forest is a spanning tree then we get the
set of basis of a matroid on the set of indices of the components.
Two matroids will be defined on the edge set of the auxiliary graph D, one
of them will be defined by the above introduced matroid, and the other one will
be defined by the cycle matroid of B. The matroid intersection theorem will
provide a forest of G with (a), (b) and (c). As we mentioned earlier, each part of
the forest, which corresponds to a component, can be replaced by a convenient
cactus, and thus the desired cactus has been found.
2 The Proof
Proof. (max ≤ min) Let F be an arbitrary cactus in (G, V) and let (P, Q) be any
cover of (G, V). Contract each Vi ∈ P i = 1, 2, . . . , l into a vertex and let F 0 be a
subset of F of maximum size so that F 0 is a forest in the contracted graph G/P.
For the number c (c0 ) of connected components of F in G (of F 0 in G/P) we have
obviously, c0 ≤ c. Thus |F | = n − c ≤ n − c0 = (l − c0 ) + (n − l) = |F 0 | + (n − l). It
follows that vV (F ) ≤ vV (F 0 ) + n − l. Let F 00 be the maximum subforest of F 0 in
GP consisting of v-pairs S in V. Obviously, F 00 forms a cactus in each (GP [Hi ], Hi )
Hi ∈ Q. By definition, Hi ∈Q Hi covers all the v-pairs contained in F 00 . Thus
P P
vV (F 0 ) = vV (F 00 ) = vVP (F 00 ) = Hi ∈Q vHi (F 00 ) ≤ Hi ∈Q b p(H2i )−1 c, and the
desired inequality follows. t
u
Lemma 1. For each Hi ∈ Q, the unique minimum cover of (GP [Hi ], Hi ) is the
trivial one.
X
p(Hj ) − 1
= n − l∗ +
2
Hj ∈Q−{Hi }
+ (val(P 0 , Q0 ) − (p(Hi ) − l0 ))
X
p(Hj ) − 1
≤ n − (l − p(Hi ) + l0 ) +
2
Hj ∈Q−{Hi }
p(Hi ) − 1
+ − p(Hi ) + l0 = val(P, Q).
2
It follows that equality holds everywhere, so val(P 0 , Q0 ) = b p(H2i )−1 c, thus the
trivial cover of (GP [Hi ], Hi ) is minimal. Furthermore, by the minimality of l, P 0
is the trivial partition of V (GP [Hi ]) and by the maximality of k, Q0 may contain
only one set and we are done. t
u
Proof. Suppose that there exists a component Hi ∈ Q for which (GP [Hi ], Hi )
is not critical, that is there are two vertices a and b in GP [Hi ] so that after
identifying a and b the new v-graph (G0 , V 0 ) has no perfect cactus. By the hy-
pothesis of the induction, it follows that there is a cover (P 0 , Q0 ) of (G0 , V 0 ) so
that in G0 val(P 0 , Q0 ) < (p(Hi )−1)−1
2 ≤ b p(H2i )−1 c. This cover can be considered
as a cover (P , Q ) of (GP [Hi ], Hi ) and val(P 00 , Q00 ) = val(P 0 , Q0 ) + 1. Thus
00 00
val(P 00 , Q00 ) ≤ b p(H2i )−1 c, that is (P 00 , Q00 ) is a minimal cover of (GP [Hi ], Hi )
but not the trivial one (a and b are in the same member of P 00 ), which contra-
dicts Lemma 1. t
u
Remark 2. By Corollary 1, for any component Hi the v-graph (GP [Hi ], Hi ) (and
consequently (G, V)) contains a cactus containing b p(H2i )−1 c v-pairs. However, at
this moment we can not see whether we can choose a cactus containing b p(H2i )−1 c
v-pairs for all Hi so that their union is a cactus as well. Note that by Corollary
1, p(Hi ) is even for each component Hi ∈ Q, that is b p(H2i )−1 c = p(H2i )−2 .
Proof. Let (uv, vw) be one of the v-pairs in V. Let us consider the following
cover (P 0 , Q0 ) of (G, V). Each set of P 0 contains exactly one vertex of G except
one which contains u and v, and Q0 contains exactly one set H (containing all
v-pairs in V). Then, clearly, this is a minimum cover. By the assumptions for l
and k this cover also minimizes l and maximizes k, thus by Lemma 2, its unique
component H is critical, that is the v-graph (GP 0 , VP 0 ) is critical. Let F be a
perfect cactus of the v-graph obtained from (GP 0 , VP 0 ) by identifying v and w.
Obviously, F ∪ uv ∪ vw is a perfect cactus of (G, V) and we are done. t
u
Proof. Hi ∈ / ΓD (AP 0 ) implies that there exists no augmenting edge for Hi with
respect to P 0 that is (GP 0 [Hi ], Hi ) has no perfect cactus. By Proposition 1, we can
use the induction hypothesis (of Theorem 1), that is there exists a cover (P 00 , Q00 )
of (GP 0 [Hi ], Hi ) so that val(P 00 , Q00 ) ≤ (p(Hi )+1)−1
2 − 1 = p(H2i )−2 . This cover
gives a cover (P ∗ , Q∗ ) of (GP [Hi ], Hi ) with val(P ∗ , Q∗ ) ≤ p(H2i )−2 . So (P ∗ , Q∗ )
is a minimum cover of (GP [Hi ], Hi ) and by Lemma 1, it is the trivial cover.
Moreover, v1 and v2 are in different sets of P 00 (otherwise, val(P ∗ , Q∗ ) < p(H2i )−2 ,
a contradiction), hence (P ∗ , Q∗ ) is the trivial cover of (GP 0 [Hi ], Hi ) and its value
is p(H2i )−2 . It follows that v1 or v2 is not a vertex in GP 0 [Hi ] and the proposition
is proved. t
u
Let P 0 = {V11 , ..., V1r1 , V21 , ..., V2r2 , ..., Vl1 , ..., Vlrl } where ∪j Vij = Vi for all i,
be a refinement of P. It is enough to prove that for all i where ri ≥ 2 there exists
an elementary refinement P ∗ of P with Vi = Vij ∪ (Vi − Vij ) for some 1 ≤ j ≤ ri
so that in GP ∗ [Hi ] the vertex corresponding to Vi − Vij is isolated. Applying
Proposition 2, at most ri times, we see that such an elementary refinement
exists indeed. t
u
Corollary 2. The vertex sets of the connected components of the graph B (de-
fined by the augmenting edges) are exactly the sets in P.
On a Min-max Theorem of Cacti 91
|Q∗ | − (l0 − l). Let us consider the following cover (P 0 , Q3 ) of (G, V), where Q3
is obtained from the above defined Q00 by adding each element in SP 0 − SP as
a component and adding the v-pairs in VP 0 − VP to appropriate members of
Q00 . If L ∈ VP 0 − VP , then L corresponds in W to a vertex or an edge and in
the latter case L ∈ Q1 so L corresponds to an edge of a connected component
Kj of K ∗ . We add L to the member Hj00 of Q00 corresponding to Kj . (If Kj is
an isolated vertex, then the corresponding Hj00 of Q00 was empty earlier.) Now,
(P 0 , Q3 ) is a cover of (G,
PV) indeed. We shall denote the members of Q3 − Q by
Hj 1 ≤ j ≤ c. Clearly, 1 p (Hj3 ) ≤ l0 . By Lemma 3, the value of the new cover
3 c 0
is the following.
$ %
Xc
p 0
(H 3
) − 1 X p(Hi ) − 2
val(P 0 , Q3 ) = n − l0 +
j
+
1
2 ∗
2
Hi ∈Q−Q
l0 − c X p(Hi ) − 2
≤ n − l0 + + .
2 2
Hi ∈Q−Q∗
By Lemma 4, for the trivial partition P 0 of V (G), the following fact is im-
mediate.
there exists an almost perfect cactus K in (GP [Hi ], Hi ) so that a and b belong to
different components of K. Then, by Proposition 3, F − (E(F ) ∩ E(Fi )) ∪ E(K)
is a forest. We can do this for all components, so the v-graph (G, V) contains a
P
cactus containing Hi ∈Q b p(H2i )−1 c v-pairs.
Thus e ∈ E(Fi ) so that Hi ∈ Q0 and then obviously Q00 ∪ {Hi } ∈ M and we are
done. t
u
We shall apply the matroid intersection theorem for the following two ma-
troids on the edge set of the graph D. For a set Z ⊆ E(D), let us denote the
end vertices of Z in the colour class E(B) (Q) by Z1 (Z2 , respectively). The
rank of Z in the first matroid will be rB (Z1 ) and rM (Z2 ) in the second matroid,
where rB is the rank function of the cycle matroid of the graph B and rM is the
rank function of the above defined matroid M. Note that if a vertex x of D is
in the colour class E(B) (Q) then the edges incident to x correspond to parallel
elements of the first (second) matroid.
Proof. By the matroid intersection theorem (see for example [7]) we have to
prove that for any set Z ⊆ E(D) (+) n − l ≤ rB (E(D) − Z) + rM (Z).
94 Zoltán Szigeti
Suppose that there is a set Z violating (+). Clearly, we may assume that
E(D)− Z is closed in the first matroid. This implies that there is a set J ⊆ E(B)
so that E(D) − Z is the set of all edges of D incident to J and J is closed in
the cycle matroid of B. Let us denote by V10 , V20 , ..., Vl00 the vertex sets of the
connected components of the graph on vertex set V (B) with edge set J. Then
by the closedness of J, E(B)− J is the set of augmenting edges of the refinement
P 0 := {V10 , V20 , ..., Vl00 } of P, that is, AP 0 = E(B) − J. (Obviously, Z is the set
of all edges incident to E(B) − J in D.) Then rM (Z) = rM (ΓD (AP 0 )) and
rB (E(D) − Z) = rB (J) = n − l0 . By (1), l0 − l ≤ rM (ΓD (AP 0 )) and thus
n − l = (l0 − l) + (n − l0 ) ≤ rM (Z) + rB (E(D) − Z), contradicting the fact that
Z violates (+). t
u
Remark 5. While I was writing the final version of this paper I realized that the
same proof (after the natural changes) works for the general graphic matroid
parity problem. The details will be given in a forthcoming paper [8].
References
1. I. Anderson. Perfect matchings of a graph. Journal of Combinatorial Theory, Series
B, 10:183–186, 1971.
2. P. Jensen and B. Korte, Complexity of matroid property algorithms. SIAM J.
Comput., 11:184–190, 1982.
3. L. Lovász. Matroid matching problem. In Algebraic Methods in Graph Theory.
Colloquia Mathematica Societatis J. Bolyai 25, Szeged, 1978.
4. L. Lovász and M. D. Plummer. Matching Theory. North Holland, Amsterdam,
1986.
5. W. Mader. Über die maximalzahl kreuzungsfreier H-wege. Archiv der Mathematik,
31, 1978.
6. L. Nebesky. A new characterization of the maximum genus of a graph. Czechoslovak
Mathematical Journal, 31, 1981.
7. A. Recski. Matroid Theory and its Applications in Electric Network Theory and
in Statics. Akadémiai Kiadó, Budapest, 1989.
8. Z. Szigeti. On the graphic matroid parity problem. In preparation.
9. W. T. Tutte. Graph Factors. Combinatorica, 1:79-97, 1981.
Edge-Splitting and Edge-Connectivity
Augmentation in Planar Graphs
1 Introduction
Let G = (V, E) stand for an undirected multigraph, where an edge with end
vertices u and v is denoted by (u, v). For a subset1 S ⊆ V in G, G[S] denotes
the subgraph induced by S. For two disjoint subsets X, Y ⊂ V , we denote by
EG (X, Y ) the set of edges (u, v) with u ∈ X and v ∈ Y , and by cG (X, Y )
the number of edges in EG (X, Y ). The set of edges EG (u, v) may alternatively
be represented by a single link (u, v) with multiplicity cG (u, v). In this way,
we also represent a multigraph G = (V, E) by an edge-weighted simple graph
N = (V, LG , cG ) (called a network) with a set V of vertices and a set LG of links
weighted by cG : LG → Z + , where Z + is the set of non-negative integers. We
denote |V | by n, |E| by e and |LG | by m. A cut is defined as a subset X of V
1
A singleton set {x} may be simply written as x, and “ ⊂ ” implies proper inclusion
while “ ⊆ ” means “ ⊂ ” or “ = ”.
with ∅ 6= X 6= V , and the size of the cut X is defined by cG (X, V − X), which
may also be written as cG (X). If X = {x}, cG (x) denotes the degree of vertex x.
For a subset X ⊆ V , define its inner-connectivity by λG (X) = min{cG (X 0 ) | ∅ = 6
X 0 ⊂ X}. In particular, λG (V ) (i.e., the size of a minimum cut in G) is called
the edge-connectivity of G. For a vertex v ∈ V , a vertex u adjacent to v is called
a neighbor of v in G. Let ΓG (v) denote the set of neighbors of v in G.
Let s ∈ V be a designated vertex in V . A cut X is called s-proper if ∅ 6=
X ⊂ V − s. The size λG (V − s) of a minimum s-proper cut is called the s-
based-connectivity of G. Hence λG (V ) = min{λG (V − s), cG (s)}. A splitting at
s is (k, s)-feasible if λG0 (V − s) ≥ k holds for the resulting graph G0 . Lovász [6]
showed the following important property:
Since a complete (k, s)-feasible splitting effectively reduces the number of ver-
tices in a graph while preserving its s-based-connectivity, it plays an important
role in solving many graph connectivity problems (e.g., see [1,2,9]).
In this paper, we prove an extension of Lovász’s edge-splitting theorem, aim-
ing to solve the edge-connectivity augmentation problem with an additional con-
straint that preserves the planarity of a given planar graph. Firstly, we consider
the following type of splitting; for a multigraph G = (V, E) with a designated
vertex s, let ΓG (s) = {w0 , w1 , . . . , wp−1 } (p = |ΓG (s)|) of neighbors of s, and
assume that a cyclic order π = (w0 , w1 , . . . , wp−1 ) of ΓG (s) is given. We say
that two edges e1 = (wh , wi ) and e2 = (wj , w` ) are crossing (with respect to π)
if e1 and e2 are not adjacent and the four end vertices appear in the order of
wh , wj , wi , w` along π (i.e., h + a = j + b = i + c = ` (mod p) holds for some
1 ≤ c < b < a ≤ p − 1). A sequence of splittings at s is called noncrossing
if no two split edges resulting from the sequence are crossing. We prove that
there always exists a complete and noncrossing (k, s)-feasible splitting for even
integers k, and such a splitting can be found in O(n2 (m + n log n)) time.
Next we consider a planar multigraph G = (V, E) with a vertex s ∈ V of even
degree. A complete splitting at s is called planarity-preserving if the resulting
graph from the splitting remains planar. Based on the result of noncrossing
splitting, we prove that, if k is an even integer with k ≤ λG (V − s), then there
always exists a complete (k, s)-feasible and planarity-preserving splitting, and
the splitting can be found in O(n3 log n) time. For k = 3, we prove by a separate
argument that there exists a complete (k, s)-feasible and planarity-preserving
splitting if the resulting graph is allowed to be re-embedded in the plane.
Example 1. (a) Fig. 1(a) shows a graph G1 = (V, E) with cG1 (s, wi ) = 1 and
cG1 (wi , wi+1 ) = a, 0 ≤ i ≤ 3 for a given integer a ≥ 1. Clearly, λG1 (V − s) =
k for k = 2a + 1. For a cyclic order π = (w0 , w1 , w2 , w3 ), G1 has a unique
complete (k, s)-feasible splitting (i.e., splitting pair of (s, w0 ), (s, w2 ) and a pair
of (s, w1 ), (s, w3 )), which is crossing with respect to π. This implies that, for every
odd k ≥ 3, there is a graph G with a designated vertex s and a cyclic order of
98 Hiroshi Nagamochi and Peter Eades
s s s
1 1
1 1 1 1 1 1 1
1 1
1 w11 a a w1 w11 a a w1
a w0 a w0
a a a w0 a-1
w10 1 w2 w10 w2
1
a a a 1 a
w3 w1 w9 1 1 w3 w9 1 w3
a a 1 1
a a
a a w8 1 w4 w8
aw a a-1
1 a
w4
7
a a a a
w5 w5
w2 w6 w7 w6
(a) (b) (c)
ΓG (s) which has no complete and noncrossing (k, s)-feasible splitting. Note that
the planar G1 has a complete and planarity-preserving (k, s)-feasible splitting (by
putting one of the split edges in the inner area of cycle C1 = {w0 , w1 , w2 , w3 }).
(b) Fig. 1(b) shows a planar graph G2 = (V, E) with cG2 (wi , wi+1 ) = a (mod
12) for 0 ≤ i ≤ 11 and cG2 (e) = 1 otherwise for an integer a ≥ 1, which satisfies
λG2 (V − s) = k for k = 2a + 1. The G2 has a unique complete (k, s)-splitting,
which is not planarity-preserving unless the embedding of subgraph G2 [V − s] is
not changed; if G2 [V − s] is re-embedded in the plane so that block components
{w2 , w3 , w4 } and {w8 , w9 , w10 } of G2 [V − s] are flipped and two vertices w3 and
w9 share the same inner face, then the complete (k, s)-splitting is now planarity-
preserving. From this, we see that for every odd k ≥ 3, there is a planar graph
G with a designated vertex s which has no complete and planarity-preserving
(k, s)-feasible splitting (unless the embedding of G is re-embedded).
(c) Let a ≥ 2 be an integer, and consider the graph G3 = (V, E) in Fig. 1(c),
where cG3 (wi , wi+1 ) = a for i ∈ {1, 7}, cG3 (wi , wi+1 ) = a (mod 12) for i ∈
{0, 1, . . . , 11} − {1, 7}, and cG3 (e) = 1 otherwise. Clearly, λG3 (V − s) = k for
k = 2a + 1 (≥ 5). It is easily observed that the unique complete (k, s)-feasible
splitting is not planarity-preserving for any choice of re-embedding of G3 in the
plane. This implies that for every odd k ≥ 5, there exists a graph which has no
complete and planarity-preserving (k, s)-feasible splitting even if re-embedding
after splitting is allowed. t
u
2 Preliminaries
2.1 Computing s-Based Connectivity
The vertex set V of a multigraph G = (V, E) are denoted by V (G). We say that
a cut X separates two disjoint subsets Y and Y 0 of V if Y ⊆ X ⊆ V − Y 0 (or
Y 0 ⊆ X ⊆ V − Y ). The local edge-connectivity λG (x, y) for two vertices x, y ∈ V
is defined to be the minimum size of a cut in G that separates x and y. A cut X
crosses another cut Y if none of subsets X ∩ Y , X − Y , Y − X and V − (X ∪ Y )
is empty.
Augmentation in Planar Graphs 99
Algorithm CONTRACT
Input: A multigraph G = (V, E) with |V | ≥ 3 and a designated vertex s ∈ V .
Output: an s-proper cut X ∗ with cG (X ∗ ) = λG (V − s) < λG (X ∗ ).
1 α := min{cG (v) | v ∈ V − s};
2 Let X := {v} for a vertex v ∈ V − s with cG (v) = α;
3 H := G;
4 while |V (H)| ≥ 4 do { cH (u) ≥ α holds for all u ∈ V (H) − s }
5 Find an MA-ordering in H starting from v1 = s, and let v, w (6= s) be the
last two vertices in this ordering; { λH (v, w) = cH (w) by Lemma 1(ii) }
6 Contract v and w into a vertex, say z, and let H be the resulting graph;
7 if cH (z) < α then
8 Let X ∗ be the set of all vertices in V − s contracted into z so far;
{ cH (z) = cG (X ∗ ) }
9 end { if }
10 end. { while }
It should be noted that for each u ∈ V (H) − s cH (u) ≥ α holds before every
iteration of the while-loop. The last two vertices v, w in an MA ordering in line 5,
which are clearly distinct from s, satisfy λH (v, w) = cH (w) by Lemma 1(ii).
Let X ∗ be the cut output by CONTRACT, and α∗ be the final value of α
(i.e., α∗ = cG (X ∗ )). Note that any two vertices v and w in line 5 have been
contracted into a single vertex only when λH (v, w) ≥ α∗ holds. We prove that
α∗ = λG (V − s). For a vertex u ∈ V (H) − s, let Xu denote the set of all
vertices in V − s contracted so far. Assume that there is an s-proper cut Y with
cG (Y ) < α∗ . Clearly, the final graph H has three vertices z1 , z2 and s, and
satisfies α∗ ≥ min{cH (z1 ), cH (z2 )}, and thus Y 6= Xz1 , Xz2 . Hence there is a
vertex pair v, w ∈ V (H) chosen in line 5 at some iteration of the while-loop such
that Xv ⊆ Y and Xw ⊆ (V − s) − Y (or Xw ⊆ Y and Xv ⊆ (V − s) − Y ).
Assume that v and w are the vertices in the earliest iteration of the while-loops
among such pairs of vertices. This implies that when v and w are contracted
into a vertex, the current graph H has a subset Y 0 ⊂ V (H) − s such that
∪y∈Y 0 Xy = Y . However, λH (v, w) ≤ cH (Y 0 ) = cG (Y ) < α∗ , contradicting
λH (v, w) ≥ α∗ . Therefore, α∗ = λG (V − s).
100 Hiroshi Nagamochi and Peter Eades
(i) If two (k, s)-semi-critical cuts X and Y s-cross each other, then cG (X) =
cG (Y ) = k + 1, cG (X − Y ) = cG (Y − X) = k and cG (X ∩ Y, V − (X ∪ Y )) = 1.
(ii) Let X be an admissible cut with respect to u, u0 ∈ V − s (possibly u = u0 ),
and Y be a (k, s)-semi-critical cut. If X and Y cross each other, then cG (X) =
cG (Y ) = k + 1 and cG (Y − X) = k.
(iii) Let Xi (resp., Xj ) be admissible cuts with respect to ui , u0i (resp., with respect
to uj , u0j ), where possibly ui = u0i or uj = u0j holds. If {ui , u0i } ∩ {uj , u0j } = ∅ or
cG (s, u) ≥ 2 for some u ∈ {ui , u0i } ∩ {uj , u0j }, then two cuts Xi and Xj do not
cross each other. t
u
We now describe an algorithm, called COLLECTION, which computes a
(k, s)-semi-critical covering collection X in a graph G∗ obtained from G by a
noncrossing sequence of (k, s)-feasible splittings. Let π = (w0 , w1 , . . . , wp−1 ) be
a cyclic order of ΓG (s). In a graph G0 obtained from G by a noncrossing sequence
of (k, s)-feasible splittings, a vertex wj is called a successor of a vertex wi if
cG0 (s, wj ) ≥ 1 and h > 0 with j = i + h (mod p) is minimum.
0. Initialize X to be ∅.
1. for each wi , i := 0, . . . , p − 1 do
if wi is not in any cut X ∈ X then execute MAXSPLIT(wi , wi , k) to compute
G0 = G/(wi , wi , δ) with δ = ∆G (wi , wi , k) and an admissible cut Xwi in G0 (if
cG0 (s, wi ) ≥ 2); let G := G0 ;
if cG (s, wi ) ≥ 2 then X := X ∪ {Xwi }, discarding all X ∈ X with X ⊂ Xwi
from X .
end { for }
2. for each wi such that cG (s, wi ) = 1, i := 0, . . . , p − 1 do
if wi is not in any cut X ∈ X then execute MAXSPLIT(wi , wj , k) for wi and
the successor wj of s in the current G to compute G0 = G/(wi , wj , δ) with
δ = ∆G (wi , wj , k) and an admissible cut Xwi in G0 (if cG0 (s, wi ) = 1); let
G := G0 ;
if cG (s, wi ) = 1 then X := {X − Xwi | cG (s, X − Xwi ) > 0, X ∈ X } ∪ {Xwi }.
else (if cG (s, wi ) = 0) remove any cut X with cG (s, X) = 0 from X .
end { for }
Output G∗ := G. t
u
Clearly, the resulting sequence of splitting is (k, s)-feasible and noncrossing.
Lemma 5. Algorithm COLLECTION correctly computes a (k, s)-semi-critical
covering collection X in the output graph G∗ .
Proof: Let X be the set of cuts obtained after step 1. If two cuts Xwi , Xwj ∈ X
(0 ≤ i < j ≤ p − 1) has a common vertex v, then wj 6∈ Xwi and Xwi − Xwj 6= ∅
(otherwise, Xwi must have been discarded). However, this implies that Xwi and
Xwj cross each other, contradicting Lemma 4(iii). Thus, the X is a (k, s)-semi-
critical collection.
Now we prove by induction that X is a (k, s)-semi-critical collection dur-
ing step 2. Assume that MAXSPLIT(wi , wj , k) is executed to compute G0 =
G/(wi , wj , δ) with δ = ∆G (wi , wj , k). If cG0 (s, wi ) = 0, then a cut X ∈ X with
wj ∈ X may satisfy cG0 (s, X) = 0 after the splitting. However, such a cut will
Augmentation in Planar Graphs 103
most 4(|ΓG (s)|+|X |) = O(|ΓG (s)|) times, we can obtain a complete (k, s)-feasible
splitting of a given graph G, which is obviously noncrossing.
4 Planarity-Preserving Splitting
(i) Any s-proper cut X with cG (X) ≤ 4 induces a connected subgraph G[X].
(ii) Assume λG[V −s] (V − s) = 0, and let u and v be two neighbors of s such that
they belong to different 1-components in G[V − s]. Then ∆G (u, v, 3) ≥ 1.
(iii) Assume λG[V −s] (V − s) = 1. Let Y be a leaf 2-component in G[V − s]. If
∆G (u, v, 3) = 0 for some neighbors u ∈ ΓG (s) ∩ Y and v ∈ ΓG (s) − Y , then
ΓG (s) − Y − v 6= ∅ and ∆G (u0 , v 0 , 3) ≥ 1 for any neighbors v 0 ∈ ΓG (s) − Y − v
and u0 ∈ ΓG (s) ∩ Y .
(iv) Assume λG[V −s] (V − s) = 2. Let Y be a 3-component with cG (s, Y ) ≥ 2
in G[V − s]. Then ∆G (u, v, 3) ≥ 1 for any neighbors u ∈ ΓG (s) ∩ Y and
v ∈ ΓG (s) − Y .
(v) Assume λG[V −s] (V −s) = 2. Let Y be a non-leaf 3-component with cG (s, Y ) =
1 in G[V − s]. If ∆G (u, v, 3) = 0 for some neighbors u ∈ ΓG (s) ∩ Y and
v ∈ ΓG (s) − Y , then ΓG (s) − Y − v 6= ∅ and ∆G (u, v 0 , 3) ≥ 1 for any neighbor
v 0 ∈ ΓG (s) − Y − v. t
u
Based on this lemma, for a given cyclic order π of ΓG (s), we can find a
noncrossing sequence of (k, s)-feasible splittings (which may not be complete)
such that the resulting graph G∗ satisfies either cG∗ (s) = 0 (i.e., the obtained
splitting is complete) or the following condition:
Algorithm PREPROCESS
Input: A multigraph G = (V, E) (which is not necessarily planar), a designated
vertex s ∈ V with even degree and λG (V − s) ≥ 3 , and a cyclic order π of ΓG (s).
Output: A multigraph G∗ obtained from G by a noncrossing (3, s)-feasible
splitting such that G∗ satisfies either cG∗ (s) = 0 or (2).
1 G0 := G;
2 while G0 [V − s] is not connected do
3 Find a neighbor w ∈ ΓG0 (s) and its successor w0 ∈ ΓG0 (s) such that
w and w0 belong to different 1-components in G0 [V − s];
4 G0 := G0 /(w, w0 , 1)
5 end; { while }
6 while G0 [V − s] is not 2-edge-connected (i.e., λG0 [V −s] (V − s) = 1) do
7 Choose a leaf 2-component Y in G0 [V − s];
8 Find a neighbor w ∈ ΓG0 (s) ∩ Y and its successor w0 ∈ ΓG0 (s) − Y ;
9 if ∆G (w, w0 , 3) ≥ 1 then G0 := G0 /(w, w0 , 1)
10 else
11 Find a neighbor w00 ∈ ΓG0 (s) − Y and its successor w000 ∈ ΓG0 (s) ∩ Y ,
and G0 := G0 /(w00 , w000 , 1)
12 end { if }
Augmentation in Planar Graphs 107
13 end; { while }
14 while G0 [V − s] has a 3-component Y with cG0 (s, Y ) ≥ 2 or a non-leaf
3-component Y with cG0 (s, Y ) = 1 do
15 Find neighbors w ∈ ΓG0 (s) ∩ Y and w0 ∈ ΓG0 (s) − Y such that w0 is
the successor of w;
16 if ∆G (w, w0 , 3) ≥ 1 then G0 := G0 /(w, w0 , 1)
17 else { Y is a non-leaf 3-component with cG0 (s, Y ) = 1 }
18 Find a neighbor w00 ∈ ΓG0 (s) − Y such that w is the successor of w00 ,
and G0 := G0 /(w00 , w, 1)
19 end { if }
20 end; { while }
21 Output G∗ := G0 .
In other words, cactus GG00 represents all 2-cuts in G00 = G∗ [V −s]. By Lemma 9,
there is a bijection between EG∗ (s) and L(GG00 ), and thus GG00 has an even
number of leaf vertices. A set σ of new edges which pairwise connect all leaf
vertices in a cactus is called a leaf-matching. Hence finding a complete (k, s)-
feasible splitting in G∗ is to obtain a leaf-matching σ in GG00 such that adding
the leaf-matching destroys all 2-cuts in the cactus GG00 .
However, to ensure that the complete splitting corresponding to a leaf-mat-
ching preserves the planarity of G∗ , we need to choose a leaf-matching σ of GG00
carefully. An embedding χ of a cactus in the plane is called standard if all leaf
vertices are located on the outer face of χ. In particular, for a cyclic order π of leaf
vertices, a standard embedding χ of a cactus is called a standard π-embedding
if the leaf vertices appear in the order of π along the outer face of χ. Note that
a standard π-embedding of a cactus is unique (unless we distinguish one edge
from the other in a cycle of length two). We define a flipping operation in an
embedding χ of cactus G = (V, E) as follows. Choose a cycle C in G and a vertex
z in C. We see that removal of the two edges in C incident to z creates two
connected components, say G 0 and G 00 ; we assume that z ∈ V (G 0 ). Let G[C, z]
denote the subgraph G 0 of G. We say that the embedding χ of G is flipped by
(C, z) if we fold the subgraph G[C, z] back into the other side of area surrounded
by C while fixing the other part of the embedding χ. An embedding obtained
from a standard π-embedding of a cactus by a sequence of flipping operations is
called a π 0 -embedding.
Recall that neighbors in ΓG∗ (s) appear in cyclic order πψ0 = (w1 , . . . , wr )
in an embedding χψ of G∗ . We also use πψ0 to represent the cyclic order of
leaf vertices z1 = ϕ(w1 ), z2 = ϕ(w2 ), . . . , zr = ϕ(wr ) in cactus GG00 . Then the
standard πψ0 -embedding χψ of GG00 has the following property:
each vertex z ∈ V in GG00 can be replaced with the subgraph
(3)
G∗ [ϕ−1 (z)] without creating crossing edges in χ.
Observe that a flipping operation preserves property (3), and hence any π-
embedding χ of GG00 also satisfies the property (3).
A pair (σ, χ) of a leaf-matching σ on leaf vertices in a cactus G and a π-
embedding χ of G is called a π-configuration. A π-configuration (σ, χ) of G is
called good if it satisfies the following conditions.
Augmentation in Planar Graphs 109
(a) all 2-cuts in cactus G = (V, E) are destroyed by adding σ (i.e., for any 2-cut
X, σ contains an edge (z, z 0 ) with z ∈ X and z 0 ∈ V − X), and
(b) all edges in σ can be drawn in π-embedding χ of G without creating crossing
edges.
Now the problem of computing a complete and planarity-preserving (3, s)-
feasible splitting in G∗ is to find a good πψ0 -configuration (σ, χ) of GG00 . To show
that such a good πψ0 -configuration always exists in GG00 , it suffices to prove the
next lemma (the proof is omitted).
Lemma 10. For a cactus G = (V, E) and a cyclic order π of leaf vertices, as-
sume that there is a standard π-embedding of G. Then there always exists a good
π-configuration (σ, χ) of G, and such a configuration can be found in O(|V|2 )
time. t
u
By this lemma, a complete and planarity-preserving (3, s)-feasible splitting
in a graph G∗ which satisfies (2) can be computed in O(n2 ) time. This and
Lemma 8 establish the following theorem.
Theorem 4. Given a planar multigraph G = (V, E) with a designated vertex
s ∈ V of even degree, and λG (V − s) ≥ 3, there exists a complete and planarity-
preserving (3, s)-feasible splitting, and such a splitting can be found in O(n2 )
time. t
u
Acknowledgments
This research was partially supported by the Scientific Grant-in-Aid from Min-
istry of Education, Science, Sports and Culture of Japan, the grant from the
Inamori Foundation and Kyoto University Foundation, and the Research Man-
agement Committee from The University of Newcastle.
References
1. G.-R. Cai and Y.-G. Sun. The minimum augmentation of any graph to k-edge-
connected graph. Networks, 19:151–172, 1989.
2. A. Frank. Augmenting graphs to meet edge-connectivity requirements. SIAM J.
Disc. Math., 5:25–53, 1992.
3. G. Kant. Algorithms for Drawing Planar Graphs. PhD thesis, Dept. of Computer
Science, Utrecht University, 1993.
4. G. Kant. Augmenting outerplanar graphs. J. Algorithms, 21:1–25, 1996.
5. G. Kant and H. L. Boldlaender. Planar graph augmentation problems. LNCS,
Vol. 621, pages 258–271. Springer-Verlag, 1992.
6. L. Lovász. Combinatorial Problems and Exercises. North-Holland, 1979.
7. H. Nagamochi and T. Ibaraki. A linear time algorithm for computing 3-edge-
connected components in multigraphs. J. of Japan Society for Industrial and
Applied Mathematics, 9:163–180, 1992.
8. H. Nagamochi and T. Ibaraki. Computing edge-connectivity of multigraphs and
capacitated graphs. SIAM J. Disc. Math., 5:54–66, 1992.
9. H. Nagamochi and T. Ibaraki. Deterministic Õ(nm) time edge-splitting in undi-
rected graphs. J. Combinatorial Optimization, 1:5–46, 1997.
10. R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput.,
1:146–160, 1972.
Augmentation in Planar Graphs 111
1 Introduction
The 2-Edge Connected Subgraph Problem is a fundamental problem in Sur-
vivable Network Design. This problem arises in the design of communication
networks that are resilient to single-link failures and is an important special case
in the design of survivable networks [11,12,14].
1.1 Formulation
An integer programming formulation for the 2-Edge Connected Subgraph Prob-
lem is as follows. Let Kn = (V, E) be the complete graph of feasible links on
?
Supported by NSF grant DMS9509581 and DOE contract AC04-94AL85000.
??
Research supported in part by an NSF CAREER grant CCR-9625297.
minimize c · x
subject to
x(δ(v)) ≥ 2 for all v ∈ V,
(1)
x(δ(S)) ≥ 2 for all S ⊂ V,
xe ≥0 for all e ∈ E,
xe integral.
minimize c · x
subject to
x(δ(v)) = 2 for all v ∈ V, (2)
x(δ(S)) ≥ 2 for all S ⊂ V,
xe ≥ 0 for all e ∈ E.
The constraints of the subtour relaxation are called the degree constraints, the
subtour elimination constraints, and the non-negativity constraints respectively.
If one has the relationship cij ≤ cik + cjk for all distinct i, j, k ∈ V , then
c is said to satisfy the triangle inequality. An interesting known result is that
if the costs satisfy the triangle inequality, then there is an optimal solution to
(1) which is also feasible and hence optimal for (2). This follows from a result
of Cunningham [11] (A more general result called the Parsimonious Property is
shown by Goemans and Bertsimas in [7]). We can show that this equivalence
holds even when the costs do not satisfy the triangle inequality. In the latter
case, we replace the given graph by its metric completion, namely, for every
edge ij such that cij is greater than the cost of the shortest path between i and
j in the given graph, we reset the cost to that of this shortest path. The intent
is that if this edge is chosen in the solution of (1), we may replace it by the
shortest cost path connecting i and j. Since multiedges are allowed in the 2-edge
connected graph this transformation is valid. Hence without loss of generality,
we can assume that the costs satisfy the triangle inequality.
114 Robert Carr and R. Ravi
2 Motivation
In this section we discuss two distinct motivations that led us to focus on half-
integral extreme points and prove a version of Conjecture 1 for this special case.
One follows from a particular strategy to prove Conjecture 1 and the other
from examining subclasses of subtour extreme points that are sufficient to prove
Conjectures 1 and 2.
Let an arbitrary point x∗ of the subtour polytope for Kn be given. Multiply this
by 43 to obtain the vector 43 x∗ . Denote the edge incidence vector for a given 2-edge
connected subgraph H in Kn by χH . Note that edge variables could be 0,1, or 2
in this incidence vector. Suppose we could express 43 x∗ as a convex combination
of incidence vectors of 2-edge connected subgraphs Hi for i = 1, 2, . . . , k. That
is, suppose that
4 ∗ Pk
3x = i=1 λi χHi , (3)
X
k
λi = 1.
i=1
Then, taking dot products on both sides of (3) with the cost vector c yields
4
Pk
3c · x∗ = i=1 λi c · χHi . (4)
Since the right hand side of (4) is a weighted average of the numbers c · χHi , it
follows that there exists a j ∈ {1, 2, . . . , k} such that
c · χHj ≤ 43 c · x∗ . (5)
If we could establish (5) for any subtour point x∗ , then it would in particular
be valid for the optimal subtour point, which would prove Conjecture 1.
In an attempt at proving Conjecture 1, we aim at contradicting the idea of a
minimal counterexample, that is, a subtour point x∗ having the fewest number of
vertices n0 such that (3) can not hold for any set of 2-edge connected subgraphs.
First we have the following observation.
of convex multipliers. Thus, for each l, we can find a set of 2-edge connected
subgraphs Hil such that
4 l X l Hil
x = λi χ ,
3 i
where the λli ’s satisfy the usual constraints for a set of convex multipliers. Then
4 ∗
P 4
P P l
3x l 3 µl x µl λli χHi .
l
= = l i (6)
x∗ (δ(H)) = 2.
We can then split x∗ into 2 smaller subtour solutions x1 and x2 in the following
way. Take the vertices of V \ H in x∗ and contract them to a single vertex to
obtain x1 . Likewise, take the vertices of H in x∗ and contract them to a single
vertex to obtain x2 . An example of this is shown in Figure 1.
Since x1 and x2 are not counterexamples to our conjecture, we would be able
to decompose 43 x1 and 43 x2 into combinations of 2-edge connected subgraphs,
which we may then attempt to glue together to form a similar combination for
4 ∗ ∗
3 x , thereby showing that x is not a counterexample (We show how this can be
accomplished for the case of half-integral extreme points in Case 1 in the Proof
of Theorem 6).
What if there are no tight substantial cuts however? The following proposi-
tion which is shown in [1] shows us what we need to do.
2/3
2/3
1/3
2/3
1/3
1 1
1 2/3
1
1/3 2/3
2/3
1/3
2/3
Fig. 1. An idea for splitting a minimal counterexample into two smaller in-
stances. Note that H defines a substantial tight cut, i.e., both H and V \ H have
at least three vertices and x(δ(H)) = 2.
where the H i ’s are 2-edge connected graphs spanning V . For each i, contract
each circle of nodes Cv back to the vertex v ∈ V in H i . Call the resulting graph
Hi . Since contraction preserves edge connectivity, Hi is a 2-edge connected graph
spanning V . When one performs this contraction on x∗ , one gets x∗ . As a result,
we obtain that
4 ∗
P
3x = i λi χ ,
Hi
(8)
We define a tight cut for a 4-edge connected graph G to be a cut which has
exactly 4-edges in it. We define a non-trivial cut for such a graph to be a cut
where both shores have at least 2 vertices each. We have the following lemma.
Lemma 1. Let G = (V, E) be a 4-regular 4-edge connected graph which has no
tight non-trivial cut which includes an edge e = uv ∈ E. Let the other 3 (not
necessarily distinct) neighbors of v be x, y, and z. Then either ux or yz is a loop
or G0 = G − v + ux + yz is 4-regular and 4-edge connected, and likewise for the
other combinations.
3χ = i λi χHi , (11)
In (11), consider the edges incident to v1 in each of the Hi1 ’s. There are clearly
at least 2 such edges for every Hi1 . The values of edges a1 , b1 , c1 , and e1 in
2 E(G1 )\{e1 }
3χ are 23 , 23 , 23 , and 0 respectively. This adds up to 2. Hence, since we
are dealing with convex combinations, which are weighted averages, when the
weights are taken into account, the Hi1 ’s have on average 2 edges incident to v1
each. But since every Hi1 has at least 2 such edges, it follows that every Hi1 has
exactly 2 edges incident to v1 in it.
For each 2-edge connected subgraph Hi1 which has edges a1 and b1 , denote
the corresponding convex multiplier by λab i . Define λi and λi similarly. One
ac bc
can see that the only way for the variable values of edges a1 , b1 , and c1 to end
up all being 23 in 23 χE(G1 )\{e1 } is for the following to hold:
P ab P ac P bc 1
i λi = i λi = i λi = 3 . (13)
Call the three types of 2-edge connected graphs Hij as ab-graphs, ac-graphs,
and bc-graphs. Our strategy is to combine say each ab-graph Hi1 of G1 with an
ab-graph Hj2 of G2 to form an ab-graph Hijab
of G which is also 2-edge connected.
So, we define
Hij
ab
:= (Hi1 − v1 ) + (Hj2 − v2 ) + a + b, (15)
where Hi1 and Hj2 are ab-graphs. Since Hi1 − v1 and Hj2 − v2 are both connected,
it follows that Hijab
is 2-edge connected. Similarly define Hij ac
and Hijbc
.
Now consider the following expression:
P P P
i,j 3λi µj Hij + i,j 3λi µj Hij + i,j 3λi µj Hij .
ab ab ab ac ac ac bc bc bc
(16)
One can verify that this is in fact a convex combination. Any edge f in say
G1 − v1 occurs in (16) with a weight of
P P ab P ac P bc
{i | f ∈H 1 } (λi · (3 · j µj ) + λi · (3 · j µj ) + λi · (3 · j µj )). (17)
ab ac bc
i
A New Bound for the 2-Edge Connected Subgraph Problem 123
G1 = G − v + ux + yz, (20)
G2 = G − v + uy + xz, (21)
3χ = i λi χHi , (22)
and
2 E2 \{e2 } P 2
3χ = i µi χHi . (23)
Define Ĥi1 by
Hi1 − yz + yv + zv for yz ∈ Hi1 ,
Ĥi1 = (24)
Hi1 + yv + xv for yz 6∈ Hi1 .
Every edge in f ∈ E \ δ(v) occurs with a total weight of 23 in (26) since f occured
with that weight in both (22) and (23). Since yz occurs with a total weight of 23
in (22) and xz occurs with a total weight of 23 in (23), one can verify that xv, yv,
and zv each occur with a total weight of 23 in (26) as well. Therefore, we have
2 E\{e} 1 P 1
1 P 2
4 Concluding Remarks
An obvious open problem arising from our work is to extend our strategy and
settle Conjecture 1. In another direction, it would be interesting to apply our
ideas to design a 43 -approximation algorithm for the minimum cost 2-edge- and
2-vertex-connected subgraph problems.
Another interesting question is the tightness of the bound proven in Theo-
rem 1. The examples we have been able to construct seem to demonstrate an
asymptotic ratio of 65 between the cost of a minimum cost 2-edge connected sub-
graph and that of an optimal half-integral subtour solution. Finding instances
with a worse ratio or improving our bound in Theorem 1 are open problems.
References
1. M. Balinski. On recent developments in integer programming. In H. W. Kuhn,
editor, Proceedings of the Princeton Symposium on Mathematical Programming,
pages 267–302. Princeton University Press, NJ, 1970.
2. S. Boyd and R. Carr. Finding low cost TSP and 2-matching solutions using certain
half-integer subtour vertices. Manuscript, March 1998.
3. S. Boyd and R. Carr. A new bound for the 2-matching problem. Report TR-96-07,
Department of Computer Science, University of Ottawa, Ottawa, 1996.
4. N. Christofides. Worst case analysis of a new heuristic for the traveling salesman
problem. Report 388, Graduate School of Industrial Administration, Carnegie Mel-
lon University, Pittsburgh, 1976.
5. G. N. Fredrickson and J. Ja Ja. On the relationship between the biconnectiv-
ity augmentation and traveling salesman problems. Theoretical Computer Science,
19:189–201, 1982.
6. M. X. Goemans. Worst-case comparison of valid inequalities for the TSP. Math.
Programming, 69:335–349, 1995.
7. M. X. Goemans and D. J. Bertsimas. Survivable networks, linear programming
relaxations and the parsimonious property. Math. Programming, 60:145–166, 1993.
8. M. X. Goemans, A. Goldberg, S. Plotkin, D. Shmoys, É. Tardos, and D. P. Willam-
son. Approximation algorithms for network design problems. Proceedings of the
Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’94), pages
223–232, 1994.
A New Bound for the 2-Edge Connected Subgraph Problem 125
Abstract. We give a 17 12
-approximation algorithm for the following NP-
hard problem:
Given a simple undirected graph, find a 2-edge connected span-
ning subgraph that has the minimum number of edges.
The best previous approximation guarantee was 32 . If the well known TSP
4
3
conjecture holds, then there is a 43 -approximation algorithm. Thus our
main result gets half-way to this target.
1 Introduction
Given a simple undirected graph, consider the problem of finding a 2-edge con-
nected spanning subgraph that has the minimum number of edges. The problem
is NP-hard, since the Hamiltonian cycle problem reduces to it. A number of
recent papers have focused on approximation algorithms 1 for this and other
related problems, [2]. We use the abbreviation 2-ECSS for 2-edge connected
spanning subgraph.
Here is an easy 2-approximation algorithm for the problem:
Take an ear decomposition of the given graph (see Section 2 for defini-
tions), and discard all 1-ears (ears that consist of one edge). Then the
resulting graph is 2-edge connected and has at most 2n − 3 edges, while
the optimal subgraph has ≥ n edges, where n is the number of nodes.
1
An α-approximation algorithm for a combinatorial optimization problem runs in
polynomial time and delivers a solution whose value is always within the factor α
of the optimum value. The quantity α is called the approximation guarantee of the
algorithm.
Khuller & Vishkin [8] were the first to improve on the approximation guarantee
of 2. They gave a simple and elegant algorithm based on depth-first search that
achieves an approximation guarantee of 1.5. In an extended abstract, Garg, San-
tosh & Singla [6] claimed to have a 1.25-approximation algorithm for the prob-
lem. No proof of this claim is available; on the other hand, there is no evidence
indicating that achieving an approximation guarantee of 1.25 in polynomial time
is impossible.
We improve Khuller & Vishkin’s 18 17
12 -approximation guarantee to 12 . If the
4 4
well known TSP 3 conjecture holds, then there is a 3 -approximation algorithm,
see Section 5. Thus our main result gets half-way to this target.
Let G = (V, E) be the given simple undirected graph, and let n and m denote
|V | and |E|. Assume that G is 2-edge connected.
Our method is based on a matching-theory result of András Frank, namely,
there is a good characterization for the minimum number of even-length ears
over all possible ear decompositions of a graph, and moreover, an ear decom-
position achieving this minimum can be computed efficiently, [4]. Recall that
the 2-approximation heuristic starts with an arbitrary ear decomposition of G.
Instead, if we start with an ear decomposition that maximizes the number of
1-ears, and if we discard all the 1-ears, then we will obtain the optimal solution.
In fact, we start with an ear decomposition that maximizes the number of odd-
length ears. Now, discarding all the 1-ears gives an approximation guarantee of
1.5 (see Proposition 8 below). To do better, we repeatedly apply “ear-splicing”
steps to the starting ear decomposition to obtain a final ear decomposition such
that the number of odd-length ears is the same, and moreover, the internal nodes
of distinct 3-ears are nonadjacent. We employ two lower bounds to show that
discarding all the 1-ears from the final ear decomposition gives an approximation
guarantee of 1712 . The first lower bound is the “component lower bound” due to
Garg et al [6, Lemma 4.1], see Proposition 4 below. The second lower bound
comes from the minimum number of even-length ears in an ear decomposition
of G, see Proposition 7 below.
After developing some preliminaries in Sections 2 and 3, we present our
heuristic in Section 4. Section 5 shows that the well known 43 conjecture for the
metric TSP implies that there is a 43 -approximation algorithm for a minimum-
size 2-ECSS, see Theorem 18. Almost all of the results in Section 5 are well
known, but we include the details to make the paper self-contained. Section 6
has two examples showing that our analysis of the heuristic is tight. Section 6
also compares the two lower bounds with the optimal value.
A Useful Assumption
For our heuristic to work, it is essential that the given graph be 2-node con-
nected. Hence, in Section 4 of the paper where our heuristic is presented, we
will assume that the given graph G is 2-node connected. Otherwise, if G is not
2-node connected, we compute the blocks (i.e., the maximal 2-node connected
subgraphs) of G, and apply the algorithm separately to each block. We compute
a 2-ECSS for each block, and output the union of the edge sets as the edge set of
128 Joseph Cheriyan et al.
a 2-ECSS of G. The resulting graph has no cut edges since the subgraph found
for each block has no cut edge, and moreover, the approximation guarantee for
G is at most the maximum of the approximation guarantees for the blocks.
2 Preliminaries
Except in Section 5, all graphs are simple, that is, there are no loops nor multi-
edges. A closed path means a cycle, and an open path means that all the nodes
are distinct.
An ear decomposition of the graph G is a partition of the edge set into open
or closed paths, P0 + P1 + . . . + Pk , such that P0 is the trivial path with one
node, and each Pi (1 ≤ i ≤ k) is a path that has both end nodes in Vi−1 =
V (P0 ) ∪ V (P1 ) ∪ . . . ∪ V (Pi−1 ) but has no internal nodes in Vi−1 . A (closed
or open) ear means one of the (closed or open) paths P0 , P1 , . . . , Pk in the ear
decomposition, and for a nonnegative integer `, an `-ear means an ear that has `
edges. An `-ear is called even if ` is an even number, otherwise, the `-ear is called
odd. (The ear P0 is always even.) An open ear decomposition P0 + P1 + . . . + Pk
is one such that all the ears P2 , . . . , Pk are open.
An odd ear decomposition is one such that every ear (except the trivial path
P0 ) has an odd number of edges. A graph is called factor-critical if for every node
v ∈ V (G), there is a perfect matching in G − v. The next result gives another
characterization of factor-critical graphs.
Let ε(G) denote the minimum number of edges in a 2-ECSS of G. For a graph
H, let c(H) denote the number of (connected) components of H. Garg et al [6,
Lemma 4.1] use the following lower bound on ε(G).
The next result is not useful for our main result, but we include it for com-
pleteness.
Proof. Let t be the number of internal nodes in the odd ears of P0 +P1 +. . .+Pk .
(Note that the node in P0 is not counted by t.) Then, the number of edges
contributed to E 0 by the odd ears is ≤ 3t/2, and the number of edges contributed
to E 0 by the even ears is ≤ ϕ+|V |−t−1. By applying Proposition 7 (and the fact
that ε(G) ≥ |V |) we get, |E 0 |/ε(G) ≤ (t/2 + ϕ + |V | − 1)/ max(|V |, ϕ + |V | − 1) ≤
(t/2|V |) + (ϕ + |V | − 1)/(ϕ + |V | − 1) ≤ 1.5. t
u
Property (α)
(0) the number of even ears is the same in P0 + P1 + . . . + Pk and in Q0 + Q1 +
. . . + Qk ,
(1) every 3-ear Qi is a pendant ear,
(2) for every pair of 3-ears Qi and Qj , there is no edge between an internal node
of Qi and an internal node of Qj , and
(3) every 3-ear Qi is open.
Proof. The proof is by induction on the number of ears. The result clearly holds
for k = 1. Suppose that the result holds for (j − 1) ears P0 + P1 + . . . + Pj−1 . Let
An Approximation Algorithm for 2-Edge Connected Spanning Subgraphs 131
Q00 + Q01 + . . .+ Q0j−1 be the corresponding ear decomposition that satisfies prop-
erty (α). Consider the open ear Pj , j ≥ 2. Let Pj be an `-ear, v1 , v2 , . . . , v` , v`+1 .
Possibly, ` = 1. (So v1 and v`+1 are the end nodes of Pj , and v1 6= v`+1 .)
Let T denote the set of internal nodes of the 3-ears of Q00 + Q01 + . . . + Q0j−1 .
Suppose Pj is an ear of length ` ≥ 2 with exactly one end node, say, v1 in T .
Let Q0i = w1 , v1 , w3 , w4 be the 3-ear having v1 as an internal node. We take
Q0 = Q00 , . . . , Qi−1 = Q0i−1 , Qi = Q0i+1 , . . . , Qj−2 = Q0j−1 . Moreover, we take
Qj−1 to be the (` + 2)-ear obtained by adding the last two edges of Q0i to Pj , i.e.,
Qj−1 = w4 , w3 , v1 , v2 , . . . , v` , v`+1 , and we take Qj to be the 1-ear consisting of
the first edge w1 v1 of Q0i . Note that the parities of the lengths of the two spliced
ears are preserved, that is, Qj−1 is even (odd) if and only if Pj is even (odd),
and both Qj and Q0i are odd. Hence, the number of even ears is the same in
P0 + P1 + . . . + Pj and in Q0 + Q1 + . . . + Qj .
Now, suppose Pj has both end nodes v1 and v`+1 in T . If there is one 3-ear
Q0i that has both v1 and v`+1 as internal nodes (so ` ≥ 2), then we take Qj−1
to be the (` + 2)-ear obtained by adding the first edge and the last edge of Q0i
to Pj , and we take Qj to be the 1-ear consisting of the middle edge v1 v`+1 of
Q0i . Also, we take Q0 = Q00 , . . . , Qi−1 = Q0i−1 , Qi = Q0i+1 , . . . , Qj−2 = Q0j−1 .
Observe that the number of even ears is the same in P0 + P1 + . . . + Pj and in
Q 0 + Q1 + . . . + Qj .
If there are two 3-ears Q0i and Q0h that contain the end nodes of Pj , then we
take Qj−2 to be the (` + 4)-ear obtained by adding the last two edges of both Q0i
and Q0h to Pj , and we take Qj−1 (similarly, Qj ) to be the 1-ear consisting of the
first edge of Q0i (similarly, Q0h ). (For ease of description, assume that if a 3-ear
has exactly one end node v of Pj as an internal node, then v is the second node
of the 3-ear.) Also, assuming i < h, we take Q0 = Q00 , . . . , Qi−1 = Q0i−1 , Qi =
Q0i+1 , . . . , Qh−2 = Q0h−1 , Qh−1 = Q0h+1 , . . . , Qj−3 = Q0j−1 . Again, observe that
the number of even ears is the same in P0 +P1 +. . .+Pj and in Q0 +Q1 +. . .+Qj .
If the end nodes of Pj are disjoint from T , then the proof is easy (take
Qj = Pj ). Also, if Pj is a 1-ear with exactly one end node in T , then the proof
is easy (take Qj = Pj ).
The proof ensures that in the final ear decomposition Q0 + Q1 + . . . + Qk ,
every 3-ear is pendant and open, and moreover, the internal nodes of distinct 3-
ears are nonadjacent. We leave the detailed verification to the reader. Therefore,
the ear decomposition Q0 + Q1 + . . . + Qk satisfies property (α). t
u
Remark 10. In the induction step, which applies for j ≥ 2 (but not for j = 1),
it is essential that the ear Pj is open, though Q0i (and Q0h ) may be either open
or closed. Our main result (Theorem 12) does not use part (3) of property (α).
Our approximation algorithm for a minimum-size 2-ECSS computes the ear
decomposition Q0 + Q1 + . . . + Qk satisfying property (α), starting from an open
evenmin ear decomposition P0 + P1 + . . . + Pk . (Note that Q0 + Q1 + . . . + Qk
is an evenmin ear decomposition.) Then, the algorithm discards all the edges
in 1-ears. Let the resulting graph be G0 = (V, E 0 ). G0 is 2-edge connected by
Proposition 1.
132 Joseph Cheriyan et al.
Theorem 12. Given a 2-edge connected graph G = (V, E), the above algorithm
finds a 2-ECSS G0 = (V, E 0 ) such that |E 0 |/ε(G) ≤ 17
12 . The algorithm runs in
time O(|V | · |E|).
Proof. By the previous lemma and Proposition 7,
We claim that
t 5(n + ϕ(G) − 1)
|E 0 | ≤+ .
4 4
To see this, note that the final ear decomposition Q0 + Q1 + . . . + Qk satisfies
the following: (i) the number of edges contributed by the 3-ears is 3t/2; (ii) the
number of edges contributed by the odd ears of length ≥ 5 is ≤ 5q/4, where q is
the number of internal nodes in the odd ears of length ≥ 5; and (iii) the number
of edges contributed by the even ears of length ≥ 2 is ≤ ϕ(G) + (n − t − q − 1),
since there are ϕ(G) such ears and they have a total of (n − t − q − 1) internal
nodes. (The node in Q0 is not an internal node of an ear of length ≥ 1.)
The approximation guarantee follows since
|E 0 | t/4 + 5(n + ϕ(G) − 1)/4
≤
ε(G) ε(G)
t/4 + 5(n + ϕ(G) − 1)/4
≤
max(n + ϕ(G) − 1, 3t/2)
t 2 5(n + ϕ(G) − 1) 1
≤ +
4 3t 4 n + ϕ(G) − 1
17
= .
12
t
u
4
5 Relation to the TSP 3
Conjecture
This section shows that the well known 43 conjecture for the metric TSP (due
to Cunningham (1986) and others) implies that there is a 43 -approximation al-
gorithm for a minimum-size 2-ECSS, see Theorem 18. Almost all of the results
An Approximation Algorithm for 2-Edge Connected Spanning Subgraphs 133
in this section are well known, except possibly Fact 13, see [1,3,5,7,11,13]. The
details are included to make the paper self-contained.
In the metric TSP (traveling salesman problem), we are given a complete
graph G0 = Kn and edge costs c0 that satisfy the triangle inequality (c0vw ≤
c0vu + c0uw , ∀v, w, u ∈ V ). The goal is to compute c0T SP , the minimum cost of a
Hamiltonian cycle.
Recall our 2-ECSS problem: Given a simple graph G = (V, E), compute ε(G),
the minimum size of a 2-edge connected spanning subgraph. Here is the multiedge
(or uncapacitated) version of our problem. Given G = (V, E) as above, compute
µ(G), the minimum size (counting multiplicities) of a 2-edge connected spanning
submultigraph H = (V, F ), where F is a multiset such that e ∈ F =⇒ e ∈ E.
(To give an analogy, if we take ε(G) to correspond to the f -factor problem, then
µ(G) corresponds to the f -matching problem.)
Proof. Let H = (V, F ) give the optimal solution for µ(G). If H uses two copies
of an edge vw, then we can replace one of the copies by some other edge of G
in the cut given by H − {vw, vw}. In other words, if S is the node set of one of
the two components of H − {vw, vw}, then we replace one copy of vw by some
edge from δG (S) − {vw}. t
u
Remark 14. The above is a lucky fact. It fails to generalize, both for minimum-
cost (rather than minimum-size) 2-ECSS, and for minimum-size k-ECSS, k ≥ 3.
Fact 15. Let G be a 2-edge connected graph, and let c assign unit costs to the
edges. The minimum cost of the TSP on the metric completion of G, c, satisfies
c0T SP ≥ µ(G) = ε(G).
c0T SP = minimize c0 · x
subject to x(δ(v)) = 2, ∀v ∈ V
x(δ(S)) ≥ 2, ∀S ⊂ V, ∅ =
6 S 6= V
x ≥ 0,
x ∈ ZZ .
134 Joseph Cheriyan et al.
4
TSP 4
3 Conjecture. If c0 is a metric, then c0T SP ≤ zST .
3
To derive the lower bound zST ≤ ε(G), we need a result of Goemans &
Bertsimas on the subtour LP, [7, Theorem 1]. In fact, a special case of this result
that appeared earlier in [11, Theorem 8] suffices for us.
Proposition 17 (Parsimonious property [7]). Consider the TSP on G0 =
(V, E 0 ), c0 , where G0 = K|V | . Assume that the edge costs c0 form a metric, i.e.,
c0 satisfies the triangle inequality. Then the optimal value of the subtour LP
remains the same even if the constraints {x(δ(v)) = 2, ∀v ∈ V } are omitted.
Note that this result does not apply to the subtour integer program given
above.
Let z2CUT denote the optimal value of the LP obtained from the subtour LP
by removing the constraints x(δ(v)) = 2 for all nodes v ∈ V . The above result
states that if c0 is a metric, then zST = z2CUT . Moreover, for a 2-edge connected
graph G and unit edge costs c = 1l, we have z2CUT ≤ µ(G) = ε(G), since µ(G) is
the optimal value of the integer program whose LP relaxation has optimal value
z2CUT . (Here, z2CUT is the optimal value of the LP on the metric completion of
G, c.) Then, by the parsimonious property, we have zST = z2CUT ≤ ε(G). The
main result in this section follows.
4
Theorem 18. Suppose that the TSP 3 conjecture holds. Then
4
zST ≤ ε(G) ≤ c0T SP ≤ zST .
3
A 43 -approximation of the minimum-size 2-ECSS is obtained by computing
4
3 zST on the metric completion of G, c, where c = 1l.
proved that the TSP tour found by the Christofides heuristic achieves an approx-
imation guarantee of 1.5. Simpler proofs of this result based on Theorem 16 were
found later by Cunningham (see [11, Theorem 8]) and by Goemans & Bertsimas
[7, Theorem 4].
Consider the minimum-cost 2-ECSS problem on a 2-edge connected graph
G = (V, E) with nonnegative edge costs c. Let the minimum cost of a simple 2-
ECSS and of a multiedge 2-ECSS be denoted by cε and cµ , respectively. Clearly,
cε ≥ cµ . Even for the case of arbitrary nonnegative costs c, we know of no exam-
cµ 7 cµ 7
ple where > . There is an example G, c with ≥ . Take two copies of
zST 6 zST 6
K3 , call them C1 , C2 , and add three disjoint length-2 paths P1 , P2 , P3 between
C1 and C2 such that each node of C1 ∪ C2 has degree 3 in the resulting graph G.
In other words, G is obtained from the triangular prism C6 by subdividing once
each of the 3 “matching edges”. Assign a cost of 2 to each edge in C1 ∪ C2 , and
assign a cost of 1 to the remaining edges. Then cε = cµ = 14, as can be seen by
taking 2 edges from each of C1 , C2 , and all 6 edges of P1 ∪ P2 ∪ P3 . Moreover,
zST ≤ 12, as can be seen by taking xe = 1/2 for each of the 6 edges e in C1 ∪ C2 ,
and taking xe = 1 for the remaining 6 edges e in P1 ∪ P2 ∪ P3 .
6 Conclusions
References
1. R. Carr and R. Ravi. A new bound for the 2-edge connected subgraph problem. In
R. E. Bixby, E. A. Boyd, and R. Z. Rı́os-Mercado, editors, Integer Programming
and Combinatorial Optimization: Proceedings of the 6th International Conference
on Integer Programming and Combinatorial Optimization, LNCS, Vol. 1412, pages
110–123. Springer, 1998. This volume.
2. J. Cheriyan and R. Thurimella. Approximating minimum-size k-connected span-
ning subgraphs via matching. Proc. 37th Annual IEEE Sympos. on Foundat. of
Comput. Sci., pages 292–301, 1996.
3. N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman
problem. Technical report, G.S.I.A., Carnegie-Mellon Univ., Pittsburgh, PA, 1976.
4. A. Frank. Conservative weightings and ear-decompositions of graphs. Combinator-
ica, 13:65–81, 1993.
5. G. L. Frederickson and J. Ja’Ja’. On the relationship between the biconnectivity
augmentation and traveling salesman problems. Theor. Comp. Sci., 19:189–201,
1982.
6. N. Garg, V. S. Santosh, and A. Singla. Improved approximation algorithms for
biconnected subgraphs via better lower bounding techniques. Proc. 4th Annual
ACM-SIAM Symposium on Discrete Algorithms, pages 103–111, 1993.
7. M. X. Goemans and D. J. Bertsimas. Survivable networks, linear programming
relaxations and the parsimonious property. Mathematical Programming, 60:143–
166, 1993.
8. S. Khuller and U. Vishkin. Biconnectivity approximations and graph carvings.
Journal of the ACM, 41:214–235, 1994. Preliminary version in Proc. 24th Annual
ACM STOC,pages 759–770, 1992.
9. L. Lovász. A note on factor-critical graphs. Studia Sci. Math. Hungar., 7:279–280,
1972.
10. L. Lovász and M. D. Plummer. Matching Theory. Akadémiai Kiadó, Budapest,
1986.
11. C. L. Monma, B. S. Munson, and W. R. Pulleyblank. Minimum-weight two-
connected spanning networks. Mathematical Programming, 46:153–171, 1990.
12. H. Whitney. Nonseparable and planar graphs. Trans. Amer. Math. Soc., 34:339–
362, 1932.
13. L. A. Wolsey. Heuristic analysis, linear programming and branch and bound. Math-
ematical Programming Study, 13:121–134, 1980.
Multicuts in Unweighted Graphs with Bounded
Degree and Bounded Tree-Width
1 Introduction
Multicommodity Flow problems have been intensely studied for decades [7,11,9],
[13,15,17] because of their practical applications and also of the appealing hard-
ness of several of their versions. The fractional version of a Multicut problem
is the dual of a Multicommodity Flow problem and, therefore, Multicut is of
similar interest [3,9,10,13,20].
?
Research supported in part by NSF grant CCR-9319106.
??
Research partially supported by NSF grant CCR-9319106 and by FAPESP (Proc.
96/04505–2).
???
Research supported in part by ProNEx (MCT/FINEP) (Proj. 107/97) and FAPESP
(Proc. 96/12111–4).
SNP-hard in binary trees, therefore letting the input graph be weighted makes
the problem harder. Finally, we show that Unweighted Edge Multicut is Max
SNP-hard if the input graphs are walls. Walls, to be formally defined in Sec-
tion 4, have degree at most three and there are walls with tree-width as large as
we wish. We conclude that letting the input graph have unbounded tree-width
makes the problem significantly harder.
In Section 2 we present the polynomial-time algorithm for Unrestricted Ver-
tex Multicut in trees and the polynomial-time approximation scheme for Unre-
stricted Vertex Multicut in bounded-tree-width graphs. In Section 3, we show the
approximation-preserving reduction from Edge Multicut to Unrestricted Vertex
Multicut. Finally, in Section 4 we present our hardness results.
Algorithm:
Input: a tree T .
Start with S = ∅.
Call a pair (si , ti ) in C active if it is not disconnected by S.
Traverse the tree in postorder.
Multicuts in Unweighted Graphs 141
Clearly the following invariant holds: all non-active pairs in C are discon-
nected by S. A pair in C that becomes non-active does not go back to active
since we never remove vertices from S. At the end of the algorithm, no pair in
C is active, meaning that S is a solution for the problem. For the minimality
of S, note that the paths joining si to ti in T for all marked pairs (si , ti ) form
a pairwise disjoint collection of paths. Any solution should contain at least one
vertex in each of these paths. But there are |S| marked paths, meaning that
any solution has at least |S| vertices. This implies that |S| is a minimum-size
solution. Besides, it is not hard to see that the algorithm can be implemented
in polynomial time.
Get (u, A), which returns a vertex u of T i−1 and a solution A for Gi−1 (u) such
that |A| ≤ (1 + )opt(Gi−1 (u)) and Xui−1 ⊆ A. Then the algorithm starts a new
iteration with Gi = Gi−1 \ Gi−1 (u), Θi = (T i , (Xwi )w∈V (T i ) ), where T i = T i−1 \
T i−1 (u) and Xwi = Xwi−1 \ V (Gi−1 (u)), for all w ∈ V (T i ), and S i = S i−1 ∪ A.
The formal description of the algorithm appears in Figure 2.1.
Algorithm:
G0 ← G;
Θ0 ← Θ;
S 0 ← ∅;
i ← 1;
while Gi−1 6= ∅ do
Get (ui , Ai ); /* |Ai | ≤ (1 + )opt(Gi−1 (ui )) and Xui−1 ⊆ Ai */
i i−1 i−1
G ←G \ G (ui );
T i ← T i−1 \ T i−1 (ui );
i i−1
Xw ← Xw \ V (Gi−1 (ui )), for each w ∈ V (T i );
S i ← S i−1 ∪ Ai ;
i ← i + 1;
endwhile;
f ← i − 1;
output S f .
We will postpone the description of Get (u, A) and, for now, assume that it
works correctly and in polynomial time. The next lemma states a property of
tree decompositions that we will use later.
of Xui−1
i
in the segment of P from s to y. Since Xui−1
i
⊆ S f , there is a vertex of
P in S . If y is not in G
f i−1
\ G (ui ), then y is not in Gi−1 . This means y is in
i−1
G (uj ), for some j < i. Moreover, s is in Gj−1 \ Gj−1 (uj ) (because this is a
j−1
Lemma 3. |S f | ≤ (1 + )opt(G).
X
f
= (1 + ) opt(Gi−1 (ui )) ≤ (1 + )opt(G),
i=1
3 Edge Multicut
In this section we show that Edge Multicut can be reduced to Unrestricted
Vertex Multicut by a reduction that preserves approximability.
The reduction has the following property. If the instance of Edge Multicut is
a graph with bounded degree and bounded tree-width, then the corresponding
instance of Unrestricted Vertex Multicut has bounded tree-width.
Given a graph G = (V, E), the line graph of G is the graph whose vertex set
is E and such that two of its vertices (edges of G) are adjacent if they share an
endpoint in G. In other words, the line graph of G is the graph (E, L), where
L = {ef : e, f ∈ E and e and f have a common endpoint}.
Consider an instance of Edge Multicut, that is, a graph G = (V, E) and a set C
of pairs of distinct vertices of G. Let us describe the corresponding instance of
Unrestricted Vertex Multicut. The input graph for Unrestricted Vertex Multicut
is the line graph of G, denoted by G0 . Now let us describe the set of pairs of
vertices of G0 . For each pair (s, t) in C, we have in C 0 all pairs (e, f ) such that e
has s as endpoint and f has t as endpoint.
Clearly G0 can be obtained from G in polynomial time. Note that C 0 has at
most k∆2 pairs, where k = |C| and ∆ is the maximum degree of G. Also C 0 can
be obtained from G and C in polynomial time.
The following theorem completes the reduction.
by the description of Edge Multicut, s 6= t.) Let e be the first edge of P and f
the last one (possibly e=f). Clearly s is incident to e, and t to f . Thus (e, f ) is a
pair in C 0 . Corresponding to P , there is a path P 0 in G0 from e to f containing
as vertices all edges of P . Since S is a solution for Unrestricted Vertex Multicut
in G0 and (e, f ) is in C 0 , S must contain a vertex of P 0 . Therefore there is an
edge of P in S, which implies that S is a solution of Edge Multicut in G.
The next lemma shows the previously mentioned property of this reduction.
Lemma 5. If G has bounded degree and bounded tree-width, then the line graph
of G has bounded tree-width.
In fact we know how to implement the PTAS given in Section 2.1, for Edge
Multicut in bounded-degree trees, in time O((n + k)d1/eddd1/e+2 ), where n
is the number of vertices of the tree, k is the number of (si , ti ) pairs, d is the
maximum degree of the tree and 1 + is the desired approximation ratio of the
algorithm. The size of the input is Θ(n + k). We omit the description of this
linear-time implementation in this extended abstract.
146 Gruia Călinescu et al.
4 Complexity Results
x3
_
xi xi
_
x1 x2
x3 x3
_ _ _ _ _
x1 x1 x2 x2 x3 x3 x1 x2 x1 x2
Fig. 2. (a) The gadget for variable xi . (b) The gadget for clause Cj =
{x1 , x2 , x3 }. (c) Tree T built for the instance Φ = (x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x2 ∨ x3 ),
that is, C1 = {x1 , x2 , x3 } and C2 = {x1 , x2 , x3 }.
1. For each variable xi , S contains the edge in the gadget for xi incident to the
leaf labeled xi if xi =TRUE or to the leaf labeled xi if xi =FALSE.
2. For each clause Cj , S contains two distinct edges in the gadget for Cj . These
edges are such that (1) they disconnect the two pairs in the gadget, and (2)
the only leaf that is still connected to the root of the gadget is a leaf with
a label x̃i ∈ Cj such that x̃i =TRUE. (The four possible choices for the two
edges are shown in Figure 3.)
r r r r
v v
v v
Fig. 3. Possible choices of two edges, the dashed edges, in the gadget for a clause
that leave exactly one leaf (the marked leaf v) connected to the root r.
For each clause Cj , there is exactly one leaf v in the gadget for Cj that is
connected to the root r of the gadget. Let x̃i ∈ {xi , xi } be the label for this leaf.
There is a pair formed by this leaf v and the leaf in the gadget for xi whose label
is x̃i . In S, there must be an edge e in the path between these two leaves. Since
leaf v is connected to the root r of the gadget for Cj and all edges in S are either
in a variable gadget or in a clause gadget, this edge e has to be in the variable
gadget. This means e is the edge incident to the leaf labeled x̃i in the gadget
for xi . Hence x̃i =TRUE, and the clause is satisfied. Since this holds for all the
clauses, the given assignment makes Φ TRUE, implying that Φ is satisfiable.
We omit the proof. The construction is similar to the one used in Theorem 7.
We omit the proof. The construction is similar to the one used in Theorem 7.
Proof sketch. Let us reduce Edge Multicut in stars to Weighted Edge Multicut
in binary trees. From an instance of the Unweighted Edge Multicut restricted
to stars, we construct an instance of the Weighted Edge Multicut restricted to
binary trees in the following way: for each leaf of the star S, there is a corre-
sponding leaf in the binary tree T . The pairs are the same (we may assume there
is no pair involving the root of the star). We connect the leaves of T arbitrarily
into a binary tree. The edges in T incident to the leaves get weight one and all
other edges of T get weight 2n + 1, where n is the number of leaves in the star
S (which is the same as the number of leaves in the tree T we construct). Any
solution within twice the optimum for the Weighted Edge Multicut instance we
constructed will contain only edges of T incident to the leaves, since any other
edge is too heavy (removing all edges incident to the leaves, we get a solution of
weight n). Then it is easy to see that any optimal solution for the Weighted Edge
Multicut instance we constructed corresponds to an optimal solution for the orig-
inal Unweighted Multicut star instance, and vice versa. Also approximability is
preserved by this reduction.
A wall of height h consists of h + 1 vertex disjoint paths R0 , . . . , Rh , which
we call rows, and h + 1 vertex disjoint paths L0 , . . . , Lh , which we call columns.
A wall of height six is depicted in Figure 4 (a). The reader should be able to
complete the definition by considering Figure 4 (a). The formal definition is as
follows. Each row is a path of 2h + 2 vertices. Each column, a path with 2h + 2
vertices. Column r contains the (2r + 1)st and the (2r + 2)nd vertices of all rows,
as well as the edge between them. For i < h and even, each Lr contains an edge
between the (2r + 2)nd vertex of Ri and the (2r + 2)nd vertex of Ri+1 . For i < h
Multicuts in Unweighted Graphs 149
(a)
L0 L1 Lr Lh
R0
R1
Ri
Rh
(b)
_ _
x1 x2 x3 x1 x2 x3
Fig. 4. (a) A wall of height six. The dark edges indicate row Ri and column Lr .
(b) The three last rows of the wall built from Φ = (x1 ∨ x2 ∨ x3 )(x1 ∨ x2 ∨ x3 ).
and odd, each Lr contains an edge between the (2r + 1)st vertex of Ri and the
(2r + 1)st vertex of Ri+1 . These are all the edges of the wall.
We prove that Edge, Vertex and Unrestricted Vertex Multicut are Max SNP-
hard in walls. This means, by Arora et al. [1], that there is a constant > 0
such that the existence of a polynomial-time approximation algorithm for any
of the three versions of Multicut with performance ratio at most 1 + implies
that P=NP.
As in [18], we use the concept of L-reduction, which is a special kind of
reduction that preserves approximability.
Let A and B be two optimization problems. We say A L-reduces to B if there
are two polynomial-time algorithms f and g, and positive constants α and β,
such that for each instance I of A,
1. Algorithm f produces an instance I 0 = f (I) of B, such that the optima
of I and I 0 , of costs denoted OptA (I) and OptB (I 0 ) respectively, satisfy
OptB (I 0 ) ≤ α · OptA (I), and
2. Given any feasible solution of I 0 with cost c0 , algorithm g produces a solution
of I with cost c such that |c − OptA (I)| ≤ β · |c0 − OptB (I 0 )|.
Theorem 12. Edge, Vertex and Unrestricted Vertex Multicut are Max SNP-
hard in walls.
Proof sketch. The reduction is from the well-known Max SNP-hard problem
MAX 3-SAT [18]. We show the reduction for Unrestricted Vertex Multicut. The
other two reductions are similar.
The first part of the L-reduction is the polynomial-time algorithm f and
the constant α. Given any instance Φ of MAX 3-SAT, f produces an instance
W, C of Unrestricted Vertex Multicut such that W is a wall. Also, the cost of
150 Gruia Călinescu et al.
Acknowledgments
The first two authors would like to thank Howard Karloff for suggesting the
problem, and for some helpful discussions.
Multicuts in Unweighted Graphs 151
References
20. É. Tardos and V. V. Vazirani. Improved bounds for the max-flow min-multicut
ratio for planar and Kr,r -free graphs. Information Processing Letters, 47(2):77-80,
1993.
21. J. van Leeuwen. Graph algorithms. Handbook of Theoretical Computer Science,
Vol. A, chapter 10, pages 525–631. The MIT Press/Elsevier, 1990.
Approximating Disjoint-Path Problems Using
Greedy Algorithms and Packing Integer
Programs ?
1 Introduction
This paper examines approximation algorithms for disjoint-path problems and
their generalizations. In the edge( vertex)-disjoint path problem, we are given a
graph G = (V, E) and a set T of connection requests, also called commodities.
Every connection request in T is a vertex pair (si , ti ), 1 ≤ i ≤ K. The objective
is to connect a maximum number of the pairs via edge( vertex)-disjoint paths.
For the vertex-disjoint paths problem, the connection requests are assumed to be
disjoint. We call the set of connected pairs realizable. A generalization of the edge-
disjoint paths problem is multiple-source unsplittable flow. In this problem every
commodity k in the set T has an associated demand ρk , and every edge e has a
capacity ue . The demand ρk must be routed on a single path from sk to tk . The
objective is to maximize the sum of the demands that can be fully routed while
respecting the capacity constraints. Wlog, we assume that maxk ρk = 1, and
following the standard definition of the problem in the literature, ue ≥ 1, ∀e ∈
E. When all demands and capacities are 1 in the multiple-source unsplittable
?
Research partly supported by NSF Award CCR-9308701 and NSF Career Award
CCR-9624828.
flow problem we obtain the edge-disjoint path problem. (See [10,14] for further
applications and motivation for unsplittable flow.) In all the above problems
one can assign a weight wi ≤ 1 to each connection request and seek to find a
realizable set of maximum total weight. In this paper we will state explicitly
when we deal with the weighted version of a problem.
Both the edge- and vertex-disjoint path problems are fundamental, exten-
sively studied (see e.g. [26,6,27,21,10,13,3]), NP-hard problems [9], with a mul-
titude of applications in areas such as telecommunications, VLSI and schedul-
ing. Despite the attention they have received, disjoint-path problems on general
graphs remain notoriously hard in terms of approximation; p even for edge-disjoint
paths, no algorithm is known which can find even an ω(1/ |E|) fraction of the
realizable paths.
In approximating these problems, we use the traditional notion of a ρ-approxi-
mation algorithm, ρ > 1, which is one that outputs, in polynomial time, a real-
izable set of size at least 1/ρ times the optimum. We will also give and refer to
algorithms which output a realizable set whose size is a non-linear function of
the optimum OP T , such as OP T 2 /|E|.
Overview of Previous Work. Two main approaches have been followed for ap-
proximation.
(i) The first approach, which we call the rounding approach, consists of solving a
fractional relaxation and then use rounding techniques to obtain an integral solu-
tion. The fractional relaxation is typically multicommodity flow and the rounding
techniques used to date involved sophisticated and non-standard use of random-
ized rounding [31]. The objective value of the resulting solution is compared to
the fractional optimum y ∗ , which is an upper bound on the integral optimum,
OPT. This approach has been the more successful one and recently yielded the
first approximation algorithm for uniform unsplittable flow [31] which is the spe-
cial case of unsplittable flow where all the capacities have the same value. Let d
denote the dilation of the fractional solution, i.e. the maximum length of a flow
path in the fractional relaxation. Bounds that rely on the dilation are particu-
larly appealing for expander graphs where it is known that d = O(polylog(n))
[16,12]. The rounding approach yields, for unweighted uniform unsplittable flow
(and thus for unweighted p edge-disjoint paths as well) a realizable set of size
Ω(max{(y ∗ )2 /|E|, y ∗ / |E|, y ∗ /d}) and an Ω(max{(y ∗ )2 /|E|, y ∗ /d}) bound for
the weighted version [31] . This p approach is known to have limitations, e.g.
it is known that a gap of Ω( |V |) exists between the fractional and integral
optima for both the edge- and vertex-disjoint path problems on a graph with
|E| = Θ(|V |) [7].
(ii) Under the second approach, which we call the routing approach, a commodity
is never split, i.e. routed fractionally along more than one path during the course
of the algorithm. In the analysis, the objective value of the solution is compared
to an estimated upper bound on the OP T. This approach has found very limited
applicability so far, one reason being the perceived hardness of deriving upper
bounds on OP T without resorting to a fractional relaxation. The only example
of this method we are aware of is the on-line Bounded Greedy Algorithm in
Approximating Disjoint-Path Problems 155
[10] whose approximation guarantee depends also on the diameter of the graph.
The algorithm can be easily modified
p into an p
off-line procedure that outputs
Ω(OP T / |E|) (Ω(OP T / |V |)) for edge( vertex)-disjoint
realizable sets of size p
paths. The Ω(OP T / |V |) bound is the best known bound to date for vertex-
disjoint paths.
We turn to the rounding approach (approach (i)) to handle the weighted dis-
joint path and unsplittable flow problems. We propose the use of packing integer
programs as a unifying framework that abstracts away the need for customized
and complex randomized rounding schemes. A packing integer program is of the
form maximize cT · x, subject to Ax ≤ b, A, b, c ≥ 0. We first develop, as part
of our tools, an improved approximation algorithm for a class of packing integer
programs, called column restricted, that are relevant to unsplittable flow prob-
lems. Armed with both this new algorithm and existing algorithms for general
packing integer programs, we show how packing formulations both provide a
unified and simplified derivation of many results from [31] and lead to new ones.
In particular, we obtain the first approximation algorithm for weighted multiple-
source unsplittable flow on networks with arbitrary demands and capacities and
the first approximation algorithm for weighted vertex-disjoint paths. Further, we
believe that our new algorithm for column-restricted packing integer programs
is of independent interest. We now elaborate on our results under the rounding
approach, providing further background as necessary.
Packing integer programs are a well-studied class of integer programs that can
model several NP-complete problems, including independent set, hypergraph
k-matching [19,1], job-shop scheduling [23,28,33,20] and many flow and path
related problems. Many of these problems seem to be difficult to approximate,
and not much is known about their worst-case approximation ratios. Following
[30] a packing integer program (PIP) is defined as follows.
Approximating Disjoint-Path Problems 157
Definition 1. Given A ∈ [0, 1]m×n , b ∈ [1, ∞)m and c ∈ [0, 1]n with maxj cj =
1, a PIP P = (A, b, c) seeks to maximize cT · x subject to x ∈ Z+n
and Ax ≤ b.
Constraints of the form 0 ≤ xj ≤ dj are also allowed. If A ∈ {0, 1}m×n, each
entry of b is assumed integral. Let B = mini bi , and α be the maximum number
of non-zero entries in any column of A.
The parameters B and α in the definition above appear in the approximation
bounds. For convenience we call bi the capacity of row i. The restrictions on the
values of the entries of A, b, c are wlog; the values in an arbitrary packing program
can be scaled to satisfy the above requirements [29]. We will state explicitly when
some packing program in this paper deviates from these requirements. When
A ∈ {0, 1}m×n, we say that we have a (0, 1)-PIP.
New Results for Column-Restricted PIP’s. The above results show that for vari-
ous combinations of values for y ∗ , m and B, the bounds obtained for a (0, 1)-PIP
are significantly better than those for general PIP’s. In fact they are always better
when y ∗ < m. As another example, the approximation ratio m1/(B+1) obtained
for a (0, 1)-PIP is polynomially better than the approximation ratio of a PIP with
the same parameters. Thus it is natural to ask whether we can bridge this gap.
We make progress in this direction by defining a column-restricted PIP Pr as one
where all non-zero entries of the j-th column of A have the same value ρj ≤ 1.
Column-restricted PIP’s arise in applications such as unsplittable flow problems
(see next section). We show how to obtain approximation guarantees for column-
restricted PIP’s that are similar to the ones obtained for (0, 1)-PIP’s. Let yr∗ de-
note the optimum of the linear relaxation of Pr . We obtain an integral solution
of value Ω(yr∗ /m1/(B+1) ) and Ω(yr∗ /α1/B ). Letting σ(yr∗ ) = Ω(yr∗ (yr∗ /m)1/B ) we
also obtain a bound that is at least as good as σ(yr∗ ) for yr∗ < m log n and in any
case it is never worse by more than a O(log1/B n) factor. Finally we show how to
improve upon the stated approximations when maxj ρj is bounded away from 1.
We develop the latter two results in a more complete version of this paper [15].
We now give an overview of our technique. First we find an optimum solution
x∗ to the linear relaxation of the column-restricted PIP Pr . We partition the ρj ’s
into a fixed number of intervals according to their values and generate a packing
subproblem for each range. In a packing subproblem P L corresponding to range
L, we only include the columns of A with ρj ∈ L and to each component of
the bL -vector we allocate only a fraction of the original bi value, a fraction
158 Stavros G. Kolliopoulos and Clifford Stein
our usage of packing in the rounding algorithms we have assumed that the pa-
rameter B of the packing program is equal to 1. Allowing B > 1 is equivalent to
allowing congestion B in the corresponding disjoint-path problem. Thus another
advantage of the packing approach is that tradeoffs with the allowed congestion
B can be obtained immediately by plugging in B in the packing algorithms that
we use as a black box. For example the approximation for edge-disjoint paths
becomes Ω(max{y ∗ (y ∗ /|E| log |E|)1/B , y ∗ /|E|1/(B+1) , y ∗ /d1/B }), when the num-
ber of connection requests is O(|E|). Our congestion tradeoffs generalize previous
work by Srinivasan [31] who showed the Ω(y ∗ /d1/B ) tradeoff for uniform capac-
ity unsplittable flow. We do not state the tradeoffs explicitly for the various
problems since they can be obtained easily by simple modifications to the given
algorithms.