Réduire $ clique $ de la décision à la recherche du problème

Question

Considérez la langue: $$ clique = Left { langle g, k Hangle | text {$ g $ est un graphique contenant une clique de taille au moins $ k $} droite } $$

Supposons qu'il y ait un algorithme de temps polynomial pour $ clique $. J'ai besoin de montrer un algorithme de temps polynomial pour trouver une clique de taille $ k $.

Maintenant, l'idée est assez facile s'il n'y a qu'une seule clique dans le graphique - vous supprimez chaque sommet $ v_i $ et requête pour $ clique (g_i, k) $.

S'il y a deux cliques dans le graphique cet algorithme ne pouvait pas être appliqué car peu importe quel sommet sera supprimé, il y aura toujours une clique de taille $ k $.

Une alternative serait de supprimer chacun des $ {m} choisir {k} $ mais si $ k = n / 2 $ par exemple, ce ne serait plus un algorithme de temps polynomial.

Ma question est donc: pouvons-nous résoudre ce problème pour le cas général où il pourrait y avoir plusieurs cliques?