2026-07-22T10:25:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24956 2026-02-09T08:02:35Z ddc:004 open_access

Quadratic Kernel for Cliques or Trees Vertex Deletion Kumabe, Soh Fixed-Parameter Tractability Kernelization Deletion to Scattered Graph Classes Cluster Vertex Deletion Feedback Vertex Set We consider Cliques or Trees Vertex Deletion, which is a hybrid of two fundamental parameterized problems: Cluster Vertex Deletion and 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⁵) vertices for this problem, which was recently improved to O(k⁴) by Tsur (IPL, 2025). Our main result is a kernel of O(k²) vertices. This result closes the gap between the kernelization result for Feedback Vertex Set, which corresponds to the case where each connected component of G-X must be a tree. Although both cluster vertex deletion number and 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 cliques or trees vertex deletion number as a structural parameter. We prove that 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Soh Kumabe 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.48 urn:nbn:de:0030-drops-249568 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.48 eng https://creativecommons.org/licenses/by/4.0/legalcode