Kick the cliques

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) k) } n^Oᵣ (1) in pseudo-disk graphs and map-graphs; * 2^Oₓ, ₑ (k^{2/3 k) } n^Oᵣ (1) in Kₓ, ₓ-subgraph-free string graphs; and * 2^O₇, ₑ (k^{2/3 k) } n^Oᵣ (1) in H-minor-free graphs.