Steiner Cut Dominants

Michele Conforti () and Volker Kaibel ()
Additional contact information
Michele Conforti: Dipartimento Matematica, Università degli Studi di Padova, 35121 Padova, Italy
Volker Kaibel: Fakultät für Mathematik, Otto-von-Guericke Universität Magdeburg, 39106 Magdeburg, Germany

Mathematics of Operations Research, 2025, vol. 50, issue 1, 764-781

Abstract: 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.

Keywords: Primary: 90C57; secondary: 90C27; 65K05; cut polyhedron; Steiner nodes; inequality description; facets; Steiner cut problem (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0280 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:50:y:2025:i:1:p:764-781

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().