Cut Polytopes of Minor-free Graphs

03/05/2019
by   Markus Chimani, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset