A Unifying Framework for Characterizing and Computing Width Measures. / Eiben, Eduard; Ganian, Robert; Hamm, Thekla; Jaffke, Lars; Kwon, O. Joung.

2022. 63:1--63:23 Paper presented at 13th Innovations in Theoretical Computer Science Conference.

Research output: Contribution to conferencePaperpeer-review

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

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
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 45563037