KIT | KIT-Bibliothek | Impressum | Datenschutz

Partitioning the Bags of a Tree Decomposition into Cliques

Bläsius, Thomas ORCID iD icon 1; Katzmann, Maximilian 2; Wilhelm, Marcus 2
1 Institut für Theoretische Informatik (ITI), Karlsruher Institut für Technologie (KIT)
2 Karlsruher Institut für Technologie (KIT)

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.


Verlagsausgabe §
DOI: 10.5445/IR/1000162490
Veröffentlicht am 24.10.2024
Originalveröffentlichung
DOI: 10.4230/lipics.sea.2023.3
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2023
Sprache Englisch
Identifikator ISBN: 978-3-9597727-9-2
ISSN: 1868-8969
KITopen-ID: 1000162490
Erschienen in 21st International Symposium on Experimental Algorithms (SEA 2023), 24th-26th July 2023, Barcelona
Veranstaltung 21st International Symposium on Experimental Algorithms (SEA 2023 2023), Barcelona, Spanien, 24.07.2023 – 26.07.2023
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik (LZI)
Seiten 3.1-3.19
Serie Leibniz International Proceedings in Informatics ; 265
Vorab online veröffentlicht am 19.07.2023
Schlagwörter treewidth, weighted treewidth, algorithm engineering, cliques, clustering, complex networks, Mathematics of computing → Graph algorithms, Theory of computation → Graph algorithms analysis
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page