2026-08-18T02:34:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22239 2024-12-05T15:32:41Z ddc:004 open_access

Kick the Cliques Berthe, Gaétan Bougeret, Marin Gonçalves, Daniel Raymond, Jean-Florent Subexponential FPT algorithms implicit hitting set problems geometric intersection graphs In the K_r-Hitting problem, given a graph G and an integer k one has to decide if there exists a set of at most k vertices whose removal destroys all r-cliques of G. In this paper we give an algorithm for K_r-Hitting that runs in subexponential FPT time on graph classes satisfying two simple conditions related to cliques and treewidth. As an application we show that our algorithm solves K_r-Hitting in time - 2^{O_r(k^{(r+1)/(r+2)}log k)} ⋅ n^{O_r(1)} in pseudo-disk graphs and map-graphs; - 2^{O_{t,r}(k^{2/3}log k)} ⋅ n^{O_r(1)} in K_{t,t}-subgraph-free string graphs; and - 2^{O_{H,r}(k^{2/3}log k)} ⋅ n^{O_r(1)} in H-minor-free graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gaétan Berthe and Marin Bougeret and Daniel Gonçalves and Jean-Florent Raymond 2024 Is Part Of LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2024.13 urn:nbn:de:0030-drops-222397 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.13 eng https://creativecommons.org/licenses/by/4.0/legalcode