Algorithme de recherche exhaustif Résolution de la couverture de sommet de taille $ k $ dans le temps $ 2 ^ {k} n ^ {o (1)} $?

Question

Dans la page wiki de Couverture de sommet, on prétend qu'un algorithme de recherche exhaustif peut résoudre le problème (la version de décision du problème de couverture du sommet) dans le temps 2 ^ {k} n ^ {o (1)} $.

Intuitivement, avec un paramètre fixe $ k $, dans le pire des cas, la recherche exhaustive doit vérifier si chaque sous-ensemble de sommet de taille $ k $ est une couverture de sommet. Le nombre de sous-ensemble de sommets de taille $ k $ est $ dbinom {n} {k} $, et nous avons $ dbinom {n} {k} = o (n ^ {k}) $. En attendant, le nombre d'étapes pour vérifier un sous-ensemble de sommet de taille $ k $ est $ o (kn) $, car nous devons seulement vérifier si le nombre de bord connectés ou contenu dans le sous-ensemble Vertex est $ m $, où $ M $ est le nombre de bord dans le graphique. Ainsi, la complexité temporelle de la recherche exhaustive est $ o (kN ^ {k + 1}) $.

Y a-t-il un problème avec mon analyse ci-dessus? Et comment obtenir un algorithme de recherche exhaustif de la complexité du temps 2 ^ {k} n ^ {o (1)} $?