×

zbMATH — the first resource for mathematics

Opposite elements in clutters. (English) Zbl 1439.90018
Summary: Let \(E\) be a finite set of elements, and let \(L\) be a clutter over ground set \(E\). We say distinct elements \(e\), \(f\) are opposite if every member and every minimal cover of \(L\) contains at most one of \(e\), \(f\). In this paper, we investigate opposite elements and reveal a rich theory underlying such a seemingly simple restriction. The clutter \(C\) obtained from \(L\) after identifying some opposite elements is called an identification of \(L\); inversely, \(L\) is called a split of \(C\). We will show that splitting preserves three clutter properties, i.e., idealness, the max-flow min-cut property, and the packing property. We will also display several natural examples in which a clutter does not have these properties but a split of them does. We will develop tools for recognizing when splitting is not a useful operation, and as well, we will characterize when identification preserves the three mentioned properties. We will also make connections to spanning arborescences, Steiner trees, comparability graphs, degenerate projective planes, binary clutters, matroids, as well as the results of Menger, Ford and Fulkerson, the replication conjecture, and a conjecture on ideal, minimally nonpacking clutters.
MSC:
90B10 Deterministic network models in operations research
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdi A, Pashkovich K (2017) Deltas, delta minors and delta free clutters. Submitted.Google Scholar · Zbl 1397.90403
[2] Abdi A, Cornuéjols G, Pashkovich K (2017) Ideal clutters that do not pack. Math. Oper. Res. Forthcoming.Link, Google Scholar
[3] Abdi A, Feldmann AE, Guenin B, Könemann J, Sanità L (2016) Lehman’s theorem and the directed Steiner tree problem. SIAM J. Discrete Math. 30(1):141-153.Crossref, Google Scholar · Zbl 1336.90107
[4] Berge C (1976) Graphs and Hypergraphs (North Holland, Amsterdam).Google Scholar
[5] Bridges WG, Ryser HJ (1969) Combinatorial designs and related systems. J. Algebra 13(3):432-446.Crossref, Google Scholar · Zbl 0185.03206
[6] Chopra S, Rao MR (1994) The Steiner tree problem I: Formulations, compositions and extension of facets. Math. Program. 64(1-3): 209-229.Crossref, Google Scholar · Zbl 0821.90124
[7] Conforti M, Cornuéjols G (1993) Clutters that pack and the max-flow min-cut property: A conjecture. The Fourth Bellairs Workshop on Combinatorial Optimization.Crossref, Google Scholar
[8] Conforti M, Cornuéjols G, Zambelli G (2014) Integer Programming (Springer International, Cham, Switzerland).Crossref, Google Scholar · Zbl 1307.90001
[9] Cornuéjols G (2001) Combinatorial Optimization, Packing and Covering (SIAM, Philadelphia).Crossref, Google Scholar · Zbl 0972.90059
[10] Cornuéjols G, Guenin B, Margot F (2000) The packing property. Math. Program. Ser. A 89(1):113-126.Crossref, Google Scholar · Zbl 1033.90099
[11] Edmonds J (1967) Optimum branchings. J. Res. Nat. Bur. Standards 71B(4):233-240.Crossref, Google Scholar · Zbl 0155.51204
[12] Edmonds J, Fulkerson DR (1970) Bottleneck extrema. J. Combin. Theory Ser. B 8(3):299-306.Crossref, Google Scholar · Zbl 0218.05006
[13] Egerváry E (1931) On combinatorial properties of matrices (in Hungarian). Matematikai és Fizikai Lapok 38:16-28.Google Scholar
[14] Ford LR, Fulkerson DR (1956) Maximal flow through a network. Canadian J. Math. 8(1):399-404.Crossref, Google Scholar · Zbl 0073.40203
[15] Fulkerson DR (1971) Blocking and anti-blocking pairs of polyhedra. Math. Program. 1(1):168-194.Crossref, Google Scholar · Zbl 0254.90054
[16] Goemans MX (1994) Arborescence polytopes for series-parallel graphs. Discrete Appl. Math. 51(3):277-289.Crossref, Google Scholar · Zbl 0802.05040
[17] Isbell JR (1958) A class of simple games. Duke Math. J. 25(3):423-439.Crossref, Google Scholar · Zbl 0083.14301
[18] Kőnig D (1931) Graphs and matrices (in Hungarian). Matematikai és Fizikai Lapok 38:116-119.Google Scholar · JFM 57.1340.04
[19] Lehman A (1964) A solution of the Shannon switching game. Society for Industrial Appl. Math. 12(4):687-725.Crossref, Google Scholar · Zbl 0137.38704
[20] Lehman A (1979) On the width-length inequality. Math. Program. 17(1):403-417.Crossref, Google Scholar · Zbl 0418.90040
[21] Lehman A (1990) The width-length inequality and degenerate projective planes. Cook W, Seymour PD, eds. Polyhedral Combinatorics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 1 (AMS, Providence, RI), 101-105.Google Scholar · Zbl 0747.05063
[22] Lütolf C, Margot F (1998) A catalog of minimally nonideal matrices. Math. Methods of Oper. Res. 47(2):221-241.Crossref, Google Scholar · Zbl 0928.15011
[23] Menger K (1927) Zur allgemeinen Kurventheorie. Fundamenta Mathematicae 10:96-115.Crossref, Google Scholar · JFM 53.0561.01
[24] Nash-Williams CSJA (1961) Edge-disjoint spanning trees of finite graphs. J. London Math. Soc. 36(1):445-450.Crossref, Google Scholar · Zbl 0102.38805
[25] Prodon A, Liebling TM, Gröflin H (1985) Steiner’s problem on 2-trees. Research Report RO 850315, Ecole Polytechnique de Lausanne.Google Scholar
[26] Schaffers M (1991) Network flow design III. Polyhedral characterization of the single source fixed costs problem on series-parallel graphs. CORE Discussion Paper, Université Catholique de Louvain, Louvain.Google Scholar
[27] Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin).Google Scholar
[28] Seymour PD (1976) The forbidden minors of binary matrices. J. London Math. Soc. 2(12):356-360.Crossref, Google Scholar · Zbl 0351.05023
[29] Seymour PD (1977) The matroids with the max-flow min-cut property. J. Combin. Theory Ser. B 23(2-3):189-222.Crossref, Google Scholar · Zbl 0375.05022
[30] Seymour PD (1990) On Lehman’s width-length characterization. Cook W, Seymour PD, eds. Polyhedral Combinatorics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 1 (AMS, Providence, RI), 107-117.Google Scholar · Zbl 0747.05066
[31] Tutte WT (1961) On the problem of decomposing a graph into n connected factors. J. London Math. Soc. 36(1):221-230.Crossref, Google Scholar · Zbl 0096.38001
[32] Vazirani VV (2001) Approximation Algorithms (Springer, Berlin).Google Scholar
[33] Yannakakis M (1991) Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3):441-466.Crossref, · Zbl 0748.90074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.