BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20200101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20210105T163000
DTEND;TZID=Asia/Seoul:20210105T173000
DTSTAMP:20260419T170645
CREATED:20201126T024545Z
LAST-MODIFIED:20240707T082022Z
UID:3313-1609864200-1609867800@dimag.ibs.re.kr
SUMMARY:O-joung Kwon (권오정)\, Directed tangles and applications
DESCRIPTION: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$. \nBy 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$. \nWe 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]. \nSecond\, 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. \nThis is joint work with Archontia C. Giannopoulou\, Ken-ichi Kawarabayashi\, Stephan Kreutzer\, and Qiqin Xie.
URL:https://dimag.ibs.re.kr/event/2021-01-05/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR