Improving the Integrality Gap for Multiway Cut

In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for is APX-hard. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrák [12] while the best known inapproximability result due to Angelidakis, Makarychev and Manurangsi [1] rules out efficient algorithms to achieve an approximation factor that is less than 1.2. In this work, we improve on the lower bound to by constructing an integrality gap instance for the CKR relaxation. A technical challenge in improving the gap has been the lack of geometric tools to understand higher-dimensional simplices. Our instance is a non-trivial 3-dimensional instance that overcomes this technical challenge. We analyze the gap of the instance by viewing it as a convex combination of 2-dimensional instances and a uniform 3-dimensional instance. We believe that this technique could be exploited further to construct instances with larger integrality gap. One of the ingredients of our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondrák [11] that might be of independent combinatorial interest.