Resolvendo o conjunto independente através da tampa do vértice

Question

Eu tenho um problema de conjunto independente, no qual eu tenho que verificar se o gráfico fornecido tem um é de determinado tamanho $ k $ .Eu já escrevi um algoritmo de cobertura de vértice por um tempo atrás e espero que eu possa reutilizá-lo aqui.Esses algoritmos estão intimamente relacionados, desde que se gráfico $ g= (v, e) $ tem é de tamanho $ K $ IFF Tem vc de tamanho $ v - k $ .Então eu estou certo que eu posso apenas usar meu algoritmo VC com $ k '= v - k $ ?

Eu li e pergunta e depois disso comecei a duvidar de que isso é tão simples.

Answer 1

É tão simples, essas perguntas estão falando sobre algoritmos tratáveis de parâmetros fixos w.r.t.O tamanho $ k $ de uma tampa independente de conjunto / vértice.Seu algoritmo funcionará apenas bem definindo $ k '= | v |- K $ .Claramente, o novo valor $ k '$ também afeta o tempo de execução do seu algoritmo.