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

October 31, 2024 Β· Declared Dead Β· πŸ› International Workshop on Graph-Theoretic Concepts in Computer Science

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors GaΓ©tan Berthe, Marin Bougeret, Daniel GonΓ§alves, Jean-Florent Raymond arXiv ID 2410.23878 Category cs.DS: Data Structures & Algorithms Cross-listed cs.DM Citations 4 Venue International Workshop on Graph-Theoretic Concepts in Computer Science Last Checked 4 months ago
Abstract
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)}$.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted