Lösen des unabhängigen Satzes durch Scheitelpunkt

Question

Ich habe ein unabhängiges Set-Problem, in dem ich prüfen muss, ob ein Diagramm ein Diagramm hat, der eine der angegebenen Größe $ k $ hat.Ich habe bereits einen Scheitelpunkt-Cover-Algorithmus ein bisschen zurückgeschrieben, und ich hoffe, ich kann es hier wiederverwenden.Diese Algorithmen sind eng miteinander verbunden, da Grafik Math-Container "> $ g= (v, e) $ hat, hat Größe $ K $ iff Es verfügt über VC der Größe $ V - K $ .Ich bin also richtig, dass ich meinen VC-Algorithmus mit $ k '= v - k $ verwenden kann?

Ich habe dies und dieses Frage und danach habe ich mit dem Zweifel, dass dies so einfach ist.

Answer 1

Es ist so einfach, dass diese Fragen über feste Parameter-traktable Algorithmen w.r.t sprechen.Die Größe $ K $ eines unabhängigen Set / Scheitelpunktabdeckels.Ihr Algorithmus funktioniert nur eine gute Einstellung $ k '= | V |- K $ .Der neue Wert $ k '$ beeinflusst auch die Laufzeit Ihres Algorithmus.