Restricted $k$-clique:

Input: $(G,v,k)$ where $v$ is vertex in $V$

Output: k-clique containing vertex $v$.

What is the space and time complexity status of this Restricted $k$-clique problem?

Is it same as $k$-clique problem?

I trying to show this problem is in $L$ or $NL$


closed as off-topic by Emil Jeřábek supports Monica, David Eppstein, Kaveh, Lev Reyzin Jun 6 '17 at 22:32

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek supports Monica, David Eppstein, Kaveh, Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.


Yes. It is essentially same as the Clique problem. Imagine a clique containing $n$ nodes. Your problem is then asking for a Clique containing $n-1$ nodes, such that all of them are adjacent to vertex $v$. $v$ is connected to all vertices in the graph. The problem is still NPComplete.

  • $\begingroup$ If we solve Restricted $k$-clique problem then we can solve $k$-clique problem. But not other way round. $\endgroup$ – GOLD Jun 6 '17 at 13:03
  • $\begingroup$ The much easier problem of approximating Clique itself is NPComplete ( groups.csail.mit.edu/cis/pubs/shafi/1991-focs-fglss.pdf). And if we consider the largest clique (of size $n$), finding the clique of size $n-1$ is obviously NPComplete. $\endgroup$ – TheoryQuest1 Jun 6 '17 at 13:08
  • 2
    $\begingroup$ What @TheoryQuest1 tries to explain I think is that a $k$-clique in a graph $G$ is exactly a restricted $k+1$-clique containing the vertex $v'$ in the graph $G'$ where $G'$ is obtained from $G$ by adding a fresh vertex $v'$ connected to all vertices of $G$. $\endgroup$ – holf Jun 6 '17 at 13:16
  • $\begingroup$ I should have put it that way. Much more accessible. $\endgroup$ – TheoryQuest1 Jun 6 '17 at 13:18

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