The k-colouring reconfiguration problem asks whether, for a given graph G, two proper k-colourings α and β of G, and a positive integer ℓ, there exists a sequence of at most ℓ proper k-colourings of G which starts with α and ends with β and where successive colourings in the sequence differ on exactly one vertex of G. We give a complete picture of the parameterized complexity of the k-colouring reconfiguration problem for each fixed k when parameterized by ℓ. First we show that the k-colouring reconfiguration problem is polynomial-time solvable for k - 3, settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all ℓ ≥ 4, we show that the k-colouring reconfiguration problem, when parameterized by ℓ, is fixed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.
展开▼
机译：k色重配置问题询问，对于给定的图G，G的两个合适的k色α和β以及一个正整数ℓ是否存在一个序列，其中最多有ℓ个G的合适的k色以α开头。并以β结尾，序列中的连续着色恰好在G的一个顶点上不同。我们给出了由parameter参数化的每个固定k的k着色重配置问题的参数化复杂度的完整图片。首先，我们证明k着色的重配置问题对于k-3是多项式时间可解的，从而解决了Cereceda，van den Heuvel和Johnson的开放问题。然后，对于所有ℓ≥4，我们证明了当用parameter进行参数化时，k色重配置问题是固定参数可处理的（解决了Mouawad，Nishimura，Raman，Simjour和Suzuki的问题），但是它没有多项式核除非多项式层次结构崩溃。
展开▼
