Reconfiguring k-path vertex covers
Reconfiguring k-path vertex covers
复制标题
DOI：
10.1007/978-3-030-39881-1_12
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Duc A. Hoang;Akira Suzuki;Tsuyoshi Yagita
中科院分区：
文献类型：
--
作者：
Duc A. Hoang;Akira Suzuki;Tsuyoshi Yagita
如果图G的每条路都包含至少一个顶点Fromi，则图G的一个顶点子集称为Ak-路顶点覆盖。K路顶点覆盖重构问题(k-PVCR)是指能否通过K路顶点覆盖序列将一条路径的顶点覆盖转换为另一条路径的顶点覆盖，其中每个中间成员只需应用一次给定的重构规则即可从其前辈那里获得。我们从图类的角度研究了K-PVCR在著名的重构规则：、和下的计算复杂性。的问题，称为顶点覆盖重新配置(VCR)问题，已经在文献中得到了很好的研究。我们证明了VCR在平面图、有界带宽图、弦图和二部图等不同图类上的某些已知硬度结果可以推广到Fork-PVCR。特别地，我们在一般图上证明了一个复杂性分叉-PVCR：在最大度为3(甚至是平面图)的图上，问题是-完全的，而在最大度为2的图(即路和圈)上，问题可以在多项式时间内求解。此外，我们还设计了多项式时间算法Fork-PVCRon树。此外，在路、圈和树上，我们描述了如何在一个yes实例中构造两个给定k路顶点覆盖之间的重构序列。特别是，在路径上，我们构造的重构序列是最短的。
A vertex subsetIof a graphGis called ak-path vertex cover if every path onkvertices inGcontains at least one vertex fromI. Thek-Path Vertex Cover Reconfiguration (k-PVCR)problem asks if one can transform onek-path vertex cover into another via a sequence ofk-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 ofk-PVCRfrom the viewpoint of graph classes under the well-known reconfiguration rules:,, and. The problem for, known as theVertex Cover Reconfiguration (VCR)problem, has been well-studied in the literature. We show that certain known hardness results forVCRon different graph classes including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, can be extended fork-PVCR. In particular, we prove a complexity dichotomy fork-PVCRon general graphs: on those whose maximum degree is 3 (and even planar), the problem is-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 fork-PVCRon trees under each ofand. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two givenk-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.