论文标题
在间隔计数的间隔图上最大切割二是NP完成
Maximum Cut on Interval Graphs of Interval Count Two is NP-complete
论文作者
论文摘要
间隔图具有间隔计数$ \ ell $，如果它具有间隔模型，则每个$ \ ell+1 $间隔中有两个具有相同长度的时间。 Adhikary等人最近发现，在间隔图上的最大切割是NP完整的。在确定其在单位间隔图上的复杂性（Interval Count One）仍然是一个长期存在的开放问题。最近，De Figueiredo等人。通过证明该问题在间隔计数四的间隔图上仍然是NP完整的，从而取得了进步。在本文中，我们表明，即使在第二间隔计数的间隔图上，最大切割也是NP完整的。
An interval graph has interval count $\ell$ if it has an interval model, where among every $\ell+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.
