Solving hard cut problems via flowaugmentation
Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2021), Solving hard cut problems via flowaugmentation, in Marx, Dániel, Proceedings of the 2021 ACMSIAM Symposium on Discrete Algorithms, Schloss DagstuhlLeibnizZentrum fuer Informatik, p. 149168. 10.1137/1.9781611976465.11
View/Open
Type
Communication / ConférenceDate
2021Conference title
ACMSIAM Symposium on Discrete Algorithms, SODA 2021Conference date
202101Book title
Proceedings of the 2021 ACMSIAM Symposium on Discrete AlgorithmsBook author
Marx, DánielPublisher
Schloss DagstuhlLeibnizZentrum fuer Informatik
ISBN
9781611976465
Number of pages
3041Pages
149168
Publication identifier
Metadata
Show full item recordAuthor(s)
Kim, Eun JungLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Kratsch, Stefan
Pilipczuk, Marcin
Wahlström, Magnus
Abstract (EN)
We present a new technique for designing FPT 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. More precisely, we consider problems where an (unknown) solution is a set Z⊆E(G) of size at most k such that (1) in G−Z, s and t are in distinct connected components, (2) every edge of Z connects two distinct connected components of G−Z, and (3) if we define the set Zs,t⊆Z as these edges e∈Z for which there exists an (s,t)path Pe with E(Pe)∩Z={e}, then Zs,t separates s from t. We prove that in this scenario one can in randomized time kO(1)(V(G)+E(G)) add a number of edges to the graph so that with 2−O(klogk) probability no added edge connects two components of G−Z and Zs,t becomes a minimum cut between s and t. We apply our method to obtain a randomized FPT algorithm for a notorious "hard nut" graph cut problem we call Coupled MinCut. This problem emerges out of the study of FPT algorithms for Min CSP problems, and was unamenable to other techniques for parameterized algorithms in graph cut problems, such as Randomized Contractions, Treewidth Reduction or Shadow Removal. To demonstrate the power of the approach, we consider more generally Min SAT(Γ), parameterized by the solution cost. We 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 mincut 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 MinCut.Subjects / Keywords
hard cut problemsRelated items
Showing items related by title and author.

Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2023) Communication / Conférence

Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2023) Communication / Conférence

Kim, Eun Jung; Kratsch, Stefan; Pilipczuk, Marcin; Wahlström, Magnus (2022) Communication / Conférence

Kim, Eun Jung; Milanic, Martin; Monnot, Jérôme; Picouleau, Christophe (2022) Article accepté pour publication ou publié

Kim, Eun Jung; Ordyniak, Sebastian; Szeider, Stefan (2014) Communication / Conférence