Algorithms for the Independent Feedback Vertex Set Problem

• TAMURA Yuma

  Graduate School of Information Sciences, Tohoku University JST, ERATO, Kawarabayashi Large Graph Project, c/o Global Research Center for Big Data Mathematics, NII

• ITO Takehiro

  Graduate School of Information Sciences, Tohoku University

• ZHOU Xiao

  Graduate School of Information Sciences, Tohoku University

抄録

A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices, from the viewpoint of graph classes. This problem is NP-hard even for planar bipartite graphs of maximum degree four. However, we show that the problem is solvable in linear time for graphs having tree-like structures, more specifically, for bounded treewidth graphs, chordal graphs and cographs. We then give a fixed-parameter algorithm for planar graphs when parameterized by the solution size. Such a fixed-parameter algorithm is already known for general graphs, but our algorithm is exponentially faster than the known one.

収録刊行物

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98.A (6), 1179-1188, 2015

  一般社団法人 電子情報通信学会

キーワード

• fixed parameter tractability
• graph algorithm
• independent feedback vertex set

詳細情報

• CRID: 1390001206310825856
• NII論文ID: 130005071827
• DOI: 10.1587/transfun.e98.a.1179
• ISSN: 17451337
• ISSN: 09168508
• Web Site: https://www.jstage.jst.go.jp/article/transfun/E98.A/6/E98.A_1179/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可