Reconfiguration of vertex covers in a graph

Takehiro Ito; Hiroyuki Nooka; Xiao Zhou

doi:10.1007/978-3-319-19315-1_15

Reconfiguration of vertex covers in a graph

Takehiro Ito, Hiroyuki Nooka, Xiao Zhou

INF - System Information Sciences

Tohoku University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

Abstract

Suppose that we are given two vertex covers C₀ and C_t 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 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.

Original language	English
Title of host publication	Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Revised Selected Papers
Editors	Dalibor Froncek, Jan Kratochvíl, Mirka Miller
Publisher	Springer Verlag
Pages	164-175
Number of pages	12
ISBN (Electronic)	9783319193144
DOIs	https://doi.org/10.1007/978-3-319-19315-1_15
Publication status	Published - 2015
Event	25th International Workshop on Combinatorial Algorithms, IWOCA 2014 - Duluth, United States Duration: 2014 Oct 15 → 2014 Oct 17

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8986
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	25th International Workshop on Combinatorial Algorithms, IWOCA 2014
Country/Territory	United States
City	Duluth
Period	14/10/15 → 14/10/17

Access to Document

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

Cite this

Ito, T., Nooka, H., & Zhou, X. (2015). Reconfiguration of vertex covers in a graph. In D. Froncek, J. Kratochvíl, & M. Miller (Eds.), Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Revised Selected Papers (pp. 164-175). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8986). Springer Verlag. https://doi.org/10.1007/978-3-319-19315-1_15

Ito, Takehiro ; Nooka, Hiroyuki ; Zhou, Xiao. / Reconfiguration of vertex covers in a graph. Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Revised Selected Papers. editor / Dalibor Froncek ; Jan Kratochvíl ; Mirka Miller. Springer Verlag, 2015. pp. 164-175 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2b58f802b8ef4a51b4b9096a8b5261f2,

title = "Reconfiguration of vertex covers in a graph",

abstract = "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.",

author = "Takehiro Ito and Hiroyuki Nooka and Xiao Zhou",

note = "Funding Information: We are grateful to Ryuhei Uehara for fruitful discussions. This work is partially supported by JSPS KAKENHI 25106504 and 25330003. Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 25th International Workshop on Combinatorial Algorithms, IWOCA 2014 ; Conference date: 15-10-2014 Through 17-10-2014",

year = "2015",

doi = "10.1007/978-3-319-19315-1_15",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "164--175",

editor = "Dalibor Froncek and Jan Kratochv{\'i}l and Mirka Miller",

booktitle = "Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Revised Selected Papers",

address = "Germany",

}

Ito, T, Nooka, H & Zhou, X 2015, Reconfiguration of vertex covers in a graph. in D Froncek, J Kratochvíl & M Miller (eds), Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8986, Springer Verlag, pp. 164-175, 25th International Workshop on Combinatorial Algorithms, IWOCA 2014, Duluth, United States, 14/10/15. https://doi.org/10.1007/978-3-319-19315-1_15

Reconfiguration of vertex covers in a graph. / Ito, Takehiro; Nooka, Hiroyuki; Zhou, Xiao.
Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Revised Selected Papers. ed. / Dalibor Froncek; Jan Kratochvíl; Mirka Miller. Springer Verlag, 2015. p. 164-175 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8986).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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 -

Ito T, Nooka H, Zhou X. Reconfiguration of vertex covers in a graph. In Froncek D, Kratochvíl J, Miller M, editors, Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Revised Selected Papers. Springer Verlag. 2015. p. 164-175. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-19315-1_15

Reconfiguration of vertex covers in a graph

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this