BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20210101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20220809T163000
DTEND;TZID=Asia/Seoul:20220809T173000
DTSTAMP:20260420T052359
CREATED:20220808T073000Z
LAST-MODIFIED:20240707T075550Z
UID:5821-1660062600-1660066200@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, Directed flow-augmentation
DESCRIPTION:We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that\, given a directed graph G\, two integers $s\,t\in V(G)$\, and an integer $k$\, adds (randomly) to $G$ a number of arcs such that for every minimal st-cut $Z$ in $G$ of size at most $k$\, with probability $2^{−\operatorname{poly}(k)}$ the set $Z$ becomes a minimum $st$-cut in the resulting graph.\nThe directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set\, whose parameterized complexity status was repeatedly posed as open problems:\n(1) Chain SAT\, defined by Chitnis\, Egri\, and Marx [ESA’13\, Algorithmica’17]\,\n(2) a number of weighted variants of classic directed cut problems\, such as Weighted st-Cut\, Weighted Directed Feedback Vertex Set\, or Weighted Almost 2-SAT.\nBy proving that Chain SAT is FPT\, we confirm a conjecture of Chitnis\, Egri\, and Marx that\, for any graph H\, if the List H-Coloring problem is polynomial-time solvable\, then the corresponding vertex-deletion problem is fixed-parameter tractable. \nJoint work with Stefan Kratsch\, Marcin Pilipczuk\, Magnus Wahlström.
URL:https://dimag.ibs.re.kr/event/2022-08-09/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR