Hugo Jacob gave an online talk on the parameterized algorithm to approximate the tree-partition-width of graphs at the Virtual Discrete Math Colloquium

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“.

Hugo Jacob, 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.

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.