Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorKim, Eun Jung
dc.contributor.authorKratsch, Stefan
dc.contributor.authorPilipczuk, Marcin
dc.contributor.authorWahlström, Magnus
dc.date.accessioned2021-11-16T11:49:19Z
dc.date.available2021-11-16T11:49:19Z
dc.date.issued2021
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/22215
dc.descriptionVirtual Conferenceen
dc.language.isoenen
dc.subjecthard cut problemsen
dc.subject.ddc005en
dc.titleSolving hard cut problems via flow-augmentationen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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 Min-Cut. 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 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.en
dc.identifier.citationpages149-168en
dc.relation.ispartoftitleProceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithmsen
dc.relation.ispartofeditorMarx, Dániel
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatiken
dc.relation.ispartofpages3041en
dc.relation.ispartofurl10.1137/1.9781611976465en
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.ispartofisbn978-1-61197-646-5en
dc.relation.conftitleACM-SIAM Symposium on Discrete Algorithms, SODA 2021en
dc.relation.confdate2021-01
dc.relation.forthcomingnonen
dc.identifier.doi10.1137/1.9781611976465.11en
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2021-11-16T11:45:25Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record