IEICE TRANSACTIONS on Information
Reconfiguring k-Path Vertex Covers
Summary :
A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The K-PATH VERTEX COVER RECONFIGURATION (K-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of k-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of K-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k=2, known as the VERTEX COVER RECONFIGURATION (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes can be extended for K-PVCR. In particular, we prove a complexity dichotomy for K-PVCR on general graphs: on those whose maximum degree is three (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is two (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for K-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.
- Publication
- IEICE TRANSACTIONS on Information Vol.E105-D No.7 pp.1258-1272
- Publication Date
- 2022/07/01
- Publicized
- 2022/04/12
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2021EDP7177
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Duc A. HOANG
Kyoto University
Akira SUZUKI
Tohoku University
Tsuyoshi YAGITA
Kyushu Institute of Technology
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
Duc A. HOANG, Akira SUZUKI, Tsuyoshi YAGITA, "Reconfiguring k-Path Vertex Covers" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 7, pp. 1258-1272, July 2022, doi: 10.1587/transinf.2021EDP7177.
Abstract: A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The K-PATH VERTEX COVER RECONFIGURATION (K-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of k-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of K-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k=2, known as the VERTEX COVER RECONFIGURATION (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes can be extended for K-PVCR. In particular, we prove a complexity dichotomy for K-PVCR on general graphs: on those whose maximum degree is three (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is two (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for K-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021EDP7177/_p
Copy
@ARTICLE{e105-d_7_1258,
author={Duc A. HOANG, Akira SUZUKI, Tsuyoshi YAGITA, },
journal={IEICE TRANSACTIONS on Information},
title={Reconfiguring k-Path Vertex Covers},
year={2022},
volume={E105-D},
number={7},
pages={1258-1272},
abstract={A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The K-PATH VERTEX COVER RECONFIGURATION (K-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of k-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of K-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k=2, known as the VERTEX COVER RECONFIGURATION (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes can be extended for K-PVCR. In particular, we prove a complexity dichotomy for K-PVCR on general graphs: on those whose maximum degree is three (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is two (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for K-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.},
keywords={},
doi={10.1587/transinf.2021EDP7177},
ISSN={1745-1361},
month={July},}
Copy
TY - JOUR
TI - Reconfiguring k-Path Vertex Covers
T2 - IEICE TRANSACTIONS on Information
SP - 1258
EP - 1272
AU - Duc A. HOANG
AU - Akira SUZUKI
AU - Tsuyoshi YAGITA
PY - 2022
DO - 10.1587/transinf.2021EDP7177
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2022
AB - A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The K-PATH VERTEX COVER RECONFIGURATION (K-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of k-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of K-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k=2, known as the VERTEX COVER RECONFIGURATION (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes can be extended for K-PVCR. In particular, we prove a complexity dichotomy for K-PVCR on general graphs: on those whose maximum degree is three (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is two (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for K-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.
ER -
English
