Reconfiguration of Vertex Covers in a Graph

• ITO Takehiro

  Graduate School of Information Sciences, Tohoku University

• NOOKA Hiroyuki

  Graduate School of Information Sciences, Tohoku University

• ZHOU Xiao

  Graduate School of Information Sciences, Tohoku University

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.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E99.D (3), 598-606, 2016

  The Institute of Electronics, Information and Communication Engineers

Keywords

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

Details

• CRID: 1390001204377430016
• NII Article ID: 130005131815
• DOI: 10.1587/transinf.2015fcp0010
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E99.D/3/E99.D_2015FCP0010/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed