Loading Events

« All Events

  • This event has passed.
:

Hugo Jacob, On the parameterized complexity of computing tree-partitions

November 9 Wednesday @ 4:30 PM - 5:30 PM KST

Zoom ID: 869 4632 6610 (ibsdimag)

Speaker

Hugo Jacob
ENS Paris-Saclay

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.

Details

Date:
November 9 Wednesday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Zoom ID: 869 4632 6610 (ibsdimag)

Organizer

O-joung Kwon (권오정)
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.