License:
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.63
URN: urn:nbn:de:0030-drops-156592
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15659/
Eiben, Eduard ;
Ganian, Robert ;
Hamm, Thekla ;
Jaffke, Lars ;
Kwon, O-joung
A Unifying Framework for Characterizing and Computing Width Measures
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.
BibTeX - Entry
@InProceedings{eiben_et_al:LIPIcs.ITCS.2022.63,
author = {Eiben, Eduard and Ganian, Robert and Hamm, Thekla and Jaffke, Lars and Kwon, O-joung},
title = {{A Unifying Framework for Characterizing and Computing Width Measures}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {63:1--63:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15659},
URN = {urn:nbn:de:0030-drops-156592},
doi = {10.4230/LIPIcs.ITCS.2022.63},
annote = {Keywords: branchwidth, parameterized algorithms, mim-width, treewidth, clique-width}
}
Keywords: |
|
branchwidth, parameterized algorithms, mim-width, treewidth, clique-width |
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
25.01.2022 |