We demonstrate a close connection between Unique Games and Multicut. In Multicut, one is given a network graph and a demand graph on the same vertex set and the goal is to remove as few edges from the network graph as possible such that every two vertices connected by a demand edge are separated. On the other hand, Unique Games is a certain family of constraint satisfaction problems.
In one direction, we show that, at least with respect to current algorithmic techniques, Multicut is not harder than Unique Games. Specifically, we can adapt most known algorithms for Unique Games to work for Multicut and obtain new approximation guarantees for Multicut that depend on the maximum degree of the demand graph. This degree plays the same role as the alphabet size plays in approximation guarantees for Unique Games.
In the other direction, we show that Multicut is not easier than Unique Games: We exhibit a reduction from Unique Games to Multicut so that the fraction of edges in the optimal multicut is up to a factor of 2 equal to the fraction of constraint violated by the optimal assignment for the Unique Games instance. In contrast to the vast majority of Unique Games reductions whose analysis relies on Fourier analysis and isoperimetric inequalities, this reduction is simple and the analysis is elementary. Further, the maximum degree of the demand graph in the instance produced by the reduction is less than the size of the alphabet size in the Unique Games instance.
Our results rely on a simple but previously unknown characterization of Multicut in terms of L_1 metrics (joint work with David Steurer).
