Back to Search Start Over

Maximum Cut on Interval Graphs of Interval Count Four Is NP-Complete

Authors :
Celina M. H. de Figueiredo and Alexsander A. de Melo and Fabiano S. Oliveira and Ana Silva
de Figueiredo, Celina M. H.
de Melo, Alexsander A.
Oliveira, Fabiano S.
Silva, Ana
Celina M. H. de Figueiredo and Alexsander A. de Melo and Fabiano S. Oliveira and Ana Silva
de Figueiredo, Celina M. H.
de Melo, Alexsander A.
Oliveira, Fabiano S.
Silva, Ana
Publication Year :
2021

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 on 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 not known. 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.

Details

Database :
OAIster
Notes :
application/pdf, English
Publication Type :
Electronic Resource
Accession number :
edsoai.on1358728881
Document Type :
Electronic Resource
Full Text :
https://doi.org/10.4230.LIPIcs.MFCS.2021.38