论文标题
$ b $ - 颜色由路径放宽参数为xnlp complete
$b$-Coloring Parameterized by Pathwidth is XNLP-complete
论文作者
论文摘要
我们表明，当通过输入图的路径宽参数化时，XNLP类$ b $颜色的问题已完成。除了确定此问题的精确参数化复杂性外，这还意味着B-coloring由路径放宽参数为$ W [t] $ - 对于所有$ t $而言，很难解决$ b $的参数化复杂性，由treewidth参数化。
We show that the $b$-Coloring problem is complete for the class XNLP when parameterized by the pathwidth of the input graph. Besides determining the precise parameterized complexity of this problem, this implies that b-Coloring parameterized by pathwidth is $W[t]$-hard for all $t$, and resolves the parameterized complexity of $b$-Coloring parameterized by treewidth.
