# Clique in P when the input graph's connected components have at most $3\log|V|$ vertices?

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?

• 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)}$. May 6, 2013 at 22:30

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