论文标题
强大独特游戏的近似算法和硬度
Approximation Algorithms and Hardness for Strong Unique Games
论文作者
论文摘要
独特的游戏问题是算法和复杂性理论中的一个核心问题。给定一个独特的游戏实例，强烈的独特游戏问题要求找到最大的顶点子集，以使其引起的独特游戏实例完全令人满意。在本文中，我们为强大的独特游戏提供了新的算法和硬度结果。 Given an instance with label set size $k$ where a set of $(1 - ε)$-fraction of the vertices induce an instance that is completely satisfiable, our first algorithm produces a set of $1 - \widetilde{O}({k^2}) ε\sqrt{\log n}$ fraction of the vertices such that the UNIQUE GAMES induced on them is completely satisfiable.在同一设置中，我们的第二算法产生了一组$ 1- \ widetilde {o}（{k^2}）\ sqrt {ε\ log d} $（此处$ d $是该图的最大顶点的最大顶点），因此在它们上引起的独特游戏是完全满足了它们的独特游戏。结果的技术核心是图形中强大的独特游戏与小型vertex-expansion之间的新联系。对此进行补充，假设唯一的游戏猜想，我们证明，计算一组大于$ 1 -ω（\ sqrt {ε\ log k \ log d}）$的尺寸是NP -HARD。 给定无向图$ g（v，e）$奇数循环横向问题要求删除最小分数的顶点，以使其剩余的两部分上的诱导图。作为我们主要算法结果的推论，我们获得了一种算法，该算法输出了$ v \ setminus s $在$ v \ setminus s $上引起的图形的算法，而$ | s |/n \ leq o（\ sqrt { + sqrt {ε\ log d} $ dection the $ d $是$ d $是$ d $ rab fr the lar fration and lar the lar fertex $删除）。假设游戏的猜想，我们证明了匹配（不变的因素）硬度。
The UNIQUE GAMES problem is a central problem in algorithms and complexity theory. Given an instance of UNIQUE GAMES, the STRONG UNIQUE GAMES problem asks to find the largest subset of vertices, such that the UNIQUE GAMES instance induced on them is completely satisfiable. In this paper, we give new algorithmic and hardness results for STRONG UNIQUE GAMES. Given an instance with label set size $k$ where a set of $(1 - ε)$-fraction of the vertices induce an instance that is completely satisfiable, our first algorithm produces a set of $1 - \widetilde{O}({k^2}) ε\sqrt{\log n}$ fraction of the vertices such that the UNIQUE GAMES induced on them is completely satisfiable. In the same setting, our second algorithm produces a set of $1 - \widetilde{O}({k^2}) \sqrt{ε\log d}$ (here $d$ is the largest vertex degree of the graph) fraction of the vertices such that the UNIQUE GAMES induced on them is completely satisfiable. The technical core of our results is a new connection between STRONG UNIQUE GAMES and Small-Set-Vertex-Expansion in graphs. Complementing this, assuming the Unique Games Conjecture, we prove that it is NP-hard to compute a set of size larger than $1 - Ω( \sqrt{ε\log k \log d})$ for which all the constraints induced on this set are satisfied. Given an undirected graph $G(V,E)$ the ODD CYCLE TRANSVERSAL problem asks to delete the least fraction of vertices to make the induced graph on the remaining vertices bipartite. As a corollary to our main algorithmic results, we obtain an algorithm that outputs a set $S$ such the graph induced on $V \setminus S$ is bipartite, and $|S|/n \leq O(\sqrt{ε\log d})$ (here $d$ is the largest vertex degree and $ε$ is the optimal fraction of vertices that need to be deleted). Assuming the Unique Games Conjecture, we prove a matching (up to constant factors) hardness.
