Multicut Lower Bounds via Network Coding
The authors introduce a new technique to certify lower bounds on the multi-cut size using network coding. In directed networks the network coding rate is not a lower bound on the multi-cut, but they identify a class of networks on which the rate is equal to the size of the minimum multi-cut and show this class is closed under the strong graph product. they then show that the famous construction of Saks et al. that gives a (k) gap between the multi-cut and the multi-commodity flow rate is contained in this class. This allows the user to apply their result to strengthen their multi-cut lower bound, determine the exact value of the minimum multi-cut, and give an optimal network coding solution with rate matching the multi-cut.