Accepted author manuscript, 364 KB, PDF document
Available under license: CC BY: Creative Commons Attribution 4.0 International License
Final published version
Licence: CC BY: Creative Commons Attribution 4.0 International License
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - On cut polytopes and graph minors
AU - Kaparis, Konstantinos
AU - Letchford, Adam
AU - Mourtos, Ioannis
PY - 2023/11/30
Y1 - 2023/11/30
N2 - The max-cut problem is a fundamental and much-studied NP-hard combinatorial optimisation problem, with a wide range of applications. Several authors have shown that the max-cut problem can be solved in polynomial time if the underlying graph is free of certain minors. We give a polyhedral counterpart of these results. In particular, we show that, if a family of valid inequalities for the cut polytope satisfies certain conditions, then there is an associated minor-closed family of graphs on which the max-cut problem can be solved efficiently.
AB - The max-cut problem is a fundamental and much-studied NP-hard combinatorial optimisation problem, with a wide range of applications. Several authors have shown that the max-cut problem can be solved in polynomial time if the underlying graph is free of certain minors. We give a polyhedral counterpart of these results. In particular, we show that, if a family of valid inequalities for the cut polytope satisfies certain conditions, then there is an associated minor-closed family of graphs on which the max-cut problem can be solved efficiently.
KW - combinatorial optimisation
KW - graph theory
U2 - 10.1016/j.disopt.2023.100807
DO - 10.1016/j.disopt.2023.100807
M3 - Journal article
VL - 50
JO - Discrete Optimization
JF - Discrete Optimization
SN - 1572-5286
M1 - 100807
ER -