Algorithme

Le problème de clique est un problème complet de bien connu $NP$où la taille de la clique requise fait partie de l'entrée. Cependant, le problème de k-clique a un algorithme de temps polynomial trivial ( $O(n^k)$ lorsque $k$ est constant). Je m'intéresse aux bornes supérieures les plus connues lorsque k est constant.

Existe-t-il un algorithme avec le temps d'exécution ? Un algorithme à temps o ( n k ) est également acceptable. De plus, y a-t-il une conséquence théorique à la complexité de l'existence de tels algorithmes?$O(n^{k-1})$$o(n^k)$

A 3-clique peut être trouvée dans un -vertex graphe G dans le temps O ( n ω ) , où ω < 2,376 est l'exposant de multiplication de matrice, et en O ( n 2 ) l' espace par suite de Itai et Rodeh [1] . Fondamentalement, ils montrent que G contient un triangle si et seulement si ( A ( G ) ) 3 a une entrée non nulle sur sa diagonale principale. Parce qu'un triangle est aussi un cycle C $n$$G$$O(n^\omega)$$\omega < 2.376$$O(n^2)$$G$$(A(G))^3$$C_3$, on peut utiliser des méthodes générales de recherche de cycle pour détecter les triangles. Alon, Yuster et Zwick montrent comment les triangles peuvent être détectés sur un graphique à bords en O ( m 2 ω / ( ω + 1 ) ) = O ( m 1,41 ) temps [6].$m$$O(m^{2\omega/(\omega+1)}) = O(m^{1.41})$

Pendant longtemps, le résultat de Nesetril et Poljak [2] a été le plus connu; ils ont montré que le nombre de cliques de taille peut être trouvé dans l' espace temporel O ( n ω k ) et O ( n 2 k ) . Enfin, Eisenbrand et Grandoni [3] ont amélioré le résultat de Nesetril et Poljak pour une clique ( 3 k + 1 ) et une clique ( 3 k + 2 ) pour les petites valeurs de k . Plus précisément, ils ont donné des algorithmes pour trouver des cliques de taille 4, 5 et 7 dans le temps $3k$$O(n^{\omega k})$$O(n^{2k})$$(3k+1)$$(3k+2)$$k$ , O ( n 4,220 ) et O ( n 5,714 ) , respectivement.$O(n^{3.334})$$O(n^{4.220})$$O(n^{5.714})$

Pour autant que je sache, pour le général , le problème de la conception de meilleurs algorithmes est ouvert. Pour les conséquences possibles ou considérations théoriques de complexité, Downey et boursiers (voir par exemple [4]) a montré k -clique avec le paramètre k est - W [ 1 ] -hard. La classe W [ 1 ] désigne la classe des problèmes de décision paramétrés réductibles à CLIQUE avec des réductions paramétrées. On pense que CLIQUE n'est pas traitable à paramètres fixes. Il existe des centaines d'autres problèmes connus pour être équivalents à CLIQUE avec des réductions paramétrées. De plus, Feige et Kilian [5, Section 2] ont un résultat disant que lorsque $k$$k$$k$$W[1]$$W[1]$$k$fait partie de l'entrée et , alors il est peu probable qu'un algorithme de polytime existe.$k \approx \log n$

Si vous considérez certaines classes de graphes restreintes, vous pouvez résoudre le problème en temps linéaire sur des graphes en accords. Calculez simplement un arbre de clique d'un graphe d'accord en temps O ( n + m ) , puis vérifiez si une clique est de taille exactement k . Sur les graphes planaires, on peut également trouver des triangles en temps O ( n ) en utilisant les méthodes de [6].$G$$O(n+m)$$k$$O(n)$

[1] Itai, Alon et Michael Rodeh. "Trouver un circuit minimum dans un graphique." SIAM Journal on Computing 7.4 (1978): 413-423.

[2] Nešetřil, Jaroslav et Svatopluk Poljak. "Sur la complexité du problème des sous-graphes." Commentationes Mathematicae Universitatis Carolinae 26.2 (1985): 415-419.

[3] Eisenbrand, Friedrich et Fabrizio Grandoni. "Sur la complexité de la clique à paramètres fixes et de l'ensemble dominant." Informatique théorique 326.1 (2004): 57-67.

[4] Downey, RG et Michael R. Fellows. "Fondamentaux de la complexité paramétrée." Textes de premier cycle en informatique, Springer-Verlag (2012).

[5] Feige, Uriel et Kilian, Joe. "Sur le Non-Déterminisme Polynomial Limité". Journal de Chicago de l'informatique théorique. (1997)

[6] Alon, Noga, Raphael Yuster et Uri Zwick. "Trouver et compter des cycles de longueur donnés." Algorithmica 17.3 (1997): 209-223.