On explique, dans la généralité étudiée par Raghavendra, la réduction de UNIQUE VERTEX COVER a un problème de satisfaction de contraintes, en utilisant les tests de dictature décrits par Eric.
- Groupe de lecture de complexité algorithmique
Optimalité (conditionnellement à UGC) des relaxations SDP des problèmes de satisfaction de contraintes, d’après P. Raghavendra, II
- Cet évènement est passé