IEICE TRANSACTIONS on Fundamentals
Algorithms for the Independent Feedback Vertex Set Problem
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E98-A No.6 pp.1179-1188
- Publication Date
- 2015/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E98.A.1179
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Yuma TAMURA
Tohoku University,c/o Global Research Center for Big Data Mathematics, NII
Takehiro ITO
Tohoku University
Xiao ZHOU
Tohoku University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yuma TAMURA, Takehiro ITO, Xiao ZHOU, "Algorithms for the Independent Feedback Vertex Set Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E98-A, no. 6, pp. 1179-1188, June 2015, doi: 10.1587/transfun.E98.A.1179.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E98.A.1179/_p
Copy
@ARTICLE{e98-a_6_1179,
author={Yuma TAMURA, Takehiro ITO, Xiao ZHOU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Algorithms for the Independent Feedback Vertex Set Problem},
year={2015},
volume={E98-A},
number={6},
pages={1179-1188},
abstract={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.},
keywords={},
doi={10.1587/transfun.E98.A.1179},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - Algorithms for the Independent Feedback Vertex Set Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1179
EP - 1188
AU - Yuma TAMURA
AU - Takehiro ITO
AU - Xiao ZHOU
PY - 2015
DO - 10.1587/transfun.E98.A.1179
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E98-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2015
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.
ER -
English
