2021年
Approximability of the independent feedback vertex set problem for bipartite graphs.
Theor. Comput. Sci.
- ,
- ,
- 巻
- 849
- 号
- 開始ページ
- 227
- 終了ページ
- 236
- 記述言語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.1016/j.tcs.2020.10.026
Given an undirected graph G with n vertices, the independent feedback vertex set problem is to find a vertex subset F of G with the minimum number of vertices such that F is both an independent set and a feedback vertex set of G, if it exists. This problem is known to be NP-hard for bipartite planar graphs of maximum degree four. In this paper, we study the approximability of the problem. We first show that, for any fixed ε>0, unless P=NP, there exists no polynomial-time n1−ε-approximation algorithm even for bipartite planar graphs. We then give an α(Δ−1)/2-approximation algorithm for bipartite graphs G of maximum degree Δ, which runs in t(α,G)+O(Δn) time, under the assumption that there is an α-approximation algorithm for the original feedback vertex set problem on bipartite graphs which runs in t(α,G) time. This algorithmic result also yields a polynomial-time (exact) algorithm for the independent feedback vertex set problem on bipartite graphs of maximum degree three.
- リンク情報
-
- DOI
- https://doi.org/10.1016/j.tcs.2020.10.026
- DBLP
- https://dblp.uni-trier.de/rec/journals/tcs/TamuraI021
- URL
- https://dblp.uni-trier.de/db/journals/tcs/tcs849.html#TamuraI021
- Scopus
- https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85096369008&origin=inward 本文へのリンクあり
- Scopus Citedby
- https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=85096369008&origin=inward
- ID情報
-
- DOI : 10.1016/j.tcs.2020.10.026
- ISSN : 0304-3975
- DBLP ID : journals/tcs/TamuraI021
- SCOPUS ID : 85096369008