기초과학연구원 이산수학그룹
On November 9, 2022, Hugo Jacob from the ENS Paris-Saclay gave an online talk at the Virtual Discrete Math Colloquium on the parameterized algorithm to approximate the tree-partition-width of graphs at the Virtual Discrete Math Colloquium. The title of his talk was “On the parameterized complexity of computing tree-partitions“.
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.