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.SEA.2023.3
URN: urn:nbn:de:0030-drops-183533
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18353/
Bläsius, Thomas ;
Katzmann, Maximilian ;
Wilhelm, Marcus
Partitioning the Bags of a Tree Decomposition into Cliques
Abstract
We consider a variant of treewidth that we call clique-partitioned treewidth in which each bag is partitioned into cliques. This is motivated by the recent development of FPT-algorithms based on similar parameters for various problems. With this paper, we take a first step towards computing clique-partitioned tree decompositions.
Our focus lies on the subproblem of computing clique partitions, i.e., for each bag of a given tree decomposition, we compute an optimal partition of the induced subgraph into cliques. The goal here is to minimize the product of the clique sizes (plus 1). We show that this problem is NP-hard. We also describe four heuristic approaches as well as an exact branch-and-bound algorithm. Our evaluation shows that the branch-and-bound solver is sufficiently efficient to serve as a good baseline. Moreover, our heuristics yield solutions close to the optimum. As a bonus, our algorithms allow us to compute first upper bounds for the clique-partitioned treewidth of real-world networks. A comparison to traditional treewidth indicates that clique-partitioned treewidth is a promising parameter for graphs with high clustering.
BibTeX - Entry
@InProceedings{blasius_et_al:LIPIcs.SEA.2023.3,
author = {Bl\"{a}sius, Thomas and Katzmann, Maximilian and Wilhelm, Marcus},
title = {{Partitioning the Bags of a Tree Decomposition into Cliques}},
booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)},
pages = {3:1--3:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-279-2},
ISSN = {1868-8969},
year = {2023},
volume = {265},
editor = {Georgiadis, Loukas},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18353},
URN = {urn:nbn:de:0030-drops-183533},
doi = {10.4230/LIPIcs.SEA.2023.3},
annote = {Keywords: treewidth, weighted treewidth, algorithm engineering, cliques, clustering, complex networks}
}
