1
$\begingroup$

What's the time complexity of the clique problem for input graphs where each connected component has size at most $3\log|V|$? Is it in P?

$\endgroup$
  • $\begingroup$ Yes it is in P for any constant $c$. What you are basically saying is that your graph has logarithmic size of the input, and then we allow (single) exponential time in the size of the actual data we use, which turns out polynomial in $n$. For any $c$, we have that $2^{O(c \log n)} = n^{O(1)}$. $\endgroup$ – Pål GD May 6 '13 at 22:30
5
$\begingroup$

Indeed, it is:

Consider the input $G,k$. First, it is easy to verify that the sizes of the connected components are as required. Now, if $k>3\log |V|$, then clearly there is no clique of size at least $k$.

Otherwise, we can find the maximal clique in each component by considering all the subsets of the component.

For a component of size $3\log |V|$, there are $2^{3\log |V|}=|V|^3$ possible subsets of vertices. Once we identified the maximal clique in each component, we can compare this size to $k$, and return the answer.

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