TY - GEN

T1 - Reconfiguring k-path vertex covers

AU - Hoang, Duc A.

AU - Suzuki, Akira

AU - Yagita, Tsuyoshi

N1 - Funding Information:
This work is partially supported by JSPS KAKENHI Grant Numbers JP17K12636, JP18H04091, and JP19K24349, and JST CREST Grant Number JPMJCR1402.
Funding Information:
This work is partially supported by JSPSKAKENHI Grant Numbers JP17K12636, JP18H04091, and JP19K24349, and JSTCREST Grant Number JPMJCR1402.
Publisher Copyright:
© Springer Nature Switzerland AG 2020.

PY - 2020

Y1 - 2020

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 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 including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, 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 3 (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is 2 (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 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 including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, 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 3 (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is 2 (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 - PSPACE-completeness

KW - Polynomial-time algorithms

KW - k-path vertex cover

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

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

U2 - 10.1007/978-3-030-39881-1_12

DO - 10.1007/978-3-030-39881-1_12

M3 - Conference contribution

AN - SCOPUS:85080945909

SN - 9783030398804

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 133

EP - 145

BT - WALCOM

A2 - Rahman, M. Sohel

A2 - Sadakane, Kunihiko

A2 - Sung, Wing-Kin

PB - Springer

T2 - 14th International Conference and Workshops on Algorithms and Computation, WALCOM 2020

Y2 - 31 March 2020 through 2 April 2020

ER -