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: https://drops.dagstuhl.de/opus/volltexte/2023/18353/
Go to the corresponding LIPIcs Volume Portal


Bläsius, Thomas ; Katzmann, Maximilian ; Wilhelm, Marcus

Partitioning the Bags of a Tree Decomposition into Cliques

pdf-format:
LIPIcs-SEA-2023-3.pdf (1 MB)


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}
}

Keywords: treewidth, weighted treewidth, algorithm engineering, cliques, clustering, complex networks
Collection: 21st International Symposium on Experimental Algorithms (SEA 2023)
Issue Date: 2023
Date of publication: 19.07.2023
Supplementary Material: Software (Source Code): https://github.com/marcwil/cptw_code archived at: https://archive.softwareheritage.org/swh:1:dir:d611a7236b805d6eb409147b28b514f9132f96c1
Software (Source Code: Archive, Docker Image): https://doi.org/10.5281/zenodo.7816985


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI