Cut Polytopes of Minor-free Graphs

2019/03/05 by Chimani, Markus, Juhnke-Kubitzke, Martina, Nover, Alexander +1
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1903.01817

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.

Related

• Cut dominants and forbidden minors
• Polynomial-time Approximation Scheme for Minimum k-cut in Planar and Minor-free Graphs
• On the Bond Polytope
• Generalized cut and metric polytopes of graphs and simplicial complexes
• On the Dominant of the Multicut Polytope