論文

2021年

Approximability of the independent feedback vertex set problem for bipartite graphs.

Theor. Comput. Sci.
  • Yuma Tamura
  • ,
  • Takehiro Ito
  • ,
  • Xiao Zhou 0001

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

エクスポート
BibTeX RIS