Partition en cliques
En théorie des graphes, une couverture par cliques ou une partition en cliques d'un graphe non orienté est une partition des sommets du graphe en cliques, c'est-à-dire en des ensembles de sommets à l'intérieur desquels deux sommets sont adjacents. Un couverture par cliques minimale est une couverture de taille minimale, c'est-à-dire par un nombre minimal de cliques. Le problème de la couverture par cliques est le problème algorithmique qui consiste à trouver une couverture par cliques minimale.
Relations avec la coloration
Une couverture par cliques d'un graphe G peut être vue comme une coloration du graphe complémentaire de G ; ce graphe complémentaire a le même ensemble de sommets, et a des arêtes entre des sommets qui ne sont pas adjacents dans G. Comme les couvertures par cliques, les colorations de graphes sont des partitions de l'ensemble de sommets, mais en sous-ensembles indépendants plutôt qu'en cliques. Un sous-ensemble de sommets est une clique de G si et seulement si elle est un ensemble indépendant dans le complément de G, donc une partition des sommets de G est une couverture par cliques de G si et seulement si c'est une coloration du complément de G.
Complexité algorithmique
Le problème de la couverture par cliques est, dans la théorie de la complexité algorithmique, le problème de trouver une couverture par cliques minimale ou, reformulé comme un problème de décision, de décider s'il existe une couverture par cliques dont le nombre de cliques est inférieur à un seuil donné. Trouver une couverture par cliques de taille minimale est NP-difficile, et sa version de décision est un problème NP-complet. Il est l'un des 21 problèmes NP-complets de Karp donnés dans son célèbre article de 1972[1].
L'équivalence entre la couverture par cliques et la coloration est une réduction qui peut être utilisée pour prouver la NP-complétude du problème de l'ouverture par cliques à partir du problème de la coloration de graphe dont la NP-complétude est connue[2].
Classes particulières de graphes
Les graphes parfaits sont les graphes dans lesquels le nombre chromatique (nombre minimum de couleurs dans une coloration) de chaque sous-graphe induit est égal à la taille de la clique maximale. D'après le théorème des graphes parfaits, le complément d'un graphe parfait est également parfait. Par conséquent, les graphes parfaits sont également les graphes dans lesquels, pour chaque sous-graphe induit, la taille d'une couverture par cliques est égale à la taille de l'ensemble indépendant maximal. Il est possible de calculer la taille d'une couverture par cliques d'un graphe parfait en temps polynomial.
Une autre classe de graphes dans lequel un couverture par cliques minimale peut être trouvée en temps polynomial sont les graphes sans triangle. Dans ces graphes, chaque couverture par cliques consiste en un couplage (un ensemble de paires disjoints de sommets adjacents) avec des singletons pour les sommets non appariés. Le nombre de cliques est égal au nombre de sommets moins le nombre de paires appariées. Par conséquent, dans les graphes sans triangles, les couvertures par cliques minimales peuvent être trouvées en utilisant un algorithme de couplage optimal.
Une partition en cliques optimale peut également être trouvée en temps polynomial pour les graphes à largeur de clique bornée[3]. Ces graphes comprennent entre autres, les cographes et les graphes complètement séparables, qui sont également tous deux des classes de parfait graphiques.
Approximation
Les résultats d'approximations connus pour la coloration de graphe s'appliquent également à la couverture par cliques. Donc, à moins que P = NP, il n'y a pas d'algorithme d'approximation en temps polynomial qui, sur un graphe à n sommets, permet d'obtenir un facteur d'approximation meilleur que n1 − ε, pour tout ε > 0[4]
Dans les graphes où chaque sommet a au plus trois voisins, la couverture par cliques reste NP-difficile, et il existe a une constante ρ > 1 telle qu'il est NP-difficile de calculer une approximation avec un facteur d'approximation ρρ ou mieux. Néanmoins on peut trouver en temps polynomial , une approximation de facteur 5/4. En d'autre termes, cet algorithme détermine une couverture par cliques dont le nombre de clique n'est pas supérieur à 5/4 fois l'optimum[5].
Un problème voisin
Le problème voisin de la couverture par cliques d'arêtes est le problème de partition en cliques des arêtes d'un graphe plutôt que de ses sommets. Il est également NP-complet[6].
Notes et références
- Richard Karp, « Reducibility Among Combinatorial Problems », dans R. E. Miller et J. W. Thatcher, Proceedings of a Symposium on the Complexity of Computer Computations, Plenum Press, (lire en ligne), p. 85–103.
- Michael R. Garey et David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, (ISBN 0-7167-1045-5) A1.2: GT19, p. 194.
- Wolfgang Espelage, Frank Gurski et Egon Wanke, « How to solve NP-hard graph problems on clique-width bounded graphs in polynomial time », dans International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2001), vol. 2204, Springer, coll. « Lecture Notes in Computer Science », (DOI 10.1007/3-540-45477-2_12), p. 117–128.
- D. Zuckerman, « Linear degree extractors and the inapproximability of Max Clique and Chromatic Number », Theory of Computing, vol. 3, , p. 103–128 (DOI 10.4086/toc.2007.v003a006).
- Márcia R. Cerioli, Luerbio Faria, Talita O. Ferreira, Carlos A. J. Martinhon, Fábio Protti et Bruce A. Reed, « Partition into cliques for cubic graphs: Planar case, complexity and approximation », Discrete Applied Mathematics, vol. 156, no 12, , p. 2270–2278 (DOI 10.1016/j.dam.2007.10.015).
- Garey et Johnson 1979, Problem GT59.
Liens externes
- (en) Viggo Kann, « Minimum clique cover », sur A compendium of NP optimization problems,
