- This event has passed.
Hugo Jacob, On the parameterized complexity of computing tree-partitions
Wednesday, November 9, 2022 @ 4:30 PM - 5:30 PM KST
Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender, Cornelissen, and van der Wegen, we consider the parameterized problem of computing a decomposition. We prove that computing an optimal tree-partition is XALP-complete, which is likely to exclude FPT algorithms. However, we prove that computing a tree-partition of approximate width is tractable using a relatively simple sketch. This is sufficient to remove the requirement of having a given tree-partition for FPT algorithms. Our simple sketch can be adapted for several regimes within polynomial time and FPT time. Furthermore, we adapt some simple structural results about the tree-partition-width of subdivisions, and use them to compare tree-cut width and tree-partition-width.
Based on joint work with Hans Bodlaender and Carla Groenland.