Anzeige
Erschienen in:
2020 | OriginalPaper | Buchkapitel
Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs
verfasst von : Yuma Tamura, Takehiro Ito, Xiao Zhou
Erschienen in: WALCOM: Algorithms and Computation
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.