La complejidad del tiempo de la cubierta del vértice vs la clique para Kiand K

Question

Tengo 2 formas de resolver el problema de conjunto independiente del tamaño fijo $ k $ para gráfico $ g= (v,E) $ :

- Algoritmo de la cubierta del vértice que se ejecuta en $ o ^ * (1.47 ^ {v - k}) $ (algoritmo recursivo optimizado)
- Algoritmo de clique que se ejecuta en $ o ({v \ elegir k}) $ (subconjuntos enumerados simples de $ v $ y compruebe algoritmo)

¿Cómo puedo determinar cuál tiene una complejidad de menor tiempo?No estoy muy familiarizado con los algoritmos para problemas completos de NP y $ o ^ * $ notación.¿Plazar las funciones son suficientes?Creo que el algoritmo VC puede tener cualquier polinomio $ n ^ {O (1)} $ como multiplicación debido a la $O ^ * $ notación y esto podría afectar los tiempos de funcionamiento, pero no estoy seguro.

Answer 1

para cualquier $ k $ , $ o (\ binom {v} {k})= O (v^ k) $ es polinomio, mientras que $ o ^ * (1.47 ^ {vk})= o ^ * (1.47 ^ v) $ es exponencial.Los exponenciales crecen mucho más rápido que los polinomios.

PLUNTLE Las curvas no son tan útiles, ya que estas son declaraciones asintóticas.

Dicho esto, si está interesado en particular $ v $ y $ k$ , entonces su mejor opción es verificar empíricamente cuál de estos algoritmos es más rápido.La notación asintótica no es útil aquí, ya que oculta factores constantes, y estos podrían hacer una gran diferencia para los valores concretos de $ v $ y $ k $ .

Answer 2

La cubierta del vértice es un parámetro fijo. Tractable. Hay un simple $ 2 ^ k n $ algoritmo para encontrar un VC de tamaño $ k $ . Esto debería superar el algoritmo ingenuo. El estado actual de la técnica es algo así como $ 1.24 ^ k n $ .

bajo algunas suposiciones No hay algoritmo para k clique con tiempo de ejecución $ f (k) n ^ c $ .

Si su gráfica tiene alguna estructura especial, los resultados pueden mejorarse.