Steiner Cut Dominants

For a subset T of nodes of an undirected graph G , a T-Steiner cut is a cut δ ( S ) with T ∩ S ≠ ø and T \ S ≠ ø . The T-Steiner cut dominant of G is the dominant 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 | ≤ τ , the nontrivial facet-defining inequalities of 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 CUT + ( G , T ) by integral inequalities can be bounded from above by a function of | T | . For all | T | ≤ 5 , we provide descriptions of CUT + ( G , T ) by facet-defining inequalities, extending the known descriptions of s - t -cut dominants.