{"ID":2868509,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.16815","arxiv_id":"2509.16815","title":"Quadratic Kernel for Cliques or Trees Vertex Deletion","abstract":"We consider \\textsc{Cliques or Trees Vertex Deletion}, which is a hybrid of two fundamental parameterized problems: \\textsc{Cluster Vertex Deletion} and \\textsc{Feedback Vertex Set}. In this problem, we are given an undirected graph $G$ and an integer $k$, and asked to find a vertex subset $X$ of size at most $k$ such that each connected component of $G-X$ is either a clique or a tree. Jacob et al. (ISAAC, 2024) provided a kernel of $O(k^5)$ vertices for this problem, which was recently improved to $O(k^4)$ by Tsur (IPL, 2025). Our main result is a kernel of $O(k^2)$ vertices. This result closes the gap between the kernelization result for \\textsc{Feedback Vertex Set}, which corresponds to the case where each connected component of $G-X$ must be a tree. Although both \\emph{cluster vertex deletion number} and \\emph{feedback vertex set number} are well-studied structural parameters, little attention has been given to parameters that generalize both of them. In fact, the lowest common well-known generalization of them is clique-width, which is a highly general parameter. To fill the gap here, we initiate the study of the \\emph{cliques or trees vertex deletion number} as a structural parameter. We prove that \\textsc{Longest Cycle}, which is a fundamental problem that does not admit $o(n^k)$-time algorithm unless ETH fails when $k$ is the clique-width, becomes fixed-parameter tractable when parameterized by the cliques or trees vertex deletion number.","short_abstract":"We consider \\textsc{Cliques or Trees Vertex Deletion}, which is a hybrid of two fundamental parameterized problems: \\textsc{Cluster Vertex Deletion} and \\textsc{Feedback Vertex Set}. In this problem, we are given an undirected graph $G$ and an integer $k$, and asked to find a vertex subset $X$ of size at most $k$ such...","url_abs":"https://arxiv.org/abs/2509.16815","url_pdf":"https://arxiv.org/pdf/2509.16815v1","authors":"[\"Soh Kumabe\"]","published":"2025-09-20T21:33:24Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}