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

Research

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:

Keywords

View graph of relations

On cut polytopes and graph minors

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

On cut polytopes and graph minors. / Kaparis, Konstantinos; Letchford, Adam; Mourtos, Ioannis.
In: Discrete Optimization, Vol. 50, 100807, 30.11.2023.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Kaparis, K, Letchford, A & Mourtos, I 2023, 'On cut polytopes and graph minors', Discrete Optimization, vol. 50, 100807. https://doi.org/10.1016/j.disopt.2023.100807

APA

Kaparis, K., Letchford, A., & Mourtos, I. (2023). On cut polytopes and graph minors. Discrete Optimization, 50, Article 100807. https://doi.org/10.1016/j.disopt.2023.100807

Vancouver

Kaparis K, Letchford A, Mourtos I. On cut polytopes and graph minors. Discrete Optimization. 2023 Nov 30;50:100807. Epub 2023 Oct 10. doi: 10.1016/j.disopt.2023.100807

Author

Kaparis, Konstantinos ; Letchford, Adam ; Mourtos, Ioannis. / On cut polytopes and graph minors. In: Discrete Optimization. 2023 ; Vol. 50.

Bibtex

@article{8e9736549a94409b81977081d238e511,
title = "On cut polytopes and graph minors",
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.",
keywords = "combinatorial optimisation, graph theory",
author = "Konstantinos Kaparis and Adam Letchford and Ioannis Mourtos",
year = "2023",
month = nov,
day = "30",
doi = "10.1016/j.disopt.2023.100807",
language = "English",
volume = "50",
journal = "Discrete Optimization",
issn = "1572-5286",
publisher = "Elsevier",

}

RIS

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 -