Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs
Approximability of the Independent Feedback Vertex Set Problem for Bipartite Graphs
复制标题
二部图独立反馈顶点集问题的逼近
DOI：
10.1016/j.tcs.2020.10.026
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Takehiro Ito and Xiao Zhou
中科院分区：
文献类型：
--
作者：
Yuma Tamura;Takehiro Ito and Xiao Zhou
给定一个n阶无向图G，独立反馈点集问题是寻找G的一个顶点数最少的点子集F，使得F既是G的一个独立集，又是G的一个反馈点集（如果存在的话）。对于最大度为4的二部平面图，这个问题是NP-困难的。在本文中，我们研究了问题的可逼近性。我们首先证明，对于任何固定的ε> 0，除非P= NP，甚至对于二部平面图也不存在多项式时间的n 1− ε-近似算法。在假定二部图上的反馈点集问题存在一个在t（α，G）时间内运行的α-近似算法的假设下，给出了最大度为Δ的二部图G在t（α，G）+ O（Δ n）时间内运行的α（Δ− 1）/2-近似算法.这个算法的结果也产生一个多项式时间（精确）算法的独立反馈顶点集问题的最大程度的三个二部图。
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 n 1− ε-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.