Loading Events

« All Events

  • This event has passed.
:

Tuukka Korhonen, Fast FPT-Approximation of Branchwidth

November 25 Thursday @ 4:30 PM - 5:30 PM KST

Zoom ID: 934 3222 0374 (ibsdimag)

Speaker

Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations could decrease the width of a branch decomposition or that the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework.

  • An algorithm that for a given n-vertex graph G and integer k in time $2^{2^{O(k)}} n^2$ either constructs a rank decomposition of G of width at most 2k or concludes that the rankwidth of G is more than $k$. It also yields a $(2^{2k+1}−1)$-approximation algorithm for cliquewidth within the same time complexity, which in turn, improves to $f(k) n^2$ the running times of various algorithms on graphs of cliquewidth $k$. Breaking the “cubic barrier” for rankwidth and cliquewidth was an open problem in the area.
  • An algorithm that for a given n-vertex graph G and integer k in time $2^{O(k)} n$ either constructs a branch decomposition of G of width at most $2k$ or concludes that the branchwidth of G is more than $k$. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].

This is joint work with Fedor Fomin.

Details

Date:
November 25 Thursday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Zoom ID: 934 3222 0374 (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.