2026-07-21T20:03:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15659 2024-03-06T10:55:52Z ddc:004 open_access

A Unifying Framework for Characterizing and Computing Width Measures Eiben, Eduard Ganian, Robert Hamm, Thekla Jaffke, Lars Kwon, O-joung branchwidth parameterized algorithms mim-width treewidth clique-width Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, no efficient algorithms for computing good decompositions were known, even under highly restrictive parameterizations. In this work we identify ℱ-branchwidth as a class of generic decompositional parameters that can capture mim-width, treewidth, clique-width as well as other measures. We show that while there is an infinite number of ℱ-branchwidth parameters, only a handful of these are asymptotically distinct. We then develop fixed-parameter and kernelization algorithms (under several structural parameterizations) that can approximate every possible ℱ-branchwidth, providing a unifying parameterized framework that can efficiently obtain near-optimal tree-decompositions, k-expressions, as well as optimal mim-width decompositions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eduard Eiben and Robert Ganian and Thekla Hamm and Lars Jaffke and O-joung Kwon 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.63 urn:nbn:de:0030-drops-156592 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.63 eng https://creativecommons.org/licenses/by/4.0/legalcode