TY - JOUR

T1 - The complexity of (List) edge-coloring reconfiguration problem

AU - Osawa, Hiroki

AU - Suzuki, Akira

AU - Ito, Takehiro

AU - Zhou, Xiao

N1 - Funding Information:
Manuscript received February 14, 2017. Manuscript revised August 10, 2017. †The authors are with the Graduate School of Information Sciences, Tohoku University, Sendai-shi, 980-8579 Japan. ∗This work is partially supported by JST CREST Grant Number JPMJCR1402, Japan, and JSPS KAKENHI Grant Numbers JP26730001, JP17K12636, JP15H00849, JP16K00004 and JP16K00003. a) E-mail: osawa@ecei.tohoku.ac.jp b) E-mail: a.suzuki@ecei.tohoku.ac.jp c) E-mail: takehiro@ecei.tohoku.ac.jp d) E-mail: zhou@ecei.tohoku.ac.jp DOI: 10.1587/transfun.E101.A.232
Publisher Copyright:
© 2018 The Institute of Electronics, Information and Communication Engineers.

PY - 2018/1

Y1 - 2018/1

N2 - Let G be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. Suppose that we are given two list edge-colorings f0 and fr of G, and asked whether there exists a sequence of list edge-colorings of G between f0 and fr such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer κ ≥ 6 and planar graphs of maximum degree three, but any computational hardness was unknown for the non-list variant in which every edge has the same list of k colors. In this paper, we first improve the known result by proving that, for every integer κ ≥ 4, the problem remains PSPACE-complete even for planar graphs of bounded bandwidth and maximum degree three. Since the problem is known to be solvable in polynomial time if κ ≥ 3, our result gives a sharp analysis of the complexity status with respect to the number k of colors. We then give the first computational hardness result for the non-list variant: For every integer κ ≥ 5, the non-list variant is PSPACEcomplete even for planar graphs of bandwidth quadratic in k and maximum degree k.

AB - Let G be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. Suppose that we are given two list edge-colorings f0 and fr of G, and asked whether there exists a sequence of list edge-colorings of G between f0 and fr such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer κ ≥ 6 and planar graphs of maximum degree three, but any computational hardness was unknown for the non-list variant in which every edge has the same list of k colors. In this paper, we first improve the known result by proving that, for every integer κ ≥ 4, the problem remains PSPACE-complete even for planar graphs of bounded bandwidth and maximum degree three. Since the problem is known to be solvable in polynomial time if κ ≥ 3, our result gives a sharp analysis of the complexity status with respect to the number k of colors. We then give the first computational hardness result for the non-list variant: For every integer κ ≥ 5, the non-list variant is PSPACEcomplete even for planar graphs of bandwidth quadratic in k and maximum degree k.

KW - Combinatorial reconfiguration

KW - Edge-coloring

KW - PSPACE-complete

KW - Planar graph

UR - http://www.scopus.com/inward/record.url?scp=85040197362&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85040197362&partnerID=8YFLogxK

U2 - 10.1587/transfun.E101.A.232

DO - 10.1587/transfun.E101.A.232

M3 - Article

AN - SCOPUS:85040197362

SN - 0916-8508

VL - E101A

SP - 232

EP - 238

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 1

ER -