TY - JOUR

T1 - Reconfiguration of vertex covers in a graph

AU - Ito, Takehiro

AU - Nooka, Hiroyuki

AU - Zhou, Xiao

N1 - Publisher Copyright:
Copyright © 2016 The Institute of Electronics, Information and Communication Engineers.

PY - 2016/3

Y1 - 2016/3

N2 - Suppose that we are given two vertex covers C0 and Ct of a graph G, together with an integer threshold k ≥ max{|C0|, |Ct|}. Then, the VERTEX COVER RECONFIGURATION problem is to determine whether there exists a sequence of vertex covers of G which transforms C0 into Ct 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.

AB - Suppose that we are given two vertex covers C0 and Ct of a graph G, together with an integer threshold k ≥ max{|C0|, |Ct|}. Then, the VERTEX COVER RECONFIGURATION problem is to determine whether there exists a sequence of vertex covers of G which transforms C0 into Ct 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.

KW - Combinatorial reconfiguration

KW - Even-hole-free graph

KW - Graph algorithm

KW - Vertex cover

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

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

U2 - 10.1587/transinf.2015FCP0010

DO - 10.1587/transinf.2015FCP0010

M3 - Article

AN - SCOPUS:84959557895

SN - 0916-8532

VL - E99D

SP - 598

EP - 606

JO - IEICE Transactions on Information and Systems

JF - IEICE Transactions on Information and Systems

IS - 3

ER -