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.
翻译：自80年代以来,MaxCut问题的计算复杂性一直限于间距图,这是Johnson在其当前NP完整性指南中提出的问题之一,直到最近Adhikary、Bose、Mukherjee和Roy才作为NP完整性得到解决。另一方面,多年来,MaxCut在更限制性的单位/丙型间距图(或间距计1的图)上,对单位/丙型间距图(或间距计1的图)提出了许多有缺陷的多元性证据,这个问题的分类仍然未知。本文为MaxCut提供了第一次NP完整性证据,但仅限于有间距的间隔计数的间距图,即有间距计4的图。
相关内容
微信扫码咨询专知VIP会员