TY - JOUR

T1 - Algorithms for the independent feedback vertex set problem

AU - Tamura, Yuma

AU - Ito, Takehiro

AU - Zhou, Xiao

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

PY - 2015/6/1

Y1 - 2015/6/1

N2 - 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.

AB - 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.

KW - Fixed parameter tractability

KW - Graph algorithm

KW - Independent feedback vertex set

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

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

U2 - 10.1587/transfun.E98.A.1179

DO - 10.1587/transfun.E98.A.1179

M3 - Article

AN - SCOPUS:84930424591

SN - 0916-8508

VL - E98A

SP - 1179

EP - 1188

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 6

ER -