[Solved]: Clique decision problem restricted to a subgraph

Problem Detail: 

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?

Thanks!

Asked By : Mark

Answered By : nyan nyan nyan

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44951