Kicken Sie die Cliquen

Im Kᵣ-Cover-Problem muss man, gegeben einen Graphen G und eine ganze Zahl k, entscheiden, ob es eine Menge von höchstens k Vertizes gibt, deren Entfernung alle r-Cliquen von G zerstört. In diesem Papier geben wir einen Algorithmus für Kᵣ-Cover an, der in subexponentieller FPT-Zeit auf Graphklassen läuft, die zwei einfache Bedingungen bezüglich Cliquen und Baumweite erfüllen. Als Anwendung zeigen wir, dass unser Algorithmus Kᵣ-Cover in der Zeit * 2^Oᵣ (k^{(r+1)/(r+2) k)} n^Oᵣ (1) in pseudo-Scheibengraphen und Karten-Grafen löst; * 2^Oₓ, ₑ (k^{2/3 k)} n^Oᵣ (1) in Kₓ, ₓ-untergraphfreien String-Grafen; und * 2^O₇, ₑ (k^{2/3 k)} n^Oᵣ (1) in H-Minor-freien Graphen.