Nombre minimum de sommets dont la suppression fait du graphe un ensemble indépendant

Question

On sait que trouver un ensemble indépendant (ou une clique) de taille au moins $k$ dans un graphique est $W[1]$ difficile, il est donc peu probable qu'il y ait $f(k)\cdot n^{O (1)}$ algorithme de temps pour trouver un ensemble indépendant de taille supérieure à $k$.

Je regardais le problème complémentaire - "Si la suppression ou non d'au plus $k$ sommets d'un graphique peut faire du graphique résultant un ensemble indépendant".

Si le graphe d’entrée $G$ contient un ensemble $W$ de taille au plus $k$ pour dont $V(G)\setminus W$ est un ensemble indépendant, alors il peut être trouvé dans $2^{O(k \log k)}\cdot n^{O(1)}$ temps comme suit :

1. Puisque les sommets d'un ensemble indépendant ont un degré d'au plus $k$, nous supprimons d'abord de $G$ tous les sommets dont le degré est supérieur à $k$.
2. Il n'y a plus que $k^2$ arêtes dans le graphique actuel.
3. Soit $A$ de tous les sommets sur lesquels au moins une arête est incidente, alors $V(G)\setmoins A$ est un ensemble indépendant de taille à moins $(n-2k^2)$.
4. Donc $W$ doit être contenu dans un ensemble $A$ dont la taille est d'au plus 2k^2$.Nous pouvons balayer tous les sous-ensembles ${2k^2}\choose{k}$ de A pour vérifier la suppression dont l’ensemble fait du graphe un ensemble indépendant.

Ma question est la suivante : le nouveau problème a-t-il un algorithme de temps $2^{O(k)}\cdot n^{O(1)}$ ?