Quasipolynomial multicut-mimicking networks and kernelization of multiway cut problems

Magnus Wahlström

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 o…