×

Vertex adjacencies in the set covering polyhedron. (English) Zbl 1352.05179

Discrete Appl. Math. 218, 40-56 (2017); addendum ibid. 243, 311-315 (2018).
Summary: We describe the adjacency of vertices of the (unbounded version of the) set covering polyhedron, in a similar way to the description given by V. Chvátal [J. Comb. Theory, Ser. B 18, 138–154 (1975; Zbl 0277.05139)] for the stable set polytope. We find a sufficient condition for adjacency, and characterize it with similar conditions in the case where the underlying matrix is row circular. We apply our findings to show a new infinite family of minimally nonideal matrices.

MSC:

05C99 Graph theory
52B20 Lattice polytopes in convex geometry (including relations with commutative algebra and algebraic geometry)

Citations:

Zbl 0277.05139

Software:

cdd; PORTA
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Alfakih, A. Y.; Murty, K. G., Adjacency on the constrained assignment problem, Discrete Appl. Math., 87, 1-3, 269-274 (1998) · Zbl 0910.90233
[2] Bartholdi, J. J.; Orlin, J. B.; Ratliff, H. D., Cyclic scheduling via integer programs with circular ones, Oper. Res., 28, 279-294 (1980) · Zbl 0451.90075
[4] Chung, S. J., Structural Complexity of Adjacency on 0-1 Polytopes (1980), University of Michigan: University of Michigan Ann Arbor, Michigan, (Ph.D. thesis)
[5] Chvátal, V., On certain polytopes associated with graphs, J. Combin. Theory Ser. B, 18, 2, 138-154 (1975) · Zbl 0277.05139
[6] Cornuéjols, G.; Novick, B., Ideal 0,1 matrices, J. Combin. Theory Ser. B, 60, 1, 145-157 (1994) · Zbl 0794.05077
[7] Eisenbrand, F.; Oriolo, G.; Stauffer, G.; Ventura, P., The stable set polytope of quasi-line graphs, Combinatorica, 28, 1, 45-67 (2008) · Zbl 1246.05138
[9] Fukuda, K.; Prodon, A., Double description method revisited, (Deza, M.; Euler, R.; Manoussakis, I., Combinatorics and Computer Science. Combinatorics and Computer Science, Lecture Notes in Computer Science, vol. 1120 (1996), Springer-Verlag), 91-111
[10] Hausmann, D.; Korte, B., Colouring criteria for adjacency on 0-1- polyhedra, Math. Program. Stud., 8, 106-127 (1978) · Zbl 0423.90051
[11] Ikebe, Y. T.; Tamura, A., Ideal polytopes and face structures of some combinatorial optimization problems, Math. Program., 71, 1, 1-15 (1995) · Zbl 0855.90107
[12] Lehman, A., Addendum: “On the width-length inequality”, Math. Program., 17, 3, 403-417 (1979) · Zbl 0418.90040
[13] Lehman, A., On the width-length inequality, Math. Program., 16, 2, 245-259 (1979) · Zbl 0396.94024
[14] Lehman, A., The width-length inequality and degenerate projective planes, (Polyhedral Combinatorics (Morristown, NJ, 1989). Polyhedral Combinatorics (Morristown, NJ, 1989), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 1 (1990), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 101-105 · Zbl 0747.05063
[15] Lütolf, C.; Margot, F., A catalog of minimally nonideal matrices, Math. Methods Oper. Res., 47, 2, 221-241 (1998) · Zbl 0928.15011
[16] Matsui, T., NP-completeness of non-adjacency relations on some 0-1 polytopes, (Proceedings of ISORA’95. Proceedings of ISORA’95, Lecture Notes in Operations Research, vol. 1 (1995)), 249-258
[17] Matsui, T.; Tamura, S., Adjacency in combinatorial polyhedra, Discrete Appl. Math., 56, 2-3, 311-321 (1995) · Zbl 0818.90070
[18] Michini, C., The Stable Set Problem: Some Structural Properties and Relaxations (2012), Università di Roma: Università di Roma Sapienza, (Ph.D. thesis)
[19] Michini, C.; Sassano, A., The Hirsch Conjecture for the fractional stable set polytope, Math. Program., 147, 1-2, 309-330 (2014) · Zbl 1297.90086
[20] Papadimitriou, C. H., The adjacency relation on the traveling salesman polytope is NP-complete, Math. Program., 14, 1, 312-324 (1978) · Zbl 0376.90067
[21] Wang, J., A new infinite family of minimally nonideal matrices, J. Combin. Theory Ser. A, 118, 2, 365-372 (2011) · Zbl 1250.90076
[22] West, D., Introduction to Graph Theory (2001), Prentice Hall
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.