On the structure of minimum cuts of a graph
Federica Cecchetto · 2019
One of the most studied problems in graph theory is the global minimum cut problem: given a connected graph G = (V;E), the goal is to remove a minimum set of edges E' such that G - E' is not connected. From the cuts of a graph G we can derive a polyhedron, called the cut dominant of G. It is an unbounded polyhedron whose points are all those that dominate some convex combination of proper cuts of G. Minimizing a non-negative linear function c >=0 over this polyhedron is the same as fi nding a cut of minimum cost over G. We characterize all graphs whose facet-de fining inequalities for the cut dominant of G have integer coeffi cients and right-hand side at most 2. They are exactly all graphs which have not a prism or a pyramid minor.