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:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20200728T163000
DTEND;TZID=Asia/Seoul:20200728T173000
DTSTAMP:20260420T020416
CREATED:20200708T123952Z
LAST-MODIFIED:20240707T083742Z
UID:2624-1595953800-1595957400@dimag.ibs.re.kr
SUMMARY:Eun Jung Kim (김은정)\, Solving hard cut problems via flow-augmentation
DESCRIPTION:We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs\, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) $(s\, t)$-cut of cardinality at most $k$ in an undirected graph $G$ with designated terminals s and t. \nMore precisely\, we consider problems where an (unknown) solution is a set $Z \subseteq E(G)$ of size at most $k$ such that \n\nin $G−Z$\, $s$ and $t$ are indistinct connected components\,\nevery edge of $Z$ connects two distinct connected components of $G − Z$\, and\nif we define the set $Z_{s\,t}\subseteq Z$ as these edges $e \in Z$ for which there exists an (s\, t)-path P_e with $E(P_e) ∩ Z = \{e\}$\, then $Z_{s\,t}$ separates s from t.\n\nWe prove that in the above scenario one can in randomized time $k^O(1)(|V (G)| + |E(G)|)$ add a number of edges to the graph so that with $2^{O(k \log k)}$ probability no added edge connects two components of $G − Z$ and $Z_{s\,t}$ becomes a minimum cut between $s$ and $t$. \nThis additional property becomes a handy lever in applications. For example\, consider the question of an $(s\, t)$-cut of cardinality at most k and of minimum possible weight (assuming edge weights in $G$). While the problem is NP-hard in general\, it easily reduces to the maximum flow / minimum cut problem if we additionally assume that k is the minimum possible cardinality an $(s\, t)$-cut in G. Hence\, we immediately obtain that the aforementioned problem admits an $2^{O(k \log k)}n^O(1)$-time randomized fixed-parameter algorithm. \nWe apply our method to obtain a randomized fixed-parameter algorithm for a notorious “hard nut” graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems (see below)\, and was unamenable to other techniques for parameterized algorithms in graph cut problems\, such as Randomized Contractions\, Treewidth Reduction or Shadow Removal. \nIn fact\, we go one step further. To demonstrate the power of the approach\, we consider more generally the Boolean Min CSP(Γ)-problems\, a.k.a. Min SAT(Γ)\, parameterized by the solution cost. This is a framework of optimization problems that includes problems such as Almost 2-SAT and the notorious l-Chain SAT problem. We are able to show that every problem Min SAT(Γ) is either (1) FPT\, (2) W[1]-hard\, or (3) able to express the soft constraint (u → v)\, and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate\, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut. In other words\, flow-augmentation is powerful enough to let us solve every fixed-parameter tractable problem in the class\, except those that explicitly encompass directed graph cuts. \nThis is a joint work with Stefan Kratsch\, Marcin Pilipczuk and Magnus Wahlström.
URL:https://dimag.ibs.re.kr/event/2020-07-28/
LOCATION:Room B232\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR