On the Parameterized Complexity of Connected Cluster Vertex Deletion
摘要
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\) .