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