In the Connected Cluster Vertex Deletion problem, the input is a graph \( G \)  and an integer \( k \) , and the task is to determine whether there exists a vertex set \( S \subseteq V(G) \) of size at most \( k \) such that \( G[S] \) is connected and the graph \( G - S \) is a cluster graph—that is, every connected component of \( G - S \)  is a clique. The problem is known to be NP-complete and has been previously studied from the viewpoint of classical computational complexity. In this paper, we initiate the study of Connected Cluster Vertex Deletion from the perspective of parameterized complexity. We show that the problem is fixed-parameter tractable (FPT) when parameterized by the solution size \( k \) , by designing an algorithm with running time \( \mathcal {O}(5.2^k \cdot n^{\mathcal {O}(1)} )\) . Furthermore, we show that Connected Cluster Vertex Deletion does not admit a polynomial kernel unless \(\textsf {NP} \subseteq \textsf {coNP}/\textsf {Poly}\) . To cope with this kernelization lower bound, we complement our result by designing a polynomial-size \(\alpha \) -approximate kernel for any fixed \(\alpha > 1\) .

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

On the Parameterized Complexity of Connected Cluster Vertex Deletion

  • Ankit Abhinav,
  • Sriram Bhyravarapu,
  • A. Mohanapriya,
  • Saket Saurabh

摘要

In the Connected Cluster Vertex Deletion problem, the input is a graph \( G \)  and an integer \( k \) , and the task is to determine whether there exists a vertex set \( S \subseteq V(G) \) of size at most \( k \) such that \( G[S] \) is connected and the graph \( G - S \) is a cluster graph—that is, every connected component of \( G - S \)  is a clique. The problem is known to be NP-complete and has been previously studied from the viewpoint of classical computational complexity. In this paper, we initiate the study of Connected Cluster Vertex Deletion from the perspective of parameterized complexity. We show that the problem is fixed-parameter tractable (FPT) when parameterized by the solution size \( k \) , by designing an algorithm with running time \( \mathcal {O}(5.2^k \cdot n^{\mathcal {O}(1)} )\) . Furthermore, we show that Connected Cluster Vertex Deletion does not admit a polynomial kernel unless \(\textsf {NP} \subseteq \textsf {coNP}/\textsf {Poly}\) . To cope with this kernelization lower bound, we complement our result by designing a polynomial-size \(\alpha \) -approximate kernel for any fixed \(\alpha > 1\) .