zbMATH — the first resource for mathematics

On the diameter of cut polytopes. (English) Zbl 1338.52003
Summary: Given an undirected graph \(G\) with node set \(V\) and edge set \(E\), the cut polytope \(C U T(G)\) is defined as the convex hull of the incidence vectors of the cuts in \(G\). For a given integer \(k \in \{1, 2, \ldots, \lfloor \frac{| V |}{2} \rfloor \}\), the uniform cut polytope \(C U T_{= k}(G)\) is defined as the convex hull of the incidence vectors of the cuts which correspond to a bipartition of the node set into sets with cardinalities \(k\) and \(| V | - k\).
In this paper, we study the diameter of these two families of polytopes. For a connected graph \(G\), we prove that the diameter of \(C U T(G)\) is at most \(| V | - 1\), improving on the bound of \(| E |\) given by F. Barahona and A. R. Mahjoub [Math. Program. 36, 157–173 (1986; Zbl 0616.90058)]. We also give its exact value for trees and complete bipartite graphs. Then, with respect to uniform cut polytopes, we introduce sufficient conditions for adjacency of two vertices in \(C U T_{= k}(G)\), we study some particular cases and provide some connections with other partition polytopes from the literature.

52A10 Convex sets in \(2\) dimensions (including convex curves)
90C27 Combinatorial optimization
05C35 Extremal problems in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
90C35 Programming involving graphs or networks
Full Text: DOI
[1] Barahona, F., On the computational complexity of Ising spin Glass models, J. Phys. A: Math. Gen., 15, 3241-3253, (1982)
[2] Barahona, F.; Mahjoub, A. R., On the cut polytope, Math. Program., 36, 2, 157-173, (1986) · Zbl 0616.90058
[3] Borgwardt, S., On the diameter of partition polytopes and vertex-disjoint cycle cover, Math. Program., 141, 1-20, (2013) · Zbl 1288.90049
[4] De Loera, J. A.; Kim, E. D., Combinatorics and geometry on transportation polytopes: an update, Comtemporary Math., 625, 37-76, (2014) · Zbl 1360.90169
[5] De Simone, C.; Diehl, M.; Jünger, M.; Mutzel, P.; Reinelt, G.; Rinaldi, G., Exact ground states of Ising spin glasses: new experimental results with a branch and cut algorithm, J. Stat. Phys., 80, 487-496, (1995) · Zbl 1106.82323
[6] Deza, M. M.; Laurent, M., Geometry of cuts and metrics, algorithms and combinatorics, vol. 15, (1997), Springer Berlin
[7] Grötschel, M.; Jünger, M.; Reinelt, G., Via minimization with pin preassignment and layer preference, Z. Angew. Math. Mech., 69, 393-399, (1989) · Zbl 0713.05036
[8] Grünbaum, B., Convex polytopes, (2003), Springer New York
[9] Klee, V.; Witzgall, C., Facets and vertices of transportation polytopes, (Dantzig, G. B.; Veinott, A. F., Mathematics of the Decision Sciences, vol. 1, (1968)), 257-282
[10] Matsui, T.; Tamura, S., Adjacency on combinatorial polyhedra, Discrete Appl. Math., 56, 311-321, (1995) · Zbl 0818.90070
[11] Naddef, D., The Hirsch conjecture is true for (0, 1)-polytopes, Math. Program., 45, 109-110, (1989) · Zbl 0684.90071
[12] Naddef, D.; Pulleyblank, W. R., Hamiltonicity and combinatorial polyhedra, J. Combin. Theory Ser. B, 31, 297-312, (1981) · Zbl 0449.05042
[13] Neto, J., From equipartition to uniform cut polytopes: extended polyhedral results, Discrete Math., 311, 705-714, (2011) · Zbl 1222.05215
[14] Neto, J., On the polyhedral structure of uniform cut polytopes, Discrete Appl. Math., 175, 62-70, (2014) · Zbl 1298.05267
[15] Schrijver, A., Combinatorial optimization: polyhedra and efficiency, (Algorithms and Combinatorics, vol. 24, (2003), Springer-Verlag) · Zbl 1041.90001
[16] Ziegler, G., (Lectures on Polytopes, Series: Graduate Texts in Mathematics, vol. 152, (1995), Springer) · Zbl 0823.52002
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.