Complexity of Maximum Cut on Interval Graphs

2020/05/29 by Ranendu Adhikary, Adhikary, Ranendu, Kaustav Bose +5 · 1 citation
Computer Science · #Formal Methods in Verification #Complexity and Algorithms in Graphs #Logic, Reasoning, and Knowledge

paper · doi:10.48550/arxiv.2006.00061

Abstract

We resolve the longstanding open problem concerning the computational complexity of Max Cut on interval graphs by showing that it is NP-complete.

Cited by

• Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson

Related

• Maximum cut on interval graphs of interval count four is NP-complete
• Maximum Cut on Interval Graphs of Interval Count Two is NP-complete
• The Maximum Cardinality Cut Problem is Polynomial in Proper Interval Graphs
• Approximating Maximum Cut on Interval Graphs and Split Graphs beyond Goemans-Williamson
• Max-Cut Parameterized Above the Edwards-Erdős Bound