Non-crossing H-graphs: a generalization of proper interval graphs admitting FPT algorithms

Authors: Flavia Bonomo-Braberman, Nick Brettell, Andrea Munaro and Daniël Paulusma.

Abstract:
Weprove 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 connected multigraph H with no selfloops, 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 f ind that the FO Model Checking problem is in FPT for non-crossing H-graphs when parameterized by ∥H∥+ℓ, where ∥H∥ is the size of H and ℓ is the size of a formula. In particular, this implies that Independent Set is in FPT on non-crossing H-graphs when parameterized by ∥H∥+k, where k is the solution size. In contrast, Independent Set for general H-graphs is W[1]-hard when parameterized by ∥H∥ +k. We strengthen the latter result by proving that Independent Set is W[1]-hard even on proper H-graphs when parameterized by ∥H∥ +k. In this way, we solve, subject to W[1]= 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.

More information:
https://arxiv.org/abs/2501.11192