Cliques, ensembles indépendants et couvertures par sommets

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. Cliques, ensembles indépendants et couvertures par sommets

Trois des questions les plus étudiées de la théorie des graphes portent sur des ensembles de sommets, et chacune s'énonce en une ligne.

• Une clique est un ensemble de sommets dans lequel deux sommets quelconques sont adjacents. Une clique à k sommets est une copie du graphe complet Kk à l'intérieur du graphe. La taille de la plus grande clique est le nombre de clique, noté ω(G).
• Un ensemble indépendant, aussi appelé stable, est un ensemble de sommets dans lequel aucun couple de sommets n'est adjacent. La taille du plus grand est le nombre d'indépendance, α(G).
• Une couverture par sommets est un ensemble de sommets qui touche toutes les arêtes : chaque arête a au moins une extrémité dans l'ensemble. La taille de la plus petite est le nombre de couverture par sommets, τ(G).

Une clique et un ensemble indépendant sont des opposés : l'une exige toutes les arêtes possibles entre les sommets choisis, l'autre aucune. Dans un réseau d'amitiés, une clique est un groupe où tout le monde connaît tout le monde, et un ensemble indépendant est un groupe de parfaits inconnus les uns pour les autres. Le mot « clique » est entré dans le domaine depuis la sociologie, où Luce et Perry l'ont employé en 1949 précisément pour de tels groupes. Le guide des sommets et arêtes présente le vocabulaire sur lequel reposent ces définitions.

Chaque question comporte un piège dans sa formulation. Un ensemble est maximal lorsqu'on ne peut rien lui ajouter (ou, pour une couverture, rien lui retirer) sans perdre la propriété. Il est maximum lorsqu'il n'existe aucun ensemble plus grand ayant la propriété (ou, pour une couverture, aucun plus petit). Tout ensemble maximum est maximal, mais la réciproque est fausse, et c'est dans la différence entre les deux que la plupart des algorithmes se trompent.

2. Un graphe, trois réponses, une identité

L'exemple suivi compte 8 sommets et 12 arêtes. Les sommets A, B, C et D sont tous reliés entre eux, D, E et F forment un triangle, et un cycle de longueur 5 C, D, F, G, H fait le tour par le bas :

E = {AB, AC, AD, BC, BD, CD, CH, DE, DF, EF, FG, GH}      8 sommets, 12 arêtes

deg:   A 3   B 3   C 4   D 5   E 2   F 3   G 2   H 2

La plus grande clique est {A, B, C, D}, donc ω = 4, et c'est la seule clique de cette taille. Les plus grands ensembles indépendants ont 3 sommets, par exemple {A, E, G}, donc α = 3 ; il y en a sept. Les plus petites couvertures par sommets ont 5 sommets, par exemple {B, C, D, F, H}, donc τ = 5, et là encore il y en a sept. Les deux sept ne sont pas une coïncidence.

Deux arguments courts relient les trois nombres. D'abord, le complémentaire d'un graphe possède une arête exactement là où le graphe n'en a pas, donc une clique de G est un ensemble indépendant du complémentaire, et inversement : ω(G) est égal à α du complémentaire. Ensuite, un ensemble S est indépendant exactement lorsque les sommets restants forment une couverture par sommets. Si une arête évitait les sommets restants, ses deux extrémités seraient dans S, donc S ne serait pas indépendant, et l'argument fonctionne de la même manière en sens inverse. Le plus grand S donne la plus petite couverture :

α(G) + τ(G) = n, pour tout graphe à n sommets.

Cette identité est généralement attribuée à Gallai, qui l'a publiée en 1959. Dans l'exemple, 3 + 5 = 8, et les sept plus grands ensembles indépendants sont exactement les complémentaires des sept plus petites couvertures. La conséquence pratique est que les trois problèmes n'en font qu'un sous trois costumes : un algorithme pour l'un d'eux, appliqué au graphe ou à son complémentaire, résout exactement les deux autres.

