Steiner Cut Dominants

• 成果类型: Article
• 署名作者: Conforti, Michele; Kaibel, Volker
• 署名单位: University of Padua; Otto von Guericke University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.0280
• 发表日期: 2025
• 关键词: traveling salesman problem

摘要

For a subset T of nodes of an undirected graph G, a T-Steiner cut is a cut delta(S) with T boolean AND S not equal & oslash; and T\S not equal & oslash;. 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 tau, there is a finite set of inequalities such that for every pair (G, T) with |T|<=tau|, 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.