In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing $W[1]$-hardness proofs for these problems, since XNLP-hardness implies $W[t]$-hardness for all $t$. It also indicates, via a conjecture by Pilipczuk and Wrochna [ToCT 2018], that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, ($q$-)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, and Bipartite Bandwidth.
翻译：在本文中, 我们展示了类 XNLP 是一个用线性宽度测量的很多难题的自然位置。 这加强了这些问题的现有 $[ 1] $- 硬度证明, 因为 XNLP 硬度意味着所有美元都是 $[ t] $- 硬度 。 它还通过 Plipczuk 和 Wrochna [ToCT 2018] 的猜想表明, 这些问题的任何 XP 算法都可能需要 XP 空间。 特别是, 我们展示了 XNLP 的自然问题的完整性, 参数是路径宽度、 线性微宽度和线性 mim- width 。 我们所考虑的问题是独立的设置、 标定的设置、 极性周期 、 ($q$) 组装、 Max Cut、 最大正常生成子图、 反馈 Vertex Set、 固化 (Red- blue) 带宽度定度设置和 双形带宽 。
相关内容
微信扫码咨询专知VIP会员