IEICE TRANSACTIONS on Fundamentals
The Complexity of (List) Edge-Coloring Reconfiguration Problem
Summary :
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 k ≥ 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 k ≥ 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 k ≤ 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 k ≥ 5, the non-list variant is PSPACE-complete even for planar graphs of bandwidth quadratic in k and maximum degree k.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E101-A No.1 pp.232-238
- Publication Date
- 2018/01/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E101.A.232
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
Hiroki OSAWA
Tohoku University
Akira SUZUKI
Tohoku University
Takehiro ITO
Tohoku University
Xiao ZHOU
Tohoku University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Hiroki OSAWA, Akira SUZUKI, Takehiro ITO, Xiao ZHOU, "The Complexity of (List) Edge-Coloring Reconfiguration Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E101-A, no. 1, pp. 232-238, January 2018, doi: 10.1587/transfun.E101.A.232.
Abstract: 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 k ≥ 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 k ≥ 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 k ≤ 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 k ≥ 5, the non-list variant is PSPACE-complete even for planar graphs of bandwidth quadratic in k and maximum degree k.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E101.A.232/_p
Copy
@ARTICLE{e101-a_1_232,
author={Hiroki OSAWA, Akira SUZUKI, Takehiro ITO, Xiao ZHOU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={The Complexity of (List) Edge-Coloring Reconfiguration Problem},
year={2018},
volume={E101-A},
number={1},
pages={232-238},
abstract={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 k ≥ 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 k ≥ 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 k ≤ 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 k ≥ 5, the non-list variant is PSPACE-complete even for planar graphs of bandwidth quadratic in k and maximum degree k.},
keywords={},
doi={10.1587/transfun.E101.A.232},
ISSN={1745-1337},
month={January},}
Copy
TY - JOUR
TI - The Complexity of (List) Edge-Coloring Reconfiguration Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 232
EP - 238
AU - Hiroki OSAWA
AU - Akira SUZUKI
AU - Takehiro ITO
AU - Xiao ZHOU
PY - 2018
DO - 10.1587/transfun.E101.A.232
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E101-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2018
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 k ≥ 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 k ≥ 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 k ≤ 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 k ≥ 5, the non-list variant is PSPACE-complete even for planar graphs of bandwidth quadratic in k and maximum degree k.
ER -
English
