Khot's Unique Games Conjecture in transversal-polynomial form
Khot's Unique Games Conjecture in transversal-polynomial form
Let be an -fold cover of a graph , where is the transversal polynomial and is the maximum number of edges satisfied by a labelling of . For all , there exists such that, given an -fold cover of a graph , it is NP-hard to distinguish between the following two cases:
- ;
- .
This is the Unique Games Conjecture, a central complexity-theoretic hypothesis whose truth would imply optimality results for approximation algorithms for several NP-hard problems. In this formulation, the degree of the transversal polynomial records the maximum number of edges satisfied by a labelling; the source provides no resolution of the conjecture.
Sources & referencesView supporting material
Primary source
Chris Godsil, Krystal Guo and Gordon Royle, “Transversal polynomial of r-fold covers”, arXiv:1910.05478 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.