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 -