Resolviendo el conjunto independiente a través de la cubierta del vértice

Question

Tengo un problema de conjunto independiente, en el que tengo que verificar si la gráfica dada tiene un tamaño dado $ k $ .Ya he escrito un algoritmo de la cubierta de vértices mientras vuelve y espero poder reutilizarlo aquí.Esos algoritmos están estrechamente relacionados, ya que si el gráfico $ g= (v, e) $ tiene es de tamaño $ k $ IFF Tiene VC de tamaño $ v - k $ .Entonces, ¿tengo razón para que puedo usar mi algoritmo VC con $ k '= v - k $ ?

He leído este y este Pregunta y después de eso he empezado a dudar de que esto es tan simple.

Answer 1

Es tan simple, esas preguntas están hablando de algoritmos tractables de parámetros fijos W.R.T.El tamaño $ k $ de una cubierta de conjunto / vértice independiente.Su algoritmo funcionará con el ajuste fino $ k '= | v |- k $ .Claramente, el nuevo valor $ k '$ también afecta el tiempo de ejecución de su algoritmo.