Maximum Minimal Feedback Vertex Set: A Parameterized Perspective
share
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^𝒪(1). 2) Next, we consider the problem parameterized by the vertex cover number of the input graph (denoted by 𝗏𝖼(G)), and design an algorithm with running time 2^𝒪(𝗏𝖼(G)log𝗏𝖼(G))n^𝒪(1). We complement this result by showing that the problem parameterized by 𝗏𝖼(G) does not admit a polynomial compression unless coNP ⊆ NP/poly. 3) Finally, we give an FPT-approximation scheme (fpt-AS) parameterized by 𝗏𝖼(G). That is, we design an algorithm that for every ϵ >0, runs in time 2^𝒪(𝗏𝖼(G)/ϵ) n^𝒪(1) and returns a minimal feedback vertex set of size at least (1-ϵ) opt.
READ FULL TEXT