TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$
A k-path vertex cover (k-PVC) of a graph G is a vertex subset I such that each path on k vertices in G contains at least one member of I. Imagine that a token is placed on each vertex of a k-PVC. Given two k-PVCs I, J of a graph G, the k-Path Vertex Cover Reconfiguration (k-PVCR) under Token Slidin...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Georgia Southern University
2023-01-01
|
| Series: | Theory and Applications of Graphs |
| Online Access: | https://digitalcommons.georgiasouthern.edu/tag/vol10/iss1/8/ |
| _version_ | 1827954359049125888 |
|---|---|
| author | Duc A. Hoang |
| author_facet | Duc A. Hoang |
| author_sort | Duc A. Hoang |
| collection | DOAJ |
| description | A k-path vertex cover (k-PVC) of a graph G is a vertex subset I such that each path
on k vertices in G contains at least one member of I. Imagine that a token is placed on each vertex of a k-PVC. Given two k-PVCs I, J of a graph G, the k-Path Vertex Cover Reconfiguration (k-PVCR) under Token Sliding (TS) problem asks if there is a sequence of k-PVCs between I and J where each intermediate member is obtained from its predecessor by sliding a token from some vertex to one of its unoccupied neighbors. This problem is known to be PSPACE-complete even for planar graphs of
maximum degree 3 and bounded treewidth and can be solved in polynomial time for paths and cycles. Its complexity for trees remains unknown. In this paper, as a first step toward answering this question, for k ≥ 4, we present a polynomial-time algorithm that solves k-PVCR under TS for caterpillars (i.e., trees formed by attaching leaves to a path).
|
| first_indexed | 2024-04-09T14:29:21Z |
| format | Article |
| id | doaj.art-6e446aade0034d0b869c59cb99fa7b76 |
| institution | Directory Open Access Journal |
| issn | 2470-9859 |
| language | English |
| last_indexed | 2024-04-09T14:29:21Z |
| publishDate | 2023-01-01 |
| publisher | Georgia Southern University |
| record_format | Article |
| series | Theory and Applications of Graphs |
| spelling | doaj.art-6e446aade0034d0b869c59cb99fa7b762023-05-03T17:25:05ZengGeorgia Southern UniversityTheory and Applications of Graphs2470-98592023-01-0110111910.20429/tag.2023.10108TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$Duc A. HoangA k-path vertex cover (k-PVC) of a graph G is a vertex subset I such that each path on k vertices in G contains at least one member of I. Imagine that a token is placed on each vertex of a k-PVC. Given two k-PVCs I, J of a graph G, the k-Path Vertex Cover Reconfiguration (k-PVCR) under Token Sliding (TS) problem asks if there is a sequence of k-PVCs between I and J where each intermediate member is obtained from its predecessor by sliding a token from some vertex to one of its unoccupied neighbors. This problem is known to be PSPACE-complete even for planar graphs of maximum degree 3 and bounded treewidth and can be solved in polynomial time for paths and cycles. Its complexity for trees remains unknown. In this paper, as a first step toward answering this question, for k ≥ 4, we present a polynomial-time algorithm that solves k-PVCR under TS for caterpillars (i.e., trees formed by attaching leaves to a path). https://digitalcommons.georgiasouthern.edu/tag/vol10/iss1/8/ |
| spellingShingle | Duc A. Hoang TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$ Theory and Applications of Graphs |
| title | TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$ |
| title_full | TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$ |
| title_fullStr | TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$ |
| title_full_unstemmed | TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$ |
| title_short | TS-Reconfiguration of $k$-Path Vertex Covers in Caterpillars for $k \geq 4$ |
| title_sort | ts reconfiguration of k path vertex covers in caterpillars for k geq 4 |
| url | https://digitalcommons.georgiasouthern.edu/tag/vol10/iss1/8/ |
| work_keys_str_mv | AT ducahoang tsreconfigurationofkpathvertexcoversincaterpillarsforkgeq4 |