Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time

Autor:	Berthe, Gaétan, Bougeret, Marin, Gonçalves, Daniel, Raymond, Jean-Florent
Rok vydání:	2024
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Discrete Mathematics
Druh dokumentu:	Working Paper
Popis:	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)}$. Comment: Presented at the conference WG 2024
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2410.23878 Zobrazit plný text záznamu View this record from Arxiv