2026-07-24T12:54:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24484 2025-12-16T13:59:47Z ddc:004 open_access

On Algorithmic Applications of ℱ-Branchwidth Bergougnoux, Benjamin Hamm, Thekla Jaffke, Lars Lima, Paloma T. Graph width parameters parameterized complexity F-branchwidth tree-width clique-width rank-width mim-width FO model checking DN logic Independent Set ETH F-branchwidth is a framework for width measures of graphs, recently introduced by Eiben et al. [ITCS 2022], that captures tree-width, co-tree-width, clique-width, and mim-width, and several of their generalizations and interpolations. In this work, we search for algorithmic applications of F-branchwidth measures that do not have an equivalent counterpart in the literature so far. Our first contribution is a minimal set of eleven F-branchwidth measures such that each of the infinitely many F-branchwidth measures is equivalent to one of the eleven. We observe that for the FO Model Checking problem, each F-branchwidth is either equivalent to clique-width (and therefore has an FPT-algorithm by formula length plus the width) or the problem remains as hard as on general graphs even on graphs of constant width. Next, we study the number of equivalence classes of the neighborhood equivalence in a decomposition, which upper bounds the run time of the model checking algorithm for ACDN logic recently introduced by Bergougnoux et al. [SODA 2023]. We give structural lower bounds that show that for each F-branchwidth, an efficient model checking algorithm was already known or cannot be obtained via this method. Lastly, we classify the complexity of Independent Set parameterized by any F-branchwidth except for one open case. Also here, our contributions are lower bounds. In this context, we also prove that Independent Set on graphs of mim-width w cannot be solved in time n^o(w) unless the Exponential Time Hypothesis fails, answering an open question in the literature. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Bergougnoux and Thekla Hamm and Lars Jaffke and Paloma T. Lima 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.16 urn:nbn:de:0030-drops-244849 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.16 eng https://creativecommons.org/licenses/by/4.0/legalcode