3. Maximal n'est pas maximum

Le triangle {D, E, F} est une clique, et on ne peut lui ajouter aucun sommet, car aucun autre sommet n'est adjacent aux trois sommets D, E et F. C'est une clique maximale de taille 3, alors que le maximum est 4. Les arêtes CH, FG et GH sont aussi des cliques maximales, de taille 2 : aucune d'elles n'est contenue dans un triangle. Au total, l'exemple compte cinq cliques maximales, et une seule d'entre elles est maximum.

Les ensembles indépendants tombent encore plus facilement dans le même piège. La méthode gloutonne naturelle parcourt les sommets et prend chacun de ceux dont aucun voisin n'a encore été pris. Le résultat est toujours maximal, mais sa taille dépend de l'ordre. Commencez par D, le sommet de plus haut degré, et D bloque cinq sommets d'un coup ; une fois G pris, tous les sommets restants sont adjacents à l'un des deux, et la méthode s'arrête sur {D, G}, un sommet en dessous de l'optimum. L'exemple compte dix ensembles indépendants maximaux, trois de taille 2 et sept de taille 3. Commencer par les sommets de faible degré, qui en bloquent peu d'autres, est une meilleure habitude, mais aucun ordre glouton ne convient à tous les graphes.

La leçon vaut aussi pour les logiciels. Une routine qui « trouve une clique » ou « trouve un ensemble indépendant » renvoie généralement un ensemble maximal, et rapidement. En trouver un maximum est une tâche différente et bien plus difficile, et la suite de cet article explique comment la résoudre, l'approcher et la borner.

4. Lister toutes les cliques maximales : Bron–Kerbosch

La méthode classique pour trouver toutes les cliques maximales est l'algorithme publié par Bron et Kerbosch en 1973. Il fait grandir une clique R un sommet à la fois et maintient deux autres ensembles : P, les sommets qui peuvent encore être ajoutés car ils sont adjacents à tous les sommets de R, et X, les sommets qui pourraient être ajoutés mais ont déjà été explorés, de sorte que toute clique qui les utilise a déjà été signalée. Lorsque P et X sont tous deux vides, R ne peut plus grandir et rien n'a été sauté, donc R est une clique maximale.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def bron_kerbosch(R, P, X, adj, out):
    """Signale chaque clique maximale qui contient R, n'utilise que P et évite X."""
    if not P and not X:
        out.append(sorted(R))                 # rien ne peut être ajouté : R est maximale
        return
    pivot = max(P | X, key=lambda u: len(P & adj[u]))
    for v in sorted(P - adj[pivot]):          # les voisins du pivot sont essayés plus tard
        bron_kerbosch(R | {v}, P & adj[v], X & adj[v], adj, out)
        P.remove(v)
        X.add(v)                              # toute clique contenant v a maintenant été signalée

def maximal_cliques(adj):
    out = []
    bron_kerbosch(set(), set(adj), set(), adj, out)
    return sorted(out, key=lambda c: (-len(c), c))

def complement(adj):
    return {v: set(adj) - adj[v] - {v} for v in adj}

