Algoritmo per trovare cricche

Question

Dato un grafico arbitrario non indiretto $ g = (v, e) $, sono interessato a un algoritmo di tempo a basso polinomiale che può trovare diversi vertici moderatamente grandi (idealmente $ o (n^ epsilon) $ vertici per cricca per $ epsilon> 0 $) cricche in $ g $, a condizione che esistano.

Sono consapevole che il problema di trovare la cricca massima è np-hard. Per i miei scopi, tuttavia, non ho bisogno di massima per dire. Piuttosto, sarebbe utile avere un algoritmo che funziona relativamente rapidamente e con elevata probabilità trova alcune cricche non banali.

Sono consapevole che per $ k $ $, trovare una cLique $ k $ se esiste può essere fatto in $ n^k $ tempo semplicemente testando tutti i sottoinsiemi di $ k $ vertici. Questo algoritmo sembra essere di uso limitato a causa della crescita esponenziale in $ k $.

Esistono un algoritmo o multiplo che può, con elevata probabilità, trovare più cricche moderatamente grandi in un grafico generale non indirizzato?