Risolvere indipendente set attraverso il coperchio del vertice

Question

Ho un problema fisso indipendente, in cui devo controllare se il grafico specificato ha un è di determinati dimensioni $ k $ .Ho già scritto un algoritmo di copertura vertice un po 'indietro e spero di poterlo riutilizzare qui.Questi algoritmi sono strettamente correlati, poiché se il grafico $ g= (V, e) $ ha è di dimensioni $ k $ IFF ha VC di dimensioni $ v - k $ .Quindi ho ragione che posso usare il mio algoritmo VC con $ k '= v - k $ ?

Ho letto Questo e Questo Domanda e dopo aver iniziato dubitando che questo è così semplice.

Answer 1

È così semplice, quelle domande parlano di algoritmi di tratti di parametro fisso w.r.t.La dimensione $ k $ di una copertura set / vertice indipendente.Il tuo algoritmo funzionerà solo per impostazione fine $ K '= | V |- K $ .Chiaramente, il nuovo valore $ k '$ influisce anche sul tempo di esecuzione del tuo algoritmo.