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:20220101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20230221T163000
DTEND;TZID=Asia/Seoul:20230221T173000
DTSTAMP:20260416T054151
CREATED:20230110T061742Z
LAST-MODIFIED:20240705T170041Z
UID:6636-1676997000-1677000600@dimag.ibs.re.kr
SUMMARY:Meike Hatzel\, Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation
DESCRIPTION:We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem\, given a directed graph $G$\, pairs of vertices (called terminals) $(s_1\,t_1)$\, $(s_2\,t_2)$\, and $(s_3\,t_3)$\, and an integer $k$\, asks to find a set of at most $k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths\, all $s_2t_2$-paths\, and all $s_3t_3$-paths. The parameterized complexity of this case has been open since Chitnis\, Cygan\, Hajiaghayi\, and Marx proved fixed-parameter tractability of the 2-terminal-pairs case at SODA 2012\, and Pilipczuk and Wahlström proved the W[1]-hardness of the 4-terminal-pairs case at SODA 2016. \nOn the technical side\, we use two recent developments in parameterized algorithms. Using the technique of directed flow-augmentation [Kim\, Kratsch\, Pilipczuk\, Wahlström\, STOC 2022] we cast the problem as a CSP problem with few variables and constraints over a large ordered domain. We observe that this problem can be in turn encoded as an FO model-checking task over a structure consisting of a few 0-1 matrices. We look at this problem through the lenses of twin-width\, a recently introduced structural parameter [Bonnet\, Kim\, Thomassé\, Watrigant\, FOCS 2020]: By a recent characterization [Bonnet\, Giocanti\, Ossona de Mendez\, Simon\, Thomassé\, Toruńczyk\, STOC 2022] the said FO model-checking task can be done in FPT time if the said matrices have bounded grid rank. To complete the proof\, we show an irrelevant vertex rule: If any of the matrices in the said encoding has a large grid minor\, a vertex corresponding to the “middle” box in the grid minor can be proclaimed irrelevant — not contained in the sought solution — and thus reduced.
URL:https://dimag.ibs.re.kr/event/2023-02-21/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR