TY - GEN

T1 - Reconfiguration of vertex covers in a graph

AU - Ito, Takehiro

AU - Nooka, Hiroyuki

AU - Zhou, Xiao

N1 - Funding Information:
We are grateful to Ryuhei Uehara for fruitful discussions. This work is partially supported by JSPS KAKENHI 25106504 and 25330003.
Publisher Copyright:
© Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

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.

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

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

U2 - 10.1007/978-3-319-19315-1_15

DO - 10.1007/978-3-319-19315-1_15

M3 - Conference contribution

AN - SCOPUS:84937485512

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 164

EP - 175

BT - Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Revised Selected Papers

A2 - Froncek, Dalibor

A2 - Kratochvíl, Jan

A2 - Miller, Mirka

PB - Springer Verlag

T2 - 25th International Workshop on Combinatorial Algorithms, IWOCA 2014

Y2 - 15 October 2014 through 17 October 2014

ER -