We prove new parameterized complexity results for the FO Model Checking problem and in particular for Independent Set, for two recently introduced subclasses of H-graphs, namely proper H-graphs and non-crossing H-graphs. It is known that proper H-graphs, and thus H-graphs, may have unbounded twin-width. However, we prove that for every multigraph H, non-crossing H-graphs have bounded proper mixed-thinness, and thus bounded twin-width. Consequently, we can apply a well-known result of Bonnet, Kim, Thomassé, and Watrigant (2021) to find that the FO Model Checking problem is in \(\textsf{FPT}\) for non-crossing H-graphs when parameterized by \(\Vert H \Vert +\ell \) , where \(\Vert H \Vert \) is the size of H and \(\ell \) is the size of a formula. In particular, this implies that Independent Set is in \(\textsf{FPT}\) for non-crossing H-graphs when parameterized by \(\Vert H \Vert +k\) , where k is the solution size. In contrast, Independent Set for general H-graphs is known to be \(\mathsf {W[1]}\) -hard when parameterized by \(\Vert H \Vert +k\) . We strengthen the latter result by proving that Independent Set is \(\mathsf {W[1]}\) -hard even on proper H-graphs when parameterized by \(\Vert H \Vert +k\) . In this way, we solve, subject to \(\mathsf {W[1]}\ne \textsf{FPT}\) , an open problem of Chaplick (2023), who asked whether there exist problems that can be solved faster for non-crossing H-graphs than for proper H-graphs.

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

Non-crossing H-Graphs: A Generalization of Proper Interval Graphs Admitting FPT Algorithms

  • Flavia Bonomo-Braberman,
  • Nick Brettell,
  • Andrea Munaro,
  • Daniël Paulusma

摘要

We prove new parameterized complexity results for the FO Model Checking problem and in particular for Independent Set, for two recently introduced subclasses of H-graphs, namely proper H-graphs and non-crossing H-graphs. It is known that proper H-graphs, and thus H-graphs, may have unbounded twin-width. However, we prove that for every multigraph H, non-crossing H-graphs have bounded proper mixed-thinness, and thus bounded twin-width. Consequently, we can apply a well-known result of Bonnet, Kim, Thomassé, and Watrigant (2021) to find that the FO Model Checking problem is in \(\textsf{FPT}\) for non-crossing H-graphs when parameterized by \(\Vert H \Vert +\ell \) , where \(\Vert H \Vert \) is the size of H and \(\ell \) is the size of a formula. In particular, this implies that Independent Set is in \(\textsf{FPT}\) for non-crossing H-graphs when parameterized by \(\Vert H \Vert +k\) , where k is the solution size. In contrast, Independent Set for general H-graphs is known to be \(\mathsf {W[1]}\) -hard when parameterized by \(\Vert H \Vert +k\) . We strengthen the latter result by proving that Independent Set is \(\mathsf {W[1]}\) -hard even on proper H-graphs when parameterized by \(\Vert H \Vert +k\) . In this way, we solve, subject to \(\mathsf {W[1]}\ne \textsf{FPT}\) , an open problem of Chaplick (2023), who asked whether there exist problems that can be solved faster for non-crossing H-graphs than for proper H-graphs.