2026-07-26T04:50:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12508 2024-03-06T10:50:19Z ddc:004 open_access

On Quasipolynomial Multicut-Mimicking Networks and Kernelization of Multiway Cut Problems Wahlström, Magnus Multiway Cut Kernelization Small Set Expansion Mimicking Networks We show the existence of an exact mimicking network of k^O(log k) edges for minimum multicuts over a set of terminals in an undirected graph, where k is the total capacity of the terminals. Furthermore, if Small Set Expansion has an approximation algorithm with a ratio slightly better than Θ(log n), then a mimicking network of quasipolynomial size can be computed in polynomial time. As a consequence of the latter, several problems would have quasipolynomial kernels, including Edge Multiway Cut, Group Feedback Edge Set for an arbitrary group, 0-Extension for integer-weighted metrics, and Edge Multicut parameterized by the solution and the number of cut requests. The result works via a combination of the matroid-based irrelevant edge approach used in the kernel for s-Multiway Cut with a recursive decomposition and sparsification of the graph along sparse cuts. The main technical contribution is a matroid-based marking procedure that we can show will mark all non-irrelevant edges, assuming that the graph is sufficiently densely connected. The only part of the result that is not currently constructive and polynomial-time computable is the detection of such sparse cuts. This is the first progress on the kernelization of Multiway Cut problems since the kernel for s-Multiway Cut for constant value of s (Kratsch and Wahlström, FOCS 2012). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Magnus Wahlström 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.101 urn:nbn:de:0030-drops-125082 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.101 eng https://creativecommons.org/licenses/by/3.0/legalcode