ECCC-Report TR09-125https://eccc.weizmann.ac.il/report/2009/125Comments and Revisions published for TR09-125en-usTue, 24 Nov 2009 18:08:41 +0200
Paper TR09-125
| Connections Between Unique Games and Multicut |
Nisheeth Vishnoi,
David Steurer
https://eccc.weizmann.ac.il/report/2009/125 In this paper we demonstrate a close connection between UniqueGames 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, UniqueGames 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 UniqueGames.
%
Specifically, we can adapt most known algorithms for UniqueGames 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 UniqueGames.
In the other direction, we show that MultiCut is not easier than
UniqueGames ($\Gamma$-max-$2$-lin to be precise).
We exhibit a reduction from UniqueGames 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
UniqueGames 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 $\ell_1$ metrics.
Tue, 24 Nov 2009 18:08:41 +0200https://eccc.weizmann.ac.il/report/2009/125