Steiner Cut Dominants
研究了无向图中T-斯坦纳割的占优多面体，证明了其非平凡面定义不等式可通过有限初始集经两次简单操作迭代生成，并给出了小|T|时的显式描述。
For a subset T of nodes of an undirected graph G, a T-Steiner cut is a cut [Formula: see text] with [Formula: see text] and [Formula: see text]. The T-Steiner cut dominant of G is the dominant [Formula: see text] of the convex hull of the incidence vectors of the T-Steiner cuts of G. For [Formula: see text], 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 [Formula: see text], the nontrivial facet-defining inequalities of [Formula: see text] 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 [Formula: see text] by integral inequalities can be bounded from above by a function of [Formula: see text]. For all [Formula: see text], we provide descriptions of [Formula: see text] by facet-defining inequalities, extending the known descriptions of s-t-cut dominants.