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 \Theta(\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\"om, FOCS 2012).
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 , as well as a method for computing a mimicking network of quasipolynomial size in polynomial time. As a consequence of the latter, several problems are shown to have quasipolynomial kernels, including Edge Multiway Cut, Group Feedback Edge Set for an arbitrary group, and Edge Multicut parameterized by the solution and the number of cut requests. The result combines 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. 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\"om, FOCS 2012).
R
. Furthermore, if Small Set Expansion has an approximation algorithm with a ratio slightly better than \Theta(\log n), then
, as well as a method for computing
D
can be computed
R
would
are shown to
D
0-Extension for integer-weighted metrics,
R
works via a combination of
combines
D
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