3 papers
cs.DS2026
Pushing the frontiers of subexponential FPT time for Feedback Vertex Set
Gaétan Berthe, Marin Bougeret, Daniel Gonçalves +1
The paper deals with the Feedback Vertex Set problem parameterized by the solution size. Given a graph and a parameter , one has to decide if there is a set of at most $…
cs.DS2025
Robust Algorithms for Path and Cycle Problems in Geometric Intersection Graphs
Malory Marin, Jean-Florent Raymond, Rémi Watrigant
We study the design of robust subexponential algorithms for classical connectivity problems on intersection graphs of similarly sized fat objects in . In this setting…
cs.DS2024
Feedback Vertex Set for pseudo-disk graphs in subexponential FPT time
Gaétan Berthe, Marin Bougeret, Daniel Gonçalves +1
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 Tri…