# 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.

##### MSC:
 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
##### Keywords:
(uniform) cut polytope; diameter; graph partitioning
Full Text:
##### References:
  Barahona, F., On the computational complexity of Ising spin Glass models, J. Phys. A: Math. Gen., 15, 3241-3253, (1982)  Barahona, F.; Mahjoub, A. R., On the cut polytope, Math. Program., 36, 2, 157-173, (1986) · Zbl 0616.90058  Borgwardt, S., On the diameter of partition polytopes and vertex-disjoint cycle cover, Math. Program., 141, 1-20, (2013) · Zbl 1288.90049  De Loera, J. A.; Kim, E. D., Combinatorics and geometry on transportation polytopes: an update, Comtemporary Math., 625, 37-76, (2014) · Zbl 1360.90169  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  Deza, M. M.; Laurent, M., Geometry of cuts and metrics, algorithms and combinatorics, vol. 15, (1997), Springer Berlin  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  Grünbaum, B., Convex polytopes, (2003), Springer New York  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  Matsui, T.; Tamura, S., Adjacency on combinatorial polyhedra, Discrete Appl. Math., 56, 311-321, (1995) · Zbl 0818.90070  Naddef, D., The Hirsch conjecture is true for (0, 1)-polytopes, Math. Program., 45, 109-110, (1989) · Zbl 0684.90071  Naddef, D.; Pulleyblank, W. R., Hamiltonicity and combinatorial polyhedra, J. Combin. Theory Ser. B, 31, 297-312, (1981) · Zbl 0449.05042  Neto, J., From equipartition to uniform cut polytopes: extended polyhedral results, Discrete Math., 311, 705-714, (2011) · Zbl 1222.05215  Neto, J., On the polyhedral structure of uniform cut polytopes, Discrete Appl. Math., 175, 62-70, (2014) · Zbl 1298.05267  Schrijver, A., Combinatorial optimization: polyhedra and efficiency, (Algorithms and Combinatorics, vol. 24, (2003), Springer-Verlag) · Zbl 1041.90001  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.