학술논문
Maximum Cut on Interval Graphs of Interval Count Four is NP-Complete
Document Type
Original Paper
Source
Discrete & Computational Geometry. 71(3):893-917
Subject
Language
English
ISSN
0179-5376
1432-0444
1432-0444
Abstract
The computational complexity of the MaxCut problem restricted to interval graphs has been open since the 80’s, being one of the problems proposed by Johnson in his Ongoing Guide to NP-completeness, and has been settled as NP-complete only recently by Adhikary, Bose, Mukherjee, and Roy. On the other hand, many flawed proofs of polynomiality for MaxCut on the more restrictive class of unit/proper interval graphs (or graphs with interval count 1) have been presented along the years, and the classification of the problem is still unknown. In this paper, we present the first NP-completeness proof for MaxCut when restricted to interval graphs with bounded interval count, namely graphs with interval count 4.