{"id":3013,"date":"2025-09-15T11:27:07","date_gmt":"2025-09-15T14:27:07","guid":{"rendered":"https:\/\/icc.fcen.uba.ar\/?p=3013"},"modified":"2025-09-16T12:18:02","modified_gmt":"2025-09-16T15:18:02","slug":"non-crossing-h-graphs-a-generalization-of-proper-interval-graphs-admitting-fpt-algorithms","status":"publish","type":"post","link":"https:\/\/icc.fcen.uba.ar\/en\/non-crossing-h-graphs-a-generalization-of-proper-interval-graphs-admitting-fpt-algorithms\/","title":{"rendered":"Non-crossing H-graphs: a generalization of proper interval graphs admitting FPT algorithms"},"content":{"rendered":"

Authors: Flavia Bonomo-Braberman, Nick Brettell, Andrea Munaro and Dani\u00ebl Paulusma.<\/p>\n

Abstract:
\nWeprove 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\u00e9, and Watrigant (2021) to f ind that the FO Model Checking problem is in FPT for non-crossing H-graphs when parameterized by \u2225H\u2225+\u2113, where \u2225H\u2225 is the size of H and \u2113 is the size of a formula. In particular, this implies that Independent Set is in FPT on non-crossing H-graphs when parameterized by \u2225H\u2225+k, where k is the solution size. In contrast, Independent Set for general H-graphs is W[1]-hard when parameterized by \u2225H\u2225 +k. We strengthen the latter result by proving that Independent Set is W[1]-hard even on proper H-graphs when parameterized by \u2225H\u2225 +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.<\/p>\n

More information:
\nhttps:\/\/arxiv.org\/abs\/2501.11192<\/a><\/p>\n<\/div><\/div><\/div><\/div><\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":9,"featured_media":3014,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[98],"tags":[],"class_list":["post-3013","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-papers"],"_links":{"self":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/3013","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/users\/9"}],"replies":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/comments?post=3013"}],"version-history":[{"count":2,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/3013\/revisions"}],"predecessor-version":[{"id":3022,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/posts\/3013\/revisions\/3022"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media\/3014"}],"wp:attachment":[{"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/media?parent=3013"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/categories?post=3013"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/icc.fcen.uba.ar\/en\/wp-json\/wp\/v2\/tags?post=3013"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}