Time complexity of Vertex Cover vs Clique for fixed k

Question

I have 2 ways of solving Independent Set problem of fixed size $k$ for graph $G = (V, E)$:
- Vertex Cover algorithm running in $O^*(1.47^{V - k})$ (optimized recursive algorithm)
- Clique algorithm running in $O({V\choose k})$ (simple enumerate subsets of $V$ and check algorithm)

How can I determine which one has a lower time complexity? I'm not very familiar with algorithms for NP-complete problems and $O^*$ notation. Would plotting those functions suffice? I think that VC algorithm can have any polynomial $n^{O(1)}$ as a multiplication because of the $O^*$ notation and this could affect the running times, but I'm not sure.

Answer 1

For any fixed $k$, $O(\binom{V}{k}) = O(V^k)$ is polynomial, whereas $O^*(1.47^{V-k}) = O^*(1.47^V)$ is exponential. Exponentials grow much faster than polynomials.

Plotting the curves is not so helpful, since these are asymptotic statements.

That said, if you're interested in particular $V$ and $k$, then your best option is to empirically check which of these algorithms is faster. Asymptotic notation is not helpful here, since it hides constant factors, and these could make a big difference for concrete values of $V$ and $k$.

Answer 2

Vertex Cover is fixed-parameter tractable. There is a simple $2^k n$ algorithm to find a VC of size $k$. This should beat the naive algorithm. The current state of the art is something like $1.24^k n$.

Under some assumptions there is no algorithm for k clique with running time $f(k) n^c$.

If your graph has some special structure the results can be improved.