Complexidade de tempo da tampa do vértice vs clique para k

Question

Eu tenho duas maneiras de resolver o problema do conjunto independente do tamanho fixo $ k $ para gráfico $ g= (v,E) $ :
- Algoritmo de capa do vértice em execução em $ o ^ * (1,47 ^ ^ {v - k}) $ (algoritmo recursivo otimizado)
- Algoritmo de clique em execução em $ o ({v \ escolher k}) $ (enumerar subjetos de $ v $ e verificar algoritmo)

Como posso determinar qual deles tem uma complexidade de tempo menor?Eu não estou muito familiarizado com algoritmos para problemas np-completos e $ o ^ * $ notação.Iria traçar essas funções suficientes?Eu acho que o algoritmo VC pode ter qualquer polinômio $ n ^ ^ {O (1)} $ como uma multiplicação por causa da $O ^ * $ Notação e isso pode afetar os tempos de funcionamento, mas não tenho certeza.

Answer 1

Para qualquer $ k $ , $ O (\ binom {v} {k})= o (v^ k) $ é polinomial, enquanto $ o ^ * (1,47 ^ {vk})= o ^ * (1,47 ^ v) $ é exponencial.Exponenciais crescem muito mais rápido do que polinômios.

Plotting As curvas não é tão útil, uma vez que estas são declarações assintóticas.

Dito isto, se você estiver interessado em particular $ v $ e $ K$ , então sua melhor opção é verificar empiricamente quais desses algoritmos é mais rápido.A notação assintótica não é útil aqui, uma vez que esconde fatores constantes, e estes podem fazer uma grande diferença para valores concretos de $ v $ e $ k $ .

Answer 2

A tampa do vértice é tratável de parâmetro fixo. Há uma simples $ 2 ^ k n $ algoritmo para encontrar um VC de tamanho $ k $ . Isso deve bater o algoritmo ingênuo. O estado atual da arte é algo como $ 1,24 ^ k n $ .

Sob algumas suposições Não há algoritmo para K CLIQUE com tempo de execução $ f (k) n ^ c $ .

Se o seu gráfico tiver alguma estrutura especial, os resultados podem ser melhorados.