Abstract
A family of sets H is ideal if the polyhedron x ≥ 0: ∑i∈S x i ≥, 1; ∀S ∈ H is integral. Consider a graph G with vertices s, t. An odd st-walk is either: an odd st-path; or the union of an even st-path and an odd circuit which share at most one vertex. Let T be a subset of vertices of even cardinality. An st-T-cut is a cut of the form δ(U) where |U ∩ T| is odd and U contains exactly one of s or t. We give excluded minor characterizations for when the families of odd st-walks and st-T-cuts (represented as sets of edges) are ideal. As a corollary we characterize which extensions and coextensions of graphic and cographic matroids are 1-flowing.
This work supported by the Fields Institute and the University of Waterloo.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
W. G. Bridges and H. J. Ryser. Combinatorial designs and related systems. J. Algebra, 13:432–446, 1969.
G. Cornuéjols and B. Guenin. Ideal binary clutters, connectivity and a conjecture of Seymour. Submitted to SIAM J. on Discrete Mathematics, 1999.
G. Cornuéjols, B. Guenin, and F. Margot. The packing property. Math. Program., Ser. A, 89:113–126, 2000.
J. Edmonds and E. L. Johnson. Matching, euler tours and the chinese postman. Math. Prog., 5:88–124, 1973.
L.R. Ford and D.R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
M.X. Goemans and V.S. Ramakrishnan. Minimizing submodular functions over families of sets. Combinatorica, 15:499–513, 1995.
B. Guenin. A characterization of weakly bipartite graphs. In R. E. Bixby, E. A. Boyd, and R. Z. R∷os-Mercado, editors, Integer Programming and Combinatorial Optimization, volume 1412 of Lecture Notes in Computer Science, pages 9–22. 6th International IPCO Conference, Houston, Texas, Springer, June 1998. Submitted to J. of Comb. Theory Ser. B.
T. C. Hu. Multicommodity network flows. Operations Research, 11:344–360, 1963.
Mei-Ko Kwan. Graphic programming using odd or even points (in chinese). Acta Mathematica Sinica, 10:263–266, 1960.
A. Lehman. A solution of the Shannon switching game. J. SIAM, 12(4):687–725, 1964.
A. Lehman. On the width-length inequality. Mathematical Programming, 17:403–417, 1979.
A. Lehman. On the width-length inequality and degenerate projective planes. In W. Cook and P.D. Seymour, editors, Polyhedral Combinatorics, volume 1 of DIMACS Series in Discrete Math. and Theoretical Computer Science, pages 101–105, 1990.
A. Schrijver. Theory of Linear and Integer Programming. Wiley-Interscience, 1986. ISBN 0-471-90854-1.
P.D. Seymour. The matroids with the max-flow min-cut property. J. Comb. Theory Ser. B, 23:189–222, 1977.
P.D. Seymour. Matroids and multicommodity flows. European J. of Combinatorics, pages 257–290, 1981.
W. T. Tutte. A homotopy theorem for matroids, i,ii. Amer. Math. Soc., 88:144–174, 1958.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Guenin, B. (2001). Integral Polyhedra Related to Even Cycle and Even Cut Matroids. In: Aardal, K., Gerards, B. (eds) Integer Programming and Combinatorial Optimization. IPCO 2001. Lecture Notes in Computer Science, vol 2081. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45535-3_16
Download citation
DOI: https://doi.org/10.1007/3-540-45535-3_16
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42225-9
Online ISBN: 978-3-540-45535-6
eBook Packages: Springer Book Archive