Reconfiguration of Vertex Covers in a Graph

Takehiro ITO; Hiroyuki NOOKA; Xiao ZHOU

doi:10.1587/transinf.2015FCP0010

IEICE TRANSACTIONS on Information

Reconfiguration of Vertex Covers in a Graph

Takehiro ITO, Hiroyuki NOOKA, Xiao ZHOU

Full Text Views

0

Cite this

Summary :

Suppose that we are given two vertex covers C₀ and C_t of a graph G, together with an integer threshold k ≥ max{|C₀|, |C_t|}. Then, the vertex cover reconfiguration problem is to determine whether there exists a sequence of vertex covers of G which transforms C₀ into C_t such that each vertex cover in the sequence is of cardinality at most k and is obtained from the previous one by either adding or deleting exactly one vertex. This problem is PSPACE-complete even for planar graphs. In this paper, we first give a linear-time algorithm to solve the problem for even-hole-free graphs, which include several well-known graphs, such as trees, interval graphs and chordal graphs. We then give an upper bound on k for which any pair of vertex covers in a graph G has a desired sequence. Our upper bound is best possible in some sense.

Publication: IEICE TRANSACTIONS on Information Vol.E99-D No.3 pp.598-606

Publication Date: 2016/03/01

Publicized: 2015/12/16

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2015FCP0010

Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science---Developments of the Theory of Algorithms and Computation---)

Category

Authors

Takehiro ITO
  Tohoku University
Hiroyuki NOOKA
  Tohoku University
Xiao ZHOU
  Tohoku University

Keyword

combinatorial reconfiguration, even-hole-free graph, graph algorithm, vertex cover

Cite this

Copy

Takehiro ITO, Hiroyuki NOOKA, Xiao ZHOU, "Reconfiguration of Vertex Covers in a Graph" in IEICE TRANSACTIONS on Information, vol. E99-D, no. 3, pp. 598-606, March 2016, doi: 10.1587/transinf.2015FCP0010.
Abstract: Suppose that we are given two vertex covers C₀ and C_t of a graph G, together with an integer threshold k ≥ max{|C₀|, |C_t|}. Then, the vertex cover reconfiguration problem is to determine whether there exists a sequence of vertex covers of G which transforms C₀ into C_t such that each vertex cover in the sequence is of cardinality at most k and is obtained from the previous one by either adding or deleting exactly one vertex. This problem is PSPACE-complete even for planar graphs. In this paper, we first give a linear-time algorithm to solve the problem for even-hole-free graphs, which include several well-known graphs, such as trees, interval graphs and chordal graphs. We then give an upper bound on k for which any pair of vertex covers in a graph G has a desired sequence. Our upper bound is best possible in some sense.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2015FCP0010/_p

Copy

@ARTICLE{e99-d_3_598,
author={Takehiro ITO, Hiroyuki NOOKA, Xiao ZHOU, },
journal={IEICE TRANSACTIONS on Information},
title={Reconfiguration of Vertex Covers in a Graph},
year={2016},
volume={E99-D},
number={3},
pages={598-606},
abstract={Suppose that we are given two vertex covers C₀ and C_t of a graph G, together with an integer threshold k ≥ max{|C₀|, |C_t|}. Then, the vertex cover reconfiguration problem is to determine whether there exists a sequence of vertex covers of G which transforms C₀ into C_t such that each vertex cover in the sequence is of cardinality at most k and is obtained from the previous one by either adding or deleting exactly one vertex. This problem is PSPACE-complete even for planar graphs. In this paper, we first give a linear-time algorithm to solve the problem for even-hole-free graphs, which include several well-known graphs, such as trees, interval graphs and chordal graphs. We then give an upper bound on k for which any pair of vertex covers in a graph G has a desired sequence. Our upper bound is best possible in some sense.},
keywords={},
doi={10.1587/transinf.2015FCP0010},
ISSN={1745-1361},
month={March},}

Copy

TY - JOUR
TI - Reconfiguration of Vertex Covers in a Graph
T2 - IEICE TRANSACTIONS on Information
SP - 598
EP - 606
AU - Takehiro ITO
AU - Hiroyuki NOOKA
AU - Xiao ZHOU
PY - 2016
DO - 10.1587/transinf.2015FCP0010
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E99-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2016
AB - Suppose that we are given two vertex covers C₀ and C_t of a graph G, together with an integer threshold k ≥ max{|C₀|, |C_t|}. Then, the vertex cover reconfiguration problem is to determine whether there exists a sequence of vertex covers of G which transforms C₀ into C_t such that each vertex cover in the sequence is of cardinality at most k and is obtained from the previous one by either adding or deleting exactly one vertex. This problem is PSPACE-complete even for planar graphs. In this paper, we first give a linear-time algorithm to solve the problem for even-hole-free graphs, which include several well-known graphs, such as trees, interval graphs and chordal graphs. We then give an upper bound on k for which any pair of vertex covers in a graph G has a desired sequence. Our upper bound is best possible in some sense.
ER -

IEICE TRANSACTIONS on Information