The Complexity of Bounded Length Graph Recoloring
The Complexity of Bounded Length Graph Recoloring
复制标题
有界长度图重新着色的复杂性
DOI：
10.1002/jgt.22870
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
A. E. Mouawad
中科院分区：
文献类型：
--
作者：
P. Bonsma;A. E. Mouawad
我们研究以下问题：给出了图$G$在$n$顶点上的两个$k$-染色$\α$和$\beta$，以及整数$\ell$。问题是，是否可以通过一次为一个顶点重新着色，同时始终保持$k$-着色，并至多使用$\ell$这样的重新着色步骤，将$\α$修改为$\beta$。这个问题是弱PSPACE的-对每一个常数$k\ge 4$都是困难的。我们证明了对于每一个常数$k，它也是强NP-难的。对于某些可计算函数，我们给出了问题的$O(f(k，ell)n^{O(1)})$算法。因此，当被$k+\ell$参数化时，问题是固定参数可处理的。最后，我们证明了该问题是W[1]-困难的(但在XP中)，当仅由$\ell$参数化时。
We study the following question: Given are two $k$-colorings $\alpha$ and $\beta$ of a graph $G$ on $n$ vertices, and integer $\ell$. The question is whether $\alpha$ can be modified into $\beta$, by recoloring vertices one at a time, while maintaining a $k$-coloring throughout, and using at most $\ell$ such recoloring steps. This problem is weakly PSPACE-hard for every constant $k\ge 4$. We show that it is also strongly NP-hard for every constant $k\ge 4$. On the positive side, we give an $O(f(k,\ell) n^{O(1)})$ algorithm for the problem, for some computable function $f$. Hence the problem is fixed-parameter tractable when parameterized by $k+\ell$. Finally, we show that the problem is W[1]-hard (but in XP) when parameterized only by $\ell$.