2022/03/13 by Barsukov, Alexey, Roy, Bodhayan · 1 citation
#35A01 #65L10 #65L12 #65L20 #65L70 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2203.06630
An interval graph has interval count ℓ if it has an interval model, where among every ℓ+1 intervals there are two that have the same length. Maximum Cut on interval graphs has been found to be NP-complete recently by Adhikary et al. while deciding its complexity on unit interval graphs (graphs with interval count one) remains a longstanding open problem. More recently, de Figueiredo et al. have made an advancement by showing that the problem remains NP-complete on interval graphs of interval count four. In this paper, we show that Maximum Cut is NP-complete even on interval graphs of interval count two.