Title: Steiner Cut Dominants
| Speaker: | Volker Kaibel |
| Affiliation: | Otto von Guericke University Magdeburg |
| Location: | MC 5501 or contact Eva Lee for Zoom link |
Abstract: For a subset of terminals T of the nodes of a graph G a cut in G is called a T-Steiner cut if it subdivides T into two non-empty sets. The Steiner cut dominant of G is the Minkowski sum of the convex hull of the incidence vectors of T-Steiner cuts in G and the nonnegative orthant. It is the polyhedron that is naturally associated with the problem of finding a minimum T-Steiner cut in G w.r.t. nonnegative edge weights. While it is well understood for two terminals (s-t-cuts), for larger sets T no inequality descriptions have been known so far despite quite some efforts that have been spent into investigating this problem for T being the complete node set of G (global cuts). In this talk we derive such descriptions for all graphs and up to five terminals. Moreover, we prove that for each number k there is a finite list of inequalities from which one can derive by means of iterated applications of two simple operations inequality descriptions of the Steiner cut dominant for every graph and up to k terminals. We furthermore introduce the concept of the Steiner rank of a facet of a global cut dominant and classify the facets of Steiner rank at most five.
The talk is based on joint work with Michele Conforti.