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.
翻译：我们显示,当用输入图的路径线参数参数来参数化 XNLP 类的 $b$ 的组装问题已经完全解决。 除了确定这一问题的精确参数化复杂性外,这意味着路径线的b- 组装参数对于所有$t来说都是 $W[t]$-硬的,并且解决了用树枝参数化的 $b$- 组装参数化的参数化复杂度。
相关内容
Arxiv
0+阅读 · 2022年10月24日
Arxiv
0+阅读 · 2022年10月21日
Arxiv
0+阅读 · 2022年10月21日
相关VIP内容
相关资讯
微信扫码咨询专知VIP会员