Skip to main navigation Skip to search Skip to main content

On the Parameterized Complexity of Computing Tree-Partitions

  • Hans L. Bodlaender*
  • , Carla Groenland
  • , Hugo Jacob
  • *Corresponding author for this work

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

Abstract

We study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree. On one hand, we can obtain approximations of the tree-partition-width efficiently: we show that there is an algorithm that, given an n-vertex graph G and an integer k, constructs a tree-partition of width O(k7) for G or reports that G has tree-partition width more than k, in time kO(1)n2. We can improve slightly on the approximation factor by sacrificing the dependence on k, or on n. On the other hand, we show the problem of computing tree-partition-width exactly is XALP-complete, which implies that it is W[t]-hard for all t. We deduce XALP-completeness of the problem of computing the domino treewidth. Finally, we adapt some known results on the parameter tree-partition-width and the topological minor relation, and use them to compare tree-partition-width to tree-cut width.

Original languageEnglish
Title of host publication17th International Symposium on Parameterized and Exact Computation, IPEC 2022
EditorsHolger Dell, Jesper Nederlof
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772600
DOIs
Publication statusPublished - 2022
Externally publishedYes
Event17th International Symposium on Parameterized and Exact Computation, IPEC 2022 - Potsdam, Germany
Duration: 7 Sept 2022 → 9 Sept 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume249
ISSN (Print)1868-8969

Conference

Conference17th International Symposium on Parameterized and Exact Computation, IPEC 2022
Country/TerritoryGermany
CityPotsdam
Period7/09/22 → 9/09/22

Keywords

  • Approximation Algorithms
  • Domino Treewidth
  • Parameterized algorithms
  • Parameterized Complexity
  • Tree partitions
  • tree-partition-width
  • Treewidth

Fingerprint

Dive into the research topics of 'On the Parameterized Complexity of Computing Tree-Partitions'. Together they form a unique fingerprint.

Cite this