0
$\begingroup$

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$

$\endgroup$

closed as off-topic by Emil Jeřábek, 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, David Eppstein, Kaveh, Lev Reyzin
If this question can be reworded to fit the rules in the help center, please edit the question.

3
$\begingroup$

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.

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