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)}\) .

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Feedback Vertex Set for Pseudo-disk Graphs in Subexponential FPT Time

  • Gaétan Berthe,
  • Marin Bougeret,
  • Daniel Gonçalves,
  • Jean-Florent Raymond

摘要

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)}\) .