Advertisement
Published in:
2020 | OriginalPaper | Chapter
Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs
Authors : Yuma Tamura, Takehiro Ito, Xiao Zhou
Published in: WALCOM: Algorithms and Computation
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Given a 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. In this paper, we study the approximability of the problem. We first show that, for any fixed \(\varepsilon > 0\), unless \(\mathrm{P} = \mathrm{NP}\), there exists no polynomial-time \(n^{1-\varepsilon }\)-approximation algorithm even for bipartite planar graphs. This gives a contrast to the existence of a polynomial-time 2-approximation algorithm for the original feedback vertex set problem on general graphs. We then give an \(\alpha (\mathrm{\Delta }-1)/2\)-approximation algorithm for bipartite graphs G of maximum degree \(\mathrm{\Delta }\), which runs in \(O(t(G)+\mathrm{\Delta }n)\) time, under the assumption that there is an \(\alpha \)-approximation algorithm for the original feedback vertex set problem on bipartite graphs which runs in O(t(G)) time.