Markus Chimani, Martina Juhnke-Kubitzke, Alexander Nover, Tim Römer: Cut polytopes of minor-free graphs, 97-112

Abstract:

The cut polytope of a graph $G$ is the convex hull of the indicator vectors of all cuts in $G$ and is closely related to the MAXCUT problem. We give the facet-description of cut polytopes of $K_{3,3}$-minor-free graphs and introduce an algorithm solving MAXCUT on those graphs, which only requires the running time of planar MAXCUT. Moreover, starting a systematic geometric study of cut polytopes, we classify graphs admitting a simple or simplicial cut polytope.

Key Words: Maximum cut, cut polytope, polyhedral study, facets, lattice polytope, combinatorial optimization, graph.

2010 Mathematics Subject Classification: Primary 52B12; Secondary 05C83.

Download the paper in pdf format here.