TY - JOUR
T1 - Approximability of the independent feedback vertex set problem for bipartite graphs
AU - Tamura, Yuma
AU - Ito, Takehiro
AU - Zhou, Xiao
N1 - Funding Information:
Partially supported by JSPS KAKENHI Grant Number JP20J11259, Japan.Partially supported by JST CREST Grant Number JPMJCR1402, and JSPS KAKENHI Grant Numbers JP18H04091 and JP19K11814, Japan.Partially supported by JSPS KAKENHI Grant Number JP19K11813, Japan.We are grateful to anonymous referees of the preliminary version [20] and of this journal version for their helpful suggestions. We thank the support by the Research Institute for Mathematical Sciences, an International Joint Usage/Research Center located in Kyoto University, when Yuma Tamura presented the preliminary version of this paper.
Funding Information:
We are grateful to anonymous referees of the preliminary version [20] and of this journal version for their helpful suggestions. We thank the support by the Research Institute for Mathematical Sciences , an International Joint Usage/Research Center located in Kyoto University, when Yuma Tamura presented the preliminary version of this paper.
Publisher Copyright:
© 2020 Elsevier B.V.
PY - 2021/1/6
Y1 - 2021/1/6
N2 - 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.
AB - 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.
KW - Bipartite graphs
KW - Graph algorithms
KW - Inapproximability
KW - Independent feedback vertex set
UR - http://www.scopus.com/inward/record.url?scp=85096369008&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85096369008&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2020.10.026
DO - 10.1016/j.tcs.2020.10.026
M3 - Article
AN - SCOPUS:85096369008
SN - 0304-3975
VL - 849
SP - 227
EP - 236
JO - Theoretical Computer Science
JF - Theoretical Computer Science
ER -