Sur la Conjecture des Jeux Uniques

Stéphane Pérennes (1)

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications

La plupart des problèmes d'optimisation combinatoire sont NP-difficiles, c'est-à-dire qu'ils ne peuvent être résolus en temps polynomial que si les classes P et NP sont identiques. Pour ces problèmes on peut espérer soit trouver des algorithmes d'approximation, soit prouver qu'ils ne peuvent pas être approximés de manière efficace. En 2002 S. Khot formula la Conjecture des Jeux Uniques (UGC), qui géneralise le théorème PCP et impliquerait d'importants résultats d'innaproximabilité pour plusieurs problèmes d'optimisation combinatoire (par exemple Max Cut ou Vertex Cover). Intuitivement, la UGC dit que, pour une certaine classe de jeux, appelés uniques, il est NP-dur de décider si l'on peut trouver une solution proche de l'optimale, ou si toutes les solutions sont loin de l'optimale. Cette conjecture est devenue un problème ouvert des plus importants dans la théorie de la complexité et de l'approximation. Dans cet article nous étudions un problème très relié à la UGC: Max-E$2$-Lin2 dans les graphes bipartis. Dans Max-E$2$-Lin2 on a un graphe $G$ ayant deux type d'arêtes, requérant soit la même soit différente couleur pour ses extrémités. Le but est de 2-colorer les sommets de $G$ en maximisant le nombre d'arêtes satisfaites. Nous prouvons que ce problème est APX-complet dans les graphes bipartis et, en utilisant le Théorème de Répétition Paralèlle, nous discutons les conséquences de ce résultat dans le cadre des jeux uniques et la UGC.

Domaines: Combinatoire [math.CO]

Stéphane Pérennes. Sur la Conjecture des Jeux Uniques. [Research Report] RR-6691, INRIA. 2008. ⟨inria-00331248⟩