Problème de la clique

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis 3-SAT vers clique)
Aller à : navigation, rechercher

Le problème de la clique est le problème algorithmique qui consiste a trouver la plus grande clique d'un graphe, ou une clique d'une certaine taille.

Énoncé[modifier | modifier le code]

Le problème de décision associé au problème de la clique maximum prend en entrée un graphe G et un entier et détermine si G contient une clique de cardinal au moins égal à un entier donné k. C'est un problème NP-complet.

Le problème d'optimisation associé au « problème de la clique » est le problème de la clique maximum : il consiste à exhiber, dans un graphe fini, l'une des cliques de taille maximale

La recherche d'une clique dans un graphe revient aussi à rechercher un stable dans le graphe complémentaire. Ce dernier graphe s'obtient en enlevant les arêtes du graphe G et en rajoutant toutes les arêtes reliant les sommets, qui n'y étaient pas.

NP-complétude[modifier | modifier le code]

La NP-dureté du problème de la clique résulte directement de la NP-dureté du problème du « stable », parce que dire qu'un graphe contient une clique de taille k, revient à affirmer qu'il existe un stable de cardinal k dans le graphe complémentaire : en effet, si un sous-graphe est complet, le sous-graphe complément n'a pas d'arêtes.

On peut aussi passer par 3-SAT.

Algorithmes[modifier | modifier le code]

La recherche exhaustive d'une k-clique à l'intérieur d'un graphe procédera par examen de tous les sous-graphes de taille k, en testant s'ils forment une clique. Toutefois, le nombre de sous-graphes de taille k dans un graphe à n sommets peut être très élevé : il est égal à .

Une heuristique consiste à considérer chaque sommet comme une 1-clique (une clique de cardinal 1), et à former des cliques de tailles croissantes par réunion de deux cliques connues jusqu'à ce qu'il n'y ait plus de réunion possible. On pourra réunir deux cliques A et B si tout sommet de la clique A est adjacent à chaque sommet de la clique B. Cette heuristique s'exécute à un coût linéaire (fonction linéaire du nombre de sommets du graphe), mais elle peut passer à côté d’une grande clique, parce que deux ou plusieurs sommets de cette « clique intéressante » auront déjà été regroupés à une étape antérieure avec des sommets qui n'appartiennent pas à cette clique. On peut mettre en œuvre avantageusement cet algorithme grâce à la stratégie « Union-Find ».

Certains cas particuliers peuvent être résolus à un coût sous-exponentiel. Pour k = 3, il existe un algorithme de complexité O(n1.41) où n est le nombre de sommets du graphe[1].

Histoire[modifier | modifier le code]

Le problème de décision associé à celui de la clique maximum fait partie des 21 problèmes NP-complets de Karp publiés en 1972 dans Reducibility Among Combinatorial Problems[2]. L'article didactique de Cook sur les problèmes NP-complets le mentionne aussi.

Notes et références[modifier | modifier le code]

  1. Le « problème de la k-clique », consistant à établir s'il y a, ou pas, une « k-clique » dans un graphe donné G de taille n, est de coût exponentiel en k (et non exponentiel en n, ordre du graphe G) ; cf. à ce sujet N. Alon, R. Yuster et U. Zwick, « Finding and counting given length cycles », Algorithmica, vol. 17,‎ , p. 209-223 (DOI 10.1007/BF02523189, lire en ligne).
  2. (Karp 1972).

Bibliographie[modifier | modifier le code]

  • (en) Stephen A. Cook, « The Complexity of Theorem-Proving Procedures », dans Proceedings of the Third Annual ACM Symposium on Theory of Computing, Shaker Heights, Ohio, (lire en ligne), p. 151-158
  • (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103
  • (en) Michael R. Garey et David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, vol. A1.2: GT19, W.H. Freeman, (ISBN 0-7167-1045-5), p. 194