2020/12/17 by Celina M.H. de Figueiredo, Alexsander A. de Melo, de Figueiredo, Celina M. H. +5 · 1 citation
Computer Science · #05C62 #68Q17 #68Q25 #68R10 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #Graph Labeling and Dimension Problems
paper · doi:10.48550/arxiv.2012.09804
openalex publication_date 2020/12/17 · openalex created_date 2022/07/19 · openalex updated_date 2026/07/28
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 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.