论文标题
XNLP完整性，用于具有线性结构的图形上的参数化问题
XNLP-completeness for Parameterized Problems on Graphs with a Linear Structure
论文作者
论文摘要
在本文中，我们将XNLP级展示为通过线性宽度测量参数参数的许多硬性问题的自然位置。这加强了现有的$ w [1] $ - 这些问题的硬度证明，因为XNLP硬度意味着$ W [t] $ - 所有$ t $的硬度。它还通过pilipczuk和wrochna的猜想[TOCT 2018]表明，对于此类问题的任何XP算法都可能需要XP空间。 特别是，我们显示了XNLP完整性的自然问题，该自然问题通过路径 - 线性元素宽度和线性模拟宽度参数参数。我们认为的问题是独立的集，主导集，奇数循环横向，（$ q $ - ）着色，最大切割，最大常规诱导子图，反馈顶点集，电容（红蓝）主导集和双部分带宽。
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.
