Loading Events

« All Events

  • This event has passed.
:

O-joung Kwon (권오정), Directed tangles and applications

Tuesday, January 5, 2021 @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

Speaker

O-joung Kwon (권오정)
Incheon National University & IBS Discrete Mathematics Group
http://ojkwon.com

The canonical tree-decomposition theorem, proved by Robertson and Seymour in their seminal graph minors series, turns out to be an extremely valuable tool in structural and algorithmic graph theory. In this paper, we prove the analogous result for digraphs, the directed tangle tree-decomposition theorem. More precisely, we introduce directed tangles and provide a directed tree-decomposition of digraphs $G$ that distinguishes all maximal directed tangles in $G$. Furthermore, for any integer $k$, we construct a directed tree-decomposition that distinguishes all directed tangles of order $k$, for any integer $k$.

By relaxing the bound slightly, we can make the previous result algorithmic: for fixed $k$, we design a polynomial-time algorithm that finds a directed tree-decomposition distinguishing all directed tangles of order $3k$ separated by some separation of order less than $k$.

We provide two direct applications of this tangle tree-decomposition theorem. First, we show that the family of directed odd cycles has the half-integral Erdős-Pósa property, that is, there is a function $f:\mathbb{N}\rightarrow \mathbb{R}$ such that for every digraph $G$ and every integer $k$, either $G$ contains a family of $k$ directed odd cycles where every vertex of $G$ is contained at most two cycles, or a vertex subset of size at most $f(k)$ hitting all directed odd cycles. This extends the half-integral Erdős-Pósa property for undirected odd cycles, shown by Reed [Mangoes and blueberries. Combinatorica 1999].

Second, for every fixed $k$ we show that there is a polynomial-time algorithm which, on input $G$, and source and sink vertices $(s_1, t_1), \dots, (s_k, t_k)$, either finds a family of paths $P_1, \dots, P_k$ such that each $P_i$ links $s_i$ to $t_i$ and every vertex of $G$ is contained in at most two paths, or determines that there is no set of pairwise vertex-disjoint paths each connecting $s_i$  to $t_i$. This result improves previous results (with “two” replaced by “three”), and given known hardness results, our result is best possible in a sense that we cannot hope for fixed parameter tractability or fully vertex-disjoint directed paths.

This is joint work with Archontia C. Giannopoulou, Ken-ichi Kawarabayashi, Stephan Kreutzer, and Qiqin Xie.

Details

Date:
Tuesday, January 5, 2021
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:
,

Venue

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum (엄상일)
View Organizer Website
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.