论文标题
最大最小反馈顶点集：参数化的视角
Maximum Minimal Feedback Vertex Set: A Parameterized Perspective
论文作者
论文摘要
在本文中，我们研究了经典反馈顶点集（FVS）问题的最大化版本，即在参数化复杂性的领域中，最大最大FVS问题。在此问题中，鉴于无向图$ g $，一个正整数$ k $，问题是要检查$ g $是否具有最小的反馈顶点大小至少至少$ k $。我们获得了最大最小FVS的以下结果。 1）我们首先设计了一个固定参数可处理的（FPT）算法，用于最大最低fvs，以$ 10^kn^{\ Mathcal {o}（O}（1）} $运行。 2）接下来，我们考虑通过输入图的顶点封面编号（用$ \ Mathsf {vc}（g）$表示）的问题，并设计具有运行时间$ 2^{\ Mathcal {o}的算法\ Mathsf {vc}（g））} n^{\ Mathcal {O}（1）} $。我们通过证明$ \ mathsf {vc}（g）$参数化的问题来补充这一结果，除非conp $ \ subseteq $ np/poly，否则除非conp $ \ subseteq $ np/poly。 3）最后，我们给出了由$ \ mathsf {vc}（g）$参数化的fpt-approximation方案（fpt-as）。也就是说，我们设计了一种算法，每$ε> 0 $，按时运行$ 2^{\ mathcal {o} \ left（\ frac {\ frac {\ mathsf {vc}（vc}（g）}（g）}ε\ right）} n^{n^{\ nathcal {\ nathcal {\ natercal {o} $} $（1-ε）{\ sf opt} $。
In this paper we study a maximization version of the classical Feedback Vertex Set (FVS) problem, namely, the Max Min FVS problem, in the realm of parameterized complexity. In this problem, given an undirected graph $G$, a positive integer $k$, the question is to check whether $G$ has a minimal feedback vertex set of size at least $k$. We obtain following results for Max Min FVS. 1) We first design a fixed parameter tractable (FPT) algorithm for Max Min FVS running in time $10^kn^{\mathcal{O}(1)}$. 2) Next, we consider the problem parameterized by the vertex cover number of the input graph (denoted by $\mathsf{vc}(G)$), and design an algorithm with running time $2^{\mathcal{O}(\mathsf{vc}(G)\log \mathsf{vc}(G))}n^{\mathcal{O}(1)}$. We complement this result by showing that the problem parameterized by $\mathsf{vc}(G)$ does not admit a polynomial compression unless coNP $\subseteq$ NP/poly. 3) Finally, we give an FPT-approximation scheme (fpt-AS) parameterized by $\mathsf{vc}(G)$. That is, we design an algorithm that for every $ε>0$, runs in time $2^{\mathcal{O}\left(\frac{\mathsf{vc}(G)}ε\right)} n^{\mathcal{O}(1)}$ and returns a minimal feedback vertex set of size at least $(1-ε){\sf opt}$.
