Quasi-polynomial-sized vertex multicut-mimicking networks and kernelization for Vertex Multiway CutResearch Paper
Many graph-separation problems only care about how a small set of terminals can be cut apart, not about the rest of the graph. A mimicking network replaces a large graph by a small one that answers every such cut question exactly, and it is the standard way to obtain polynomial kernels (provably small equivalent instances) for parameterized cut problems…