I know that the clique problem is NP-complete.

However, what if we change the problem a little bit?

For example,

Given a graph $G(V,E)$, an integer $k$ and a subset $S$ of $m$ vertices, we are given a decision problem to find a clique with size $k$ contained within $S$.

A real world example would be something like a social networking graph. Where each node is a person and an edge represents that they are friends with each other. Now what if we were to find clique with size $k$ amongst the set of teenagers.

Does that change the complexity? Since we are only looking into a subgraph, e.g. less vertices to look for?


  • 1
    $\begingroup$ I don't understand what you mean by "only have to look into $m$ vertices". But, since you've not excluded the possibility that $m=|V|$, the new problem includes the standard clique problem as a sub-problem. So the new problem is NP-complete, too. $\endgroup$ – David Richerby Aug 2 '15 at 9:05
  • $\begingroup$ thats the part that i was confused about, for example, what if the total number of vertices are 10, and m = 3, then does it change the problem? however, m does not need to be a constant. It varies in every question. $\endgroup$ – Mark Aug 2 '15 at 14:58
  • $\begingroup$ Sure, $m$ could be less than $|V|$ but any algorithm that solves your problem (whatever that problem is -- I still can't understand it) still has to be able to deal with the case where $m=|V|$. If it can solve the case $m=|V|$, then it can solve the standard clique problem. If it can solve the standard clique problem, it's NP-hard. $\endgroup$ – David Richerby Aug 2 '15 at 15:19
  • $\begingroup$ it makes sense now. should i add details to the question? or are you gonna withdraw the hold? thanks! $\endgroup$ – Mark Aug 3 '15 at 15:34
  • $\begingroup$ I still don't understand what problem you're trying to solve when $m\neq|V|$ so, to me, the question is still very unclear. I can't take the hold off unilaterally but, if you edit the question to clarify it, a vote will begin automatically. $\endgroup$ – David Richerby Aug 3 '15 at 16:02

Formally, time complexity is defined as

Let T : N → N. A Turing Machine M has time complexity T(n) if $∀ x ∈ \{0, 1\}^*$ , M(x) halts in at most T(|x|) steps.

That is to say, time complexity captures the (relative) amount of time taken for all inputs.

Thus the answer is no, that doesn't change the time complexity at all, because then you would just have an instance of the question: Given a graph $G(V',E)$, where $|V'| = m$, and an integer, $k$, determine if a clique with size $k$ exists.

As $m$ increases, the running time would increase in the way similar to how it would if |V| increases in the original problem.

However, if $m$ is defined to be a constant, then the time-complexity would be $O(1)$ (the TM would halt in at most x steps no matter what the graph is) but the problem itself would not make any sense

Given a graph G(V,E), and k-integer, determine if a clique with size k exists after checking m vertices, where m is a constant.

because a decision problem is formally defined in terms of set-membership, and a different algorithm (a different way to finding if a clique exists) would yield a different result, for $|V| > m$.

| cite | improve this answer | |

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