Reconfiguring k-Path Vertex Covers

Duc A. Hoang, Akira Suzuki, Tsuyoshi Yagita

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Pages (from-to)1258-1272
Number of pages15
JournalIEICE Transactions on Information and Systems
Issue number7
Publication statusPublished - 2022


  • combinatorial reconfiguration
  • computational complexity
  • k-path vertex cover
  • polynomial-time algorithms
  • PSPACE-completeness


Dive into the research topics of 'Reconfiguring k-Path Vertex Covers'. Together they form a unique fingerprint.

Cite this