Steiner Cut Dominants
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914709726298112 |
|---|---|
| author | Conforti, Michele Kaibel, Volker |
| author_facet | Conforti, Michele Kaibel, Volker |
| contents | For a subset T of nodes of an undirected graph G, a T-Steiner cut is a cut δ(S) where S intersects both T and the complement of T. 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 \emph{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 non-trivial 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_14802 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Steiner Cut Dominants Conforti, Michele Kaibel, Volker Combinatorics Optimization and Control 90C57, 90C27, 65K05 For a subset T of nodes of an undirected graph G, a T-Steiner cut is a cut δ(S) where S intersects both T and the complement of T. 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 \emph{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 non-trivial 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. |
| title | Steiner Cut Dominants |
| topic | Combinatorics Optimization and Control 90C57, 90C27, 65K05 |
| url | https://arxiv.org/abs/2209.14802 |