Ridurre $ cricca $ dalla decisione di cercare problemi

Question

Considera la lingua: $$ clique = left { langle g, k rangle | text {$ g $ è un grafico contenente una clique di dimensioni almeno $ k $} destra } $$

Supponiamo che ci sia un algoritmo di tempo polinomiale per $ cricca $. Devo mostrare un algoritmo di tempo polinomiale per trovare una cricca di dimensioni $ k $.

Ora, l'idea è abbastanza semplice se c'è solo una cricca nel grafico: rimuovi ogni vertice $ v_i $ e query per $ clique (g_i, k) $.

Se ci sono due cricche nel grafico questo algoritmo non poteva essere applicato poiché non importa quale vertice verrà rimosso ci sarà sempre una cricca di dimensioni $ k $.

Un'alternativa sarebbe rimuovere ognuno di $ {M} Scegli {k} $ ma se $ k = n/2 $ ad esempio, non sarebbe più un algoritmo del tempo polinomiale.

Quindi la mia domanda è: possiamo risolvere questo problema per il caso generale in cui potrebbero esserci più cricche?