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 and Triangle Hitting. 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 given a geometric representation FVS can be solved in time \(2^{\mathcal {O}(k^{9/10}\log k)}n^{\mathcal {O}(1)}\) and TH in time \(2^{\mathcal {O}(k^{3/4}\log k)}n^{\mathcal {O}(1)}\) .