Loading [MathJax]/jax/output/HTML-CSS/jax.js

Hans L. Bodlaender ; Carla Groenland ; Hugo Jacob - On the parameterized complexity of computing tree-partitions

dmtcs:12540 - Discrete Mathematics & Theoretical Computer Science, February 16, 2025, vol. 26:3 - https://doi.org/10.46298/dmtcs.12540
On the parameterized complexity of computing tree-partitionsArticle

Authors: Hans L. Bodlaender ; Carla Groenland ; Hugo Jacob

    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. Next, 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. Finally, for the related parameter weighted tree-partition-width, we give a similar approximation algorithm (with ratio now O(k15)) and show XALP-completeness for the special case where vertices and edges have weight 1.


    Volume: vol. 26:3
    Section: Discrete Algorithms
    Published on: February 16, 2025
    Accepted on: July 29, 2024
    Submitted on: November 12, 2023
    Keywords: Computer Science - Discrete Mathematics

    Consultation statistics

    This page has been seen 98 times.
    This article's PDF has been downloaded 78 times.