Résolution indépendante définie à travers la couverture de sommet

Question

J'ai un problème d'ensemble indépendant, dans lequel je dois vérifier si le graphe donné a une taille de taille $ k $ .J'ai déjà écrit un algorithme de couverture de sommet un algorithme et j'espère pouvoir y réutiliser ici.Ces algorithmes sont étroitement liés, car si graphique $ g= (v, e) $ a une taille $ k $ iff il a VC de taille $ v - k $ .Alors suis-je raison que je puisse simplement utiliser mon algorithme VC avec $ k '= v - k $ ?

J'ai lu Ce et Ce question et après que j'ai commencé à douter que c'est aussi simple.

Answer 1

C'est aussi simple que ces questions parlent de paramètres fixes algorithmes traitables de paramètres W.R.T.La taille $ k $ d'une couverture indépendante Set / Vertex.Votre algorithme fonctionnera juste un bon réglage $ k '= | v |- K $ .Clairement, la nouvelle valeur $ k '$ affecte également la durée d'exécution de votre algorithme.