Algorithme pour trouver des cliques

Question

Étant donné un graphique non dirigé arbitraire $ g = (v, e) $, je suis intéressé par un algorithme de temps à faible polynomial qui peut trouver plusieurs sommets modérément grands (idéalement $ o (n ^ epsilon) $ vertices par clique pour $ epsilon> 0 $) Cliques en $ G $, à condition qu'ils existent.

Je suis conscient que le problème de la recherche de la clique maximale est durs NP. Pour mes besoins, cependant, je n'ai pas besoin de maximalité par exemple. Il serait plutôt utile d'avoir un algorithme qui fonctionne relativement rapidement et avec une forte probabilité trouve des cliques non triviales.

Je suis conscient que pour Fixed $ k $, trouver un $ k $ -clique s'il existe peut être fait en $ N ^ k $ en testant simplement tous les sous-ensembles de Vertices $ k $. Cet algorithme semble être limité en raison de la croissance exponentielle de $ k $.

Existe-t-il un algorithme ou plusieurs qui peuvent, avec une forte probabilité, trouver plusieurs cliques modérément grandes dans un graphique général non dirigé?