In the Kᵣ-Cover 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ᵣ-Cover 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ᵣ-Cover in time * 2^Oᵣ (k(r+1)/(r+2)log k ) · nOᵣ(1) in pseudo-disk graphs and map-graphs; * 2^Ot,r(k2/3log k) · nOᵣ(1) in Kt,t-subgraph-free string graphs; and * 2^OH,r(k2/3log k) · nOᵣ(1) in H-minor-free graphs.
No takes yet. Share an insight, caveat, or question.
Berthe et al. (2024) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: