The Feedback Vertex Set (FVS) problem, together with several of its variants, is arguably one of the most well-studied problems in the field of Parameterized Complexity. Two versions of the problem that have garnered significant interest involve the inclusion of an independence constraint and a connectivity constraint in the solution. This paper introduces generalized versions of both these variants, known as At least-c-FVS and At most-c-FVS, respectively, serving as extensions of Connected FVS and Independent FVS, respectively. The problem At most-c-FVS (resp., At least-c-FVS) is defined as follows: given a graph G and an integer k, the objective is to determine whether there exists a subset \(S \subseteq V(G)\) , with \(|S| \le k\) , such that the subgraph \(G-S\) is a forest and each component of G[S] contains at most c (resp., at least c) vertices. We study these problems in the realm of Parameterized Complexity and obtain the following results: – At most-c-FVS parameterized by k has a kernel of size \(\mathcal {O}(k^{3+c})\) , and admits an FPT algorithm running in time \( 2^{\mathcal {O}(k) +c \cdot \log (k^2)} \cdot n^{\mathcal {O}(1)}\) . – At least-c-FVS parameterized by k has no kernel of size \(k^{f(c)}\) for any computable function f (unless co-NP \(\subseteq \) NP/poly), but admits an FPT algorithm running in time \(2^{\mathcal {O}(k)}\cdot n^{\mathcal {O}(1)}\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Parameterized Complexity of Feedback Vertex Set with Connectivity Constraints

  • Ankit Abhinav,
  • Satyabrata Jana,
  • Nidhi Purohit,
  • Abhishek Sahu,
  • Saket Saurabh

摘要

The Feedback Vertex Set (FVS) problem, together with several of its variants, is arguably one of the most well-studied problems in the field of Parameterized Complexity. Two versions of the problem that have garnered significant interest involve the inclusion of an independence constraint and a connectivity constraint in the solution. This paper introduces generalized versions of both these variants, known as At least-c-FVS and At most-c-FVS, respectively, serving as extensions of Connected FVS and Independent FVS, respectively. The problem At most-c-FVS (resp., At least-c-FVS) is defined as follows: given a graph G and an integer k, the objective is to determine whether there exists a subset \(S \subseteq V(G)\) , with \(|S| \le k\) , such that the subgraph \(G-S\) is a forest and each component of G[S] contains at most c (resp., at least c) vertices. We study these problems in the realm of Parameterized Complexity and obtain the following results: – At most-c-FVS parameterized by k has a kernel of size \(\mathcal {O}(k^{3+c})\) , and admits an FPT algorithm running in time \( 2^{\mathcal {O}(k) +c \cdot \log (k^2)} \cdot n^{\mathcal {O}(1)}\) . – At least-c-FVS parameterized by k has no kernel of size \(k^{f(c)}\) for any computable function f (unless co-NP \(\subseteq \) NP/poly), but admits an FPT algorithm running in time \(2^{\mathcal {O}(k)}\cdot n^{\mathcal {O}(1)}\) .