论文标题
在间隔计数的间隔图上最大切割四个是NP完成
Maximum cut on interval graphs of interval count four is NP-complete
论文作者
论文摘要
自80年代以来，限制在间隔图的最大问题的计算复杂性一直是开放的，这是约翰逊在其正在进行的NP完整性指南中提出的问题之一，并且仅在最近由Adhikary，Bose，Bose，Mukherjee和Roy定为NP-Complete。另一方面，在这些年份中介绍了许多限制性的单位/适当间隔图（或具有间隔计数1的图形）的多项式有缺陷的证据，并且问题的分类仍然未知。在本文中，我们介绍了最大值的第一个NP完整性证明，以限制为有界间隔计数的间隔图，即带有间隔计数4的图形。
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.
