Graphe de Frankl-Rödl

En théorie des graphes et en théorie de complexité des calculs, un graphe de Frankl-Rödl est un graphe dont les sommets sont les sommets d'un hypercube, et les arêtes joignent des sommets qui sont à une même distance paire fixe les uns des autres. Les graphes de ce type sont paramétrés par la dimension de l'hypercube et par la distance entre les sommets déclarés adjacents.

Le graphe de Frankl-Rödl est formé des sommets d'un cube tridimensionnel et des arêtes entre des sommets à distance deux.

Les graphes de Frankl-Rödl portent le nom de Péter Frankl et Vojtěch Rödl, qui ont démontré en 1987 que, pour certaines valeurs des paramètres du graphe, ils ont un nombre de stabilité (taille du stable maximal) petit et un nombre chromatique élevé[1]. Depuis, ces graphes sont devenus intéressants en complexité de calcul, comme des exemples qui sont difficiles pour la programmation semi-définie basée sur des algorithmes d'approximation du problème de couverture par sommets et pour les problèmes de coloration de graphes. Ses propriétés algorithmiques ont été utilisés pour remettre en question la conjecture des jeux uniques.

Définition et exemples

modifier
Le graphe est composé de deux copies du graphe de Turán K2,2,2,2.
Le graphe est composé de deux copies du graphe de Clebsch 5-régulier.

Soit n être un entier positif, et soit un nombre réel dans l'intervalle de l'unité . On suppose de plus que est un entier pair. Le graphe de Frankl-Rödl noté est le graphe qui a pour sommets les sommets de l'hypercube de dimension , et dans lequel deux sommets sont adjacents lorsque leur distance de Hamming (le nombre de coordonnées dans lesquelles les deux diffèrent) est exactement [2]. La condition que est un entier pair empêche le graphe d'être biparti. Le graphe de Frankl-Rödl est nécessairement non connexe, avec au moins une composante connexe pour chacun des deux côtés de la bipartition du graphe hypercube correspondant.

Comme premier exemple, le graphe de Frankl-Rödl relie les sommets à distance deux dans un cube tridimensionnel ordinaire, comme le montre l'illustration. Géométriquement, ce motif de connexion produit une forme connue sous le nom d'octangle étoilé; du point de vue de la théorie des graphes, il est formé de deux composantes connexes, dont chacune est un graphe complet à quatre sommets. De même, le graphe Frankl-Rödl relie les sommets à distance deux d'un hypercube à quatre dimensions et est formé de deux copies du graphe de Turán K2,2,2,2. Les deux graphes deFrankl-Rödl de dimension cinq, à savoir et , sont formés chacun de deux copies complémentaires de graphes de Clebsch, de degré cinq et dix respectivement.

Propriétés

modifier

Le graphe de Frankl-Rödl est un graphe régulier, de degré

Il hérite les symétries de son hypercube sous-jacent, ce qui en fait un graphe symétrique.

Comme l'on montré Frankl et Rödl 1987[3], lorsque , la taille d'un ensemble indépendant maximal dans un graphe de Frankl-Rödl est

Dans cette formule Ω dans cette formule est une Ω a le sens usuel. Pour les valeurs constantes de γ et variables de n, cette taille de l'ensemble indépendant maximal est une petite fraction des sommets du graphe. Plus précisément, cette fraction est inversement proportionnelle à une fonction exponentielle de n et une fonction polynomiale enla taille du graphique. Parce que chaque couleur dans la bonne coloration du graphe de Frankl-Rödl forme un ensemble indépendant avec peu de sommets, le nombre de couleurs doit être grand (une fonction polynomiale de la taille du graphique).

Complexité algorithmique

modifier

Le problème de couverture par sommets est de trouver un ensemble de sommets qui est adjacent à toute arête du graphe. Ce problème et NP-difficile mais peut être approché dans un taux d'approximation de valeur 2, par exemple, en prenant les extrémités des arêtes d'un couplage maximal. La preuve que c'est le meilleur taux d'approximation possible d'un algorithme d'approximation en temps polynomial est fournie par le fait que, lorsqu'il est représenté comme un programme semi-défini, le problème a un écart d'intégralité de deux ; cet écart est le rapport entre la valeur de solution de la solution entière (une couverture par sommets valide) et sa relaxation semi-définie. Selon la conjecture des jeux uniques, pour de nombreux autres problèmes le rapport d'approximation optimal est fourni par l'écart d'intégralité de leur relaxation semi-définie. Cependant, les graphes de FranklRödl sont les seuls cas connus de couverture par sommets pour lesquels l'écart d'intégralité peut être aussi mauvais que deux[4],[5].

Des graphes de Frankl–Rödl ont également été utilisés pour étudier des approches semi-définies pour la coloration de graphes. Dans cette optique, on étudie la 3-coloration de graphe en relation avec les graphes Frankl-Rödl de paramètre . Les graphes de Frankl-Rödl avec cette valeur du paramètre ont un nombre chromatique élevé ; la programmation semi-définie est néanmoins incapable de les distinguer des graphes 3-colorables[6],[7],[8]. Cependant, pour ces graphes, les méthodes algébriques basées sur des sommes polynomiales de carrés peuvent fournir des bornes plus fortes qui montrent qu'il faut beaucoup de couleurs. Ce résultat est un défi à l'optimisation de la programmation semi-définie et à la correction de la conjecture des jeux uniques[2].

Notes et références

modifier
  1. Peter Frankl et Vojtěch Rödl, « Forbidden intersections », Transactions of the American Mathematical Society, vol. 300, no 1,‎ , p. 259–286 (DOI 10.2307/2000598 Accès libre, JSTOR 2000598, MR 871675).
  2. a et b Li-Yang Tan, Yuan Zhou, Ryan O'Donnell et Manuel Kauers, « Hypercontractive inequalities via SOS, and the Frankl–Rödl graph », Discrete Analysis, vol. 2016:4,‎ , p. 20pp (DOI 10.19086/da.612, arXiv 1212.5324).
  3. Également Konstantinos Georgiou, Avner Magen, Toniann Pitassi et Iannis Tourlakis, « Integrality gaps of 2 − o(1) for vertex cover SDPs in the Lovász–Schrijver hierarchy », SIAM Journal on Computing, vol. 39, no 8,‎ , p. 3553–3570 (DOI 10.1137/080721479, MR 2745765, lire en ligne).
  4. Georgiou et al. 2010.
  5. Tan et al. 2016.
  6. David Karger, Rajeev Motwani et Madhu Sudan, « Approximate graph coloring by semidefinite programming », Journal of the ACM, vol. 45, no 2,‎ , p. 246–265 (DOI 10.1145/274787.274791, MR 1623197, arXiv cs/9812008).
  7. Jon Kleinberg et Michel X. Goemans, « The Lovász theta function and a semidefinite programming relaxation of vertex cover », SIAM Journal on Discrete Mathematics, vol. 11, no 2,‎ , p. 196–204 (DOI 10.1137/S0895480195287541, MR 1617152).
  8. Moses Charikar, « On semidefinite programming relaxations for graph coloring and vertex cover », dans Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02), Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, (ISBN 978-0-89871-513-2, lire en ligne), p. 616–620.

Articles liés

modifier