Numero minimo di vertici la cui rimozione rende il grafico un set indipendente

Question

È noto che trovare un set indipendente (o una cricca) di dimensioni almeno $ k $ in un grafico è $ w [1] $ hard, quindi è improbabile che ci sia $ f (k) cdot n^{o (1)} $ algoritmo temporale per trovare un insieme indipendente di dimensioni maggiore di uguale a $ k $.

Stavo guardando il problema complementare - "Se la rimozione dei vertici di $ k $ da un grafico può rendere il grafico risultante un set indipendente".

Se il grafico di input $ g $ contiene un set $ w $ di dimensioni al massimo $ k $ per il quale $ v (g) setminus w $ è set indipendente, allora può essere trovato in $ 2^{o (k log k )} CDOT n^{o (1)} $ tempo come segue:

1. Poiché i vertici del set indipendente hanno una laurea al massimo $ k $, rimuoviamo per la prima volta da $ g $ tutti i vertici la cui laurea è più di $ k $.
2. Ora ci sono solo $ k^2 $ bordi nel grafico corrente.
3. Lascia che $ A $ sia impostata di tutti i vertici su cui almeno un vantaggio è incidente, quindi $ v (g) setminus a $ è un set indipendente di dimensioni almeno $ (n-2k^2) $.
4. Quindi $ w $ deve essere contenuto nel set $ a $ la cui dimensione è al massimo $ 2k^2 $. Possiamo scansionare su tutti i sottoinsiemi $ {2k^2} seleziona {k} $ di A per verificare la rimozione di quale set rende il grafico un set indipendente.

La mia domanda è che il nuovo problema ha $ 2^{o (k)} CDOT n^{o (1)} $ algoritmo tempo?