Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909373731700736 |
|---|---|
| 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 this paper, we investigate the existence of parameterized algorithms running in subexponential time for two fundamental cycle-hitting problems: Feedback Vertex Set (FVS) and Triangle Hitting (TH). We focus on the class of pseudo-disk graphs, which forms a common generalization of several graph classes where such results exist, like disk graphs and square graphs. In these graphs, we show that TH can be solved in time $2^{O(k^{3/4}\log k)}n^{O(1)}$, and given a geometric representation FVS can be solved in time $2^{O(k^{6/7}\log k)}n^{O(1)}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23878 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time Berthe, Gaétan Bougeret, Marin Gonçalves, Daniel Raymond, Jean-Florent Data Structures and Algorithms Discrete Mathematics In this paper, we investigate the existence of parameterized algorithms running in subexponential time for two fundamental cycle-hitting problems: Feedback Vertex Set (FVS) and Triangle Hitting (TH). We focus on the class of pseudo-disk graphs, which forms a common generalization of several graph classes where such results exist, like disk graphs and square graphs. In these graphs, we show that TH can be solved in time $2^{O(k^{3/4}\log k)}n^{O(1)}$, and given a geometric representation FVS can be solved in time $2^{O(k^{6/7}\log k)}n^{O(1)}$. |
| title | Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2410.23878 |