G = graph(['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'CH', 'DE', 'DF', 'EF', 'FG', 'GH'])

print(maximal_cliques(G))
# [['A', 'B', 'C', 'D'], ['D', 'E', 'F'], ['C', 'H'], ['F', 'G'], ['G', 'H']]
print(maximal_cliques(complement(G)))   # les ensembles indépendants maximaux de G
# [['A', 'E', 'G'], ['A', 'E', 'H'], ['A', 'F', 'H'], ['B', 'E', 'G'], ['B', 'E', 'H'], ['B', 'F', 'H'], ['C', 'E', 'G'], ['C', 'F'], ['D', 'G'], ['D', 'H']]

Le pivot est ce qui le rend rapide. Toute clique maximale doit contenir le pivot ou un sommet qui ne lui est pas adjacent, donc la boucle n'a besoin de brancher que sur les non-voisins du pivot ; choisir comme pivot le sommet de P ou X ayant le plus de voisins dans P évite le plus de travail. Tomita, Tanaka et Takahashi ont prouvé en 2006 qu'avec cette règle, le temps d'exécution est O(3n/3), et que cette borne ne peut pas être améliorée, car Moon et Moser ont montré en 1965 qu'un graphe à n sommets peut avoir 3n/3 cliques maximales lorsque n est un multiple de 3. Le graphe extrême est le complémentaire de n/3 triangles disjoints : sur 9 sommets, il a 27 cliques maximales, et sur 30 sommets, il en a 59 049.

La première ligne de sortie liste les cinq cliques maximales de la section 3, de la plus grande à la plus petite. La seconde ligne exécute la même fonction sur le complémentaire et liste donc les dix ensembles indépendants maximaux. La fonction a été vérifiée par comparaison avec la recherche de cliques de networkx, qui utilise le même algorithme, sur 3 000 graphes aléatoires d'au plus 10 sommets.

5. Trouver exactement le plus grand ensemble indépendant

Lister tous les ensembles maximaux est souvent plus que nécessaire, et la réponse peut être trouvée directement par une recherche. Deux règles suffisent pour une méthode correcte. Un sommet de degré 0 peut toujours être pris. Un sommet v de degré 1 peut lui aussi toujours être pris : si un plus grand ensemble indépendant contient son unique voisin u, remplacer u par v le garde indépendant et de même taille. Lorsqu'aucune des deux règles ne s'applique, choisissez un sommet et essayez les deux possibilités : le prendre et supprimer ses voisins, ou l'écarter.

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

def remove(adj, gone):
    return {u: adj[u] - gone for u in adj if u not in gone}

def greedy_independent_set(adj, order):
    """Prend chaque sommet tour à tour, sauf si un voisin est déjà pris. Toujours maximal."""
    chosen = set()
    for v in order:
        if not adj[v] & chosen:
            chosen.add(v)
    return chosen

def max_independent_set(adj):
    """Exact : un sommet de degré 0 ou 1 peut toujours être pris sans risque ; sinon, brancher."""
    if not adj:
        return set()
    v = min(adj, key=lambda u: len(adj[u]))
    if len(adj[v]) <= 1:
        return {v} | max_independent_set(remove(adj, {v} | adj[v]))
    v = max(adj, key=lambda u: len(adj[u]))
    take = {v} | max_independent_set(remove(adj, {v} | adj[v]))   # v pris, voisins exclus
    skip = max_independent_set(remove(adj, {v}))                  # v exclu
    return take if len(take) >= len(skip) else skip

G = graph(['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'CH', 'DE', 'DF', 'EF', 'FG', 'GH'])

print(sorted(greedy_independent_set(G, 'DGABCEFH')))   # commencer par le sommet le plus chargé
# ['D', 'G']
best = max_independent_set(G)
print(sorted(best), sorted(set(G) - best))             # plus grand ensemble indépendant, plus petite couverture
# ['A', 'E', 'G'] ['B', 'C', 'D', 'F', 'H']

La première ligne reproduit l'impasse gloutonne de la section 3. La seconde donne un plus grand ensemble indépendant, {A, E, G}, et d'après l'identité de la section 2, les sommets qu'il laisse de côté forment une plus petite couverture par sommets, {B, C, D, F, H}. La fonction a été vérifiée par comparaison avec networkx sur les mêmes 3 000 graphes aléatoires, et chaque ensemble qu'elle a renvoyé était indépendant et de la bonne taille.

Brancher sur un sommet de degré maximum est délibéré : le prendre supprime le plus de sommets, si bien que cette branche réduit le graphe le plus vite. Les règles de degré font aussi que la recherche ne branche jamais sur une forêt, puisque toute forêt a un sommet de degré 0 ou 1 et que supprimer des sommets la laisse une forêt. Sur les graphes généraux, la recherche reste exponentielle, mais bien plus petite que les 2n sous-ensembles : Tarjan et Trojanowski ont affiné en 1977 des règles de ce type jusqu'à un temps en O(2n/3) pour leur algorithme, et des travaux ultérieurs ont encore abaissé la base.

6. Couverture par sommets : une 2-approximation et un test exact rapide

La couverture par sommets possède deux propriétés qui manquent à ses partenaires, et toutes deux viennent de l'examen des arêtes. La première est une approximation simple. Parcourez les arêtes et, chaque fois qu'une arête n'a encore aucune extrémité dans la couverture, ajoutez ses deux extrémités. Les arêtes ainsi choisies n'ont aucun sommet en commun, elles forment donc un couplage, et aucune autre arête ne pourrait s'y ajouter, c'est donc un couplage maximal. Toute couverture, quelle qu'elle soit, doit contenir au moins une extrémité de chaque arête du couplage, et ces extrémités sont toutes différentes, donc τ est au moins égal au nombre d'arêtes du couplage. La méthode prend exactement deux sommets par arête du couplage, donc sa couverture ne dépasse jamais le double de l'optimum. Cet argument est généralement attribué à Gavril et à Yannakakis, et le livre de Garey et Johnson de 1979 l'a fait largement connaître.

def matching_cover(edges):
    """2-approximation : prendre les deux extrémités de chaque arête encore non couverte."""
    cover = set()
    for u, v in edges:
        if u not in cover and v not in cover:
            cover |= {u, v}                   # ces arêtes forment un couplage maximal
    return cover

def cover_of_size(edges, k):
    """Une couverture par sommets d'au plus k sommets, ou None. Au plus 2^k branches."""
    if not edges:
        return set()
    if k == 0:
        return None
    u, v = edges[0]                           # u ou v doit figurer dans toute couverture
    for w in (u, v):
        rest = [e for e in edges if w not in e]
        found = cover_of_size(rest, k - 1)
        if found is not None:
            return found | {w}
    return None

E = ['AB', 'AC', 'AD', 'BC', 'BD', 'CD', 'CH', 'DE', 'DF', 'EF', 'FG', 'GH']

print(sorted(matching_cover(E)))
# ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
print(cover_of_size(E, 4))
# None
print(sorted(cover_of_size(E, 5)))
# ['A', 'B', 'D', 'F', 'H']

Sur l'exemple, le couplage est AB, CD, EF et GH, et la méthode prend les huit sommets. C'est une mauvaise couverture, mais le couplage prouve aussi qu'aucune couverture n'a moins de quatre sommets, donc la méthode sait que sa propre réponse est à un facteur 2 près sans connaître l'optimum. Une alternative tentante, qui consiste à prendre à répétition le sommet de plus haut degré, n'offre pas une telle garantie : sur des graphes construits avec soin, sa couverture peut être pire que l'optimum d'un facteur qui croît avec la taille du graphe.

La seconde propriété est que les petites couvertures sont faciles à trouver exactement. Toute arête uv doit avoir u ou v dans la couverture, donc la fonction cover_of_size essaie les deux et continue avec un budget de k − 1. L'arbre de recherche a une profondeur d'au plus k et au plus 2k feuilles, quel que soit le nombre de sommets. Sur l'exemple, elle signale qu'aucune couverture de 4 sommets n'existe et en trouve une de 5. Avec k = 20, l'arbre a au plus environ un million de feuilles, quelle que soit la taille du graphe : la taille de la recherche dépend de la taille de la couverture, pas du nombre de sommets. Les problèmes qui ont ce comportement sont dits traitables à paramètre fixe.

Une règle de prétraitement tirée de l'article de Buss et Goldsmith de 1993 réduit d'abord l'entrée. Un sommet ayant plus de k voisins doit appartenir à toute couverture de taille k, car sinon tous ses voisins seraient nécessaires. Après avoir pris ces sommets, chaque sommet restant couvre au plus k arêtes, donc s'il reste plus de k2 arêtes, la réponse est non. Le meilleur algorithme exact connu, dû à Chen, Kanj et Xia en 2010, s'exécute en temps O(1,2738k + kn).

7. Quelle est la difficulté de ces problèmes ?

Décider si un graphe possède une clique de taille k est NP-complet, tout comme décider s'il possède une couverture par sommets de taille k. Les deux figuraient sur la liste de 21 problèmes NP-complets établie par Karp en 1972, et l'ensemble indépendant découle de l'un ou de l'autre par les identités de la section 2. On ne connaît d'algorithme en temps polynomial pour aucun d'eux, et en trouver un prouverait que P = NP.

Les identités préservent les réponses exactes mais pas les réponses approchées, et c'est là que les trois problèmes se séparent. La couverture par sommets peut être approchée à un facteur 2 près, comme l'a montré la section 6. La clique et l'ensemble indépendant ne peuvent pratiquement pas être approchés du tout : Håstad a prouvé en 1999 que, pour tout ε > 0, aucun algorithme en temps polynomial n'approche la plus grande clique à un facteur n1−ε près, sauf si NP = ZPP, et Zuckerman a montré en 2007 que la même chose vaut en supposant seulement P ≠ NP. Un petit calcul montre pourquoi l'identité ne transfère pas la garantie : dans un graphe à 1 000 sommets avec τ = 500, une couverture de 1 000 sommets est à un facteur 2 près, et pourtant l'ensemble indépendant qu'elle laisse est vide.

Même le facteur 2 pour la couverture par sommets est peut-être le bout du chemin. Dinur et Safra ont prouvé en 2005 qu'approcher ce problème à un facteur 1,36 près est NP-difficile, et Khot et Regev ont prouvé en 2008 qu'un facteur 2 − ε est difficile à atteindre si la conjecture des jeux uniques est vraie. Le tableau paramétré diffère aussi. La couverture par sommets est traitable à paramètre fixe, comme l'a montré la section 6, tandis que trouver une clique de taille k est complet pour la classe W[1], comme Downey et Fellows l'ont prouvé en 1995, ce qui indique fortement qu'aucun algorithme de temps d'exécution f(k) · nc n'existe pour ce problème.

8. Des bornes vérifiables à la main

Comme les valeurs exactes sont difficiles à calculer, les bornes simples sont précieuses, et plusieurs relient ces problèmes à la coloration et aux degrés.

• Les cliques imposent des couleurs. Les sommets d'une clique sont deux à deux adjacents, donc chacun a besoin de sa propre couleur : χ(G) ≥ ω(G), où χ est le nombre chromatique présenté dans le guide sur la coloration de graphes. Dans l'exemple, la clique {A, B, C, D} impose 4 couleurs, et 4 suffisent.
• Les couleurs donnent des ensembles indépendants. Chaque classe de couleur d'une coloration propre est un ensemble indépendant, donc les n sommets se répartissent en χ ensembles indépendants et le plus grand a au moins n / χ sommets : α(G) ≥ n / χ(G). Dans l'exemple, cela donne α ≥ 2.
• Les faibles degrés donnent des ensembles indépendants. La borne de Caro–Wei, trouvée indépendamment par Caro en 1979 et par Wei en 1981, affirme que α(G) ≥ ∑ 1 / (d(v) + 1). Rangez les sommets dans un ordre aléatoire et gardez chaque sommet qui vient avant tous ses voisins : l'ensemble gardé est indépendant, et chaque sommet est gardé avec probabilité 1 / (d(v) + 1). Pour l'exemple, la somme vaut 127/60 ≈ 2,12, et comme α est un nombre entier, α ≥ 3, ce qui est exact ici. Le guide sur le degré d'un sommet explique pourquoi ces sommes de degrés sont si utiles.
• Beaucoup d'arêtes imposent des cliques. Le théorème de Turán de 1941 affirme qu'un graphe à n sommets sans clique de taille r + 1 a au plus (1 − 1/r) n2 / 2 arêtes, et que le maximum est atteint en répartissant les sommets en r groupes de tailles presque égales et en reliant chaque paire de sommets de groupes différents. Le cas r = 2 est le théorème de Mantel de 1907 : un graphe sans triangle a au plus n2 / 4 arêtes. Avec 8 sommets, tout graphe de plus de 16 arêtes contient un triangle et tout graphe de plus de 21 arêtes contient K4.

9. Théorie de Ramsey : l'ordre est inévitable

Le théorème de Turán dit que les graphes denses contiennent de grandes cliques. La théorie de Ramsey dit quelque chose de plus fort : tout grand graphe contient une grande clique ou un grand ensemble indépendant, quelle que soit sa densité. Le nombre de Ramsey R(s, t) est le plus petit n tel que tout graphe à n sommets possède une clique de taille s ou un ensemble indépendant de taille t. Ramsey a prouvé en 1930 que ces nombres existent.

Le plus petit cas est le problème de la fête : parmi six personnes quelconques, il y a trois amis mutuels ou trois inconnus mutuels, donc R(3, 3) = 6. La preuve tient en quelques lignes. Choisissez une personne quelconque v. Parmi les cinq autres, au moins trois sont des amis de v ou au moins trois sont des inconnus pour v ; disons trois amis x, y et z. Si deux d'entre eux sont amis, ils forment un trio d'amis avec v. Si aucun ne l'est, x, y et z sont trois inconnus mutuels. Cinq personnes ne suffisent pas : placez-les en pentagone, rendez amis les voisins et inconnus tous les autres, et aucun trio de l'un ou l'autre type n'apparaît. Une vérification exhaustive des 32 768 façons de marquer les 15 paires de six personnes comme amies ou inconnues confirme le résultat.

Au-delà des plus petits cas, les nombres de Ramsey sont notoirement difficiles. Greenwood et Gleason ont trouvé R(4, 4) = 18 en 1955. Pour R(5, 5), Exoo a montré en 1989 qu'il vaut au moins 43, et Angeltveit et McKay ont prouvé en 2024 qu'il vaut au plus 46, après des décennies de calcul ; la valeur exacte reste inconnue. Pour un k quelconque, Erdős et Szekeres ont prouvé en 1935 que R(k, k) est inférieur à 4k, et Erdős a prouvé en 1947 qu'il est supérieur à 2k/2 en montrant qu'un graphe aléatoire n'a généralement ni grande clique ni grand ensemble indépendant, l'une des premières utilisations de la méthode probabiliste. Des travaux ultérieurs ont rogné la borne supérieure, mais la base 4 a tenu jusqu'à ce que Campos, Griffiths, Morris et Sahasrabudhe l'abaissent à (4 − ε)k dans un article publié pour la première fois en 2023.

10. Des graphes particuliers où les problèmes deviennent faciles

La NP-difficulté est un énoncé qui porte sur tous les graphes. Beaucoup de classes de graphes rencontrées en pratique ont une structure qui rend ces problèmes traitables.

• Graphes bipartis. Le théorème de Kőnig de 1931 affirme que, dans un graphe biparti, la plus petite couverture par sommets a exactement autant de sommets que le plus grand couplage, et les plus grands couplages se trouvent en temps polynomial grâce aux méthodes de flot du guide sur le flot maximum. Le plus grand ensemble indépendant découle alors de α = n − τ. Le guide des graphes bipartis traite un exemple en détail.
• Arbres et forêts. Les règles de degré de la section 5 résolvent toute forêt sans branchement, ce qui donne un algorithme en temps linéaire avec les bonnes structures de données.
• Graphes cordaux. Gavril a montré en 1972 que la plus grande clique, le plus grand ensemble indépendant et une coloration optimale d'un graphe cordal peuvent tous être trouvés en temps polynomial à partir d'un ordre d'élimination parfait, comme le décrit le guide des graphes cordaux.
• Graphes parfaits. Dans un graphe parfait, le nombre chromatique est égal au nombre de clique dans chaque sous-graphe induit. Grötschel, Lovász et Schrijver ont montré en 1981 que le nombre de clique et le nombre d'indépendance d'un graphe parfait peuvent être calculés en temps polynomial, à l'aide de la méthode de l'ellipsoïde.
• Graphes planaires. Un graphe planaire ne contient pas de K5, donc sa plus grande clique a au plus 4 sommets et peut être trouvée en examinant chaque ensemble d'au plus 4 sommets. L'ensemble indépendant et la couverture par sommets restent cependant NP-complets : Garey, Johnson et Stockmeyer l'ont montré pour les graphes planaires en 1976, et Garey et Johnson l'ont étendu en 1977 aux graphes planaires de degré maximum 3.

11. Où servent les cliques, les ensembles indépendants et les couvertures

• Ordonnancement et conflits. Dans un graphe de conflits, où l'on relie les tâches qui ne peuvent pas partager un même créneau, un ensemble indépendant est un groupe de tâches qui peuvent s'exécuter ensemble, et une clique est un groupe qui exige autant de créneaux qu'il a de membres. Le nombre de clique est donc une borne inférieure du nombre de créneaux.
• Réseaux sociaux et biologiques. Les cliques modélisent les groupes de personnes très soudés et les complexes protéiques. Les données réelles sont bruitées, si bien que les analystes utilisent souvent des versions relâchées, comme les k-cœurs du guide sur le degré d'un sommet, et Bron–Kerbosch reste l'outil standard pour lister les cliques exactes dans les réseaux peu denses.
• Surveillance. Placer des capteurs sur le moins de nœuds possible de sorte que chaque lien d'un réseau soit surveillé est un problème de couverture par sommets, tout comme choisir le moins de gardes possible aux carrefours pour que chaque rue soit en vue de l'un d'eux.
• Théorie des codes. Un ensemble de mots de code de distance minimale d est un ensemble indépendant dans le graphe qui relie deux mots quelconques à distance inférieure à d, donc les meilleurs codes d'une longueur donnée sont des plus grands ensembles indépendants.
• Mise en correspondance de structures. Barrow et Burstall ont observé en 1976 que la plus grande sous-structure commune de deux graphes, utilisée pour comparer des molécules, correspond à la plus grande clique d'un graphe produit construit à partir de la paire. Le guide sur l'isomorphisme de graphes traite le problème voisin qui consiste à décider si deux graphes sont les mêmes.

12. Erreurs fréquentes

13. Glossaire

15. Références

Les définitions, théorèmes et attributions ci-dessus proviennent de ces sources, classées par ordre chronologique.

1. Mantel, W. (1907). "Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff)." Wiskundige Opgaven 10, 60 à 61.
2. Ramsey, F. P. (1930). "On a Problem of Formal Logic." Proceedings of the London Mathematical Society s2-30, 264 à 286.
3. Kőnig, D. (1931). "Gráfok és mátrixok." Matematikai és Fizikai Lapok 38, 116 à 119.
4. Erdős, P. et Szekeres, G. (1935). "A Combinatorial Problem in Geometry." Compositio Mathematica 2, 463 à 470.
5. Turán, P. (1941). "Egy gráfelméleti szélsőértékfeladatról." Matematikai és Fizikai Lapok 48, 436 à 452.
6. Erdős, P. (1947). "Some Remarks on the Theory of Graphs." Bulletin of the American Mathematical Society 53, 292 à 294.
7. Luce, R. D. et Perry, A. D. (1949). "A Method of Matrix Analysis of Group Structure." Psychometrika 14(2), 95 à 116.
8. Greenwood, R. E. et Gleason, A. M. (1955). "Combinatorial Relations and Chromatic Graphs." Canadian Journal of Mathematics 7, 1 à 7.
9. Gallai, T. (1959). "Über extreme Punkt- und Kantenmengen." Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica 2, 133 à 138.
10. Moon, J. W. et Moser, L. (1965). "On Cliques in Graphs." Israel Journal of Mathematics 3, 23 à 28.
11. Gavril, F. (1972). "Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph." SIAM Journal on Computing 1(2), 180 à 187.
12. Karp, R. M. (1972). "Reducibility Among Combinatorial Problems." Dans Complexity of Computer Computations, sous la direction de R. E. Miller et J. W. Thatcher, 85 à 103. New York : Plenum.
13. Bron, C. et Kerbosch, J. (1973). "Algorithm 457: Finding All Cliques of an Undirected Graph." Communications of the ACM 16(9), 575 à 577.
14. Barrow, H. G. et Burstall, R. M. (1976). "Subgraph Isomorphism, Matching Relational Structures and Maximal Cliques." Information Processing Letters 4(4), 83 à 84.
15. Garey, M. R., Johnson, D. S. et Stockmeyer, L. (1976). "Some Simplified NP-Complete Graph Problems." Theoretical Computer Science 1(3), 237 à 267.
16. Garey, M. R. et Johnson, D. S. (1977). "The Rectilinear Steiner Tree Problem is NP-Complete." SIAM Journal on Applied Mathematics 32(4), 826 à 834. Couverture par sommets sur les graphes planaires de degré maximum 3.
17. Tarjan, R. E. et Trojanowski, A. E. (1977). "Finding a Maximum Independent Set." SIAM Journal on Computing 6(3), 537 à 546.
18. Caro, Y. (1979). "New Results on the Independence Number." Rapport technique, Université de Tel-Aviv.
19. Garey, M. R. et Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco : W. H. Freeman. La 2-approximation pour la couverture par sommets.
20. Wei, V. K. (1981). "A Lower Bound on the Stability Number of a Simple Graph." Bell Laboratories Technical Memorandum 81-11217-9.
21. Grötschel, M., Lovász, L. et Schrijver, A. (1981). "The Ellipsoid Method and Its Consequences in Combinatorial Optimization." Combinatorica 1(2), 169 à 197.
22. Exoo, G. (1989). "A Lower Bound for R(5, 5)." Journal of Graph Theory 13(1), 97 à 98.
23. Buss, J. F. et Goldsmith, J. (1993). "Nondeterminism within P." SIAM Journal on Computing 22(3), 560 à 572.
24. Downey, R. G. et Fellows, M. R. (1995). "Fixed-Parameter Tractability and Completeness II: On Completeness for W[1]." Theoretical Computer Science 141, 109 à 131.
25. Håstad, J. (1999). "Clique is Hard to Approximate within n^1−ε." Acta Mathematica 182(1), 105 à 142.
26. Dinur, I. et Safra, S. (2005). "On the Hardness of Approximating Minimum Vertex Cover." Annals of Mathematics 162(1), 439 à 485.
27. Tomita, E., Tanaka, A. et Takahashi, H. (2006). "The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments." Theoretical Computer Science 363(1), 28 à 42.
28. Zuckerman, D. (2007). "Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number." Theory of Computing 3, 103 à 128.
29. Khot, S. et Regev, O. (2008). "Vertex Cover Might Be Hard to Approximate to within 2 − ε." Journal of Computer and System Sciences 74(3), 335 à 349.
30. Chen, J., Kanj, I. A. et Xia, G. (2010). "Improved Upper Bounds for Vertex Cover." Theoretical Computer Science 411(40–42), 3736 à 3756.
31. Diestel, R. (2017). Graph Theory, 5e édition. Graduate Texts in Mathematics 173. Berlin : Springer.
32. Angeltveit, V. et McKay, B. D. (2024). "R(5, 5) ≤ 46." arXiv:2409.15709.
33. Campos, M., Griffiths, S., Morris, R. et Sahasrabudhe, J. (2026). "An Exponential Improvement for Diagonal Ramsey." Annals of Mathematics 203(3), 869 à 932. Publié pour la première fois en 2023 sous la référence arXiv:2303.09521.