A Unifying Framework for Characterizing and Computing Width Measures

Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, O. Joung Kwon

Research output: Contribution to conferencePaperpeer-review

Abstract

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.
Original languageEnglish
Pages63:1--63:23
Number of pages23
DOIs
Publication statusPublished - 25 Jan 2022
Event13th Innovations in Theoretical Computer Science Conference - Online
Duration: 31 Jan 20223 Feb 2022
http://itcs-conf.org/itcs22/itcs22-cfp.html

Conference

Conference13th Innovations in Theoretical Computer Science Conference
Abbreviated titleITCS 2022
Period31/01/223/02/22
Internet address

Cite this