Cut Polytopes of Minor-free Graphs
share
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.
READ FULL TEXT
