Feedback Vertex Set for Pseudo-disk Graphs in Subexponential FPT Time
Feedback Vertex Set for Pseudo-disk Graphs in Subexponential FPT Time
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)}$.
Presented at the conference WG 2024
- Claude Bernard University Lyon 1 France
- Ecole Normale Supérieure de Lyon France
- University of Montpellier France
- École Normale Supérieure de Lyon France
- University of Lyon System France
Geometric inter section graphs, FOS: Computer and information sciences, Pseudo-disk graphs, Discrete Mathematics (cs.DM), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Cycle-hitting problems, [INFO] Computer Science [cs], Subexponential FPT algorithms, Computer Science - Discrete Mathematics
Geometric inter section graphs, FOS: Computer and information sciences, Pseudo-disk graphs, Discrete Mathematics (cs.DM), Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), Cycle-hitting problems, [INFO] Computer Science [cs], Subexponential FPT algorithms, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!