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 {\sc 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\'e, and Watrigant (2021) to find that the FO Model Checking problem is in $\mathsf{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 {\sc Independent Set} is in $\mathsf{FPT}$ for non-crossing $H$-graphs when parameterized by $\Vert H \Vert+k$, where $k$ is the solution size. In contrast, {\sc 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 {\sc 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]}\neq \mathsf{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.