2026-07-31T03:26:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17363 2024-03-06T10:59:33Z ddc:004 open_access

On the Parameterized Complexity of Computing Tree-Partitions Bodlaender, Hans L. Groenland, Carla Jacob, Hugo Parameterized algorithms Tree partitions tree-partition-width Treewidth Domino Treewidth Approximation Algorithms Parameterized Complexity 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(k⁷) for G or reports that G has tree-partition width more than k, in time k^O(1) n². 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans L. Bodlaender and Carla Groenland and Hugo Jacob 2022 Is Part Of LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2022.7 urn:nbn:de:0030-drops-173633 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.7 eng https://creativecommons.org/licenses/by/4.0/legalcode