Partition en cliques

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.

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 la couverture par cliques à partir du problème de la coloration de graphe dont la NP-complétude est connue[2].

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 toutes deux des classes de graphes parfaits.

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 n^{1 − ε}, 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].

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].

• (en) Viggo Kann, « Minimum clique cover », sur A compendium of NP optimization problems, 20 mars 2000