1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.