2020/02/20 by Magnus Wahlström, Wahlström, Magnus
Engineering · #Advanced Numerical Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Manufacturing Process and Optimization #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2002.08825
openalex publication_date 2020/02/20 · openalex created_date 2020/07/02 · openalex updated_date 2026/07/28
We show the existence of an exact mimicking network of kO(\log k) edges\nfor minimum multicuts over a set of terminals in an undirected graph, where k\nis the total capacity of the terminals, as well as a method for computing a\nmimicking network of quasipolynomial size in polynomial time. As a consequence\nof the latter, several problems are shown to have quasipolynomial kernels,\nincluding Edge Multiway Cut, Group Feedback Edge Set for an arbitrary group,\nand Edge Multicut parameterized by the solution and the number of cut requests.\nThe result combines the matroid-based irrelevant edge approach used in the\nkernel for s-Multiway Cut with a recursive decomposition and sparsification\nof the graph along sparse cuts. This is the first progress on the kernelization\nof Multiway Cut problems since the kernel for s-Multiway Cut for constant\nvalue of s (Kratsch and Wahlstr "om, FOCS 2012).\n