Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.01465 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916308145143808 |
|---|---|
| author | Berthe, Gaétan Bougeret, Marin Gonçalves, Daniel Raymond, Jean-Florent |
| author_facet | Berthe, Gaétan Bougeret, Marin Gonçalves, Daniel Raymond, Jean-Florent |
| contents | In the $K_r$-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_r$-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_r$-Cover in time
* $2^{O_r\left (k^{(r+1)/(r+2)}\log k \right)} \cdot n^{O_r(1)}$ in pseudo-disk graphs and map-graphs;
* $2^{O_{t,r}(k^{2/3}\log k)} \cdot n^{O_r(1)}$ in $K_{t,t}$-subgraph-free string graphs; and
* $2^{O_{H,r}(k^{2/3}\log k)} \cdot n^{O_r(1)}$ in $H$-minor-free graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_01465 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Kick the cliques Berthe, Gaétan Bougeret, Marin Gonçalves, Daniel Raymond, Jean-Florent Data Structures and Algorithms In the $K_r$-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_r$-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_r$-Cover in time * $2^{O_r\left (k^{(r+1)/(r+2)}\log k \right)} \cdot n^{O_r(1)}$ in pseudo-disk graphs and map-graphs; * $2^{O_{t,r}(k^{2/3}\log k)} \cdot n^{O_r(1)}$ in $K_{t,t}$-subgraph-free string graphs; and * $2^{O_{H,r}(k^{2/3}\log k)} \cdot n^{O_r(1)}$ in $H$-minor-free graphs. |
| title | Kick the cliques |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.01465 |