Steiner Cut Dominants

For a subset T of nodes of an undirected graph G, a T-Steiner cut is a cut $\delta (S)$ with $T\cap S\ne ø$ and $T\backslash S\ne ø$. The T-Steiner cut dominant of G is the dominant ${\text{CUT}}_{+}(G,T)$ of the convex hull of the incidence vectors of the T-Steiner cuts of G. For $T=\{s,t\}$, this is the well-understood s-t-cut dominant. Choosing T as the set of all nodes of G, we obtain the cut dominant for which an outer description in the space of the original variables is still not known. We prove that for each integer τ, there is a finite set of inequalities such that for every pair (G, T) with $|T|\le \tau$, the nontrivial facet-defining inequalities of ${\text{CUT}}_{+}(G,T)$ are the inequalities that can be obtained via iterated applications of two simple operations, starting from that set. In particular, the absolute values of the coefficients and of the right-hand sides in a description of ${\text{CUT}}_{+}(G,T)$ by integral inequalities can be bounded from above by a function of $|T|$. For all $|T|\le 5$, we provide descriptions of ${\text{CUT}}_{+}(G,T)$ by facet-defining inequalities, extending the known descriptions of s-t-cut dominants.