Non-crossing H-Graphs: A Generalization of Proper Interval Graphs Admitting FPT Algorithms
摘要
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.