Home > Research > Publications & Outputs > On cut polytopes and graph minors

Associated organisational unit

Electronic data

  • max-cut-minors

    Accepted author manuscript, 364 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

View graph of relations

On cut polytopes and graph minors

Research output: Contribution to Journal/MagazineJournal articlepeer-review

Published
Close
Article number100807
<mark>Journal publication date</mark>30/11/2023
<mark>Journal</mark>Discrete Optimization
Volume50
Publication StatusPublished
Early online date10/10/23
<mark>Original language</mark>English

Abstract

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.