TY - JOUR

T1 - Reconfiguring k-Path Vertex Covers

AU - Hoang, Duc A.

AU - Suzuki, Akira

AU - Yagita, Tsuyoshi

N1 - Funding Information:
We would like to thank the anonymous reviewers for their insightful and valuable comments that help improving the preliminary versions of this paper. This work is partially supported by JSPS KAKENHI Grant Numbers JP20H05964 (D.A. Hoang), JP18H04091, JP20K11666 and JP20H05794 (A. Suzuki), Japan.
Publisher Copyright:
Copyright © 2022 The Institute of Electronics, Information and Communication Engineers.

PY - 2022

Y1 - 2022

N2 - 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 kpath 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.

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 kpath 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.

KW - combinatorial reconfiguration

KW - computational complexity

KW - k-path vertex cover

KW - polynomial-time algorithms

KW - PSPACE-completeness

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

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

U2 - 10.1587/transinf.2021EDP7177

DO - 10.1587/transinf.2021EDP7177

M3 - Article

AN - SCOPUS:85135208973

SN - 0916-8532

VL - E105D

SP - 1258

EP - 1272

JO - IEICE Transactions on Information and Systems

JF - IEICE Transactions on Information and Systems

IS - 7

ER -