<p>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.</p>

CC BY-SA 3.0
2017-06-06T13:03:10.387Z
If we solve **Restricted** **$k$-clique** problem then we can solve $k$-clique problem. But not other way round.
GOLD
CC BY-SA 3.0
2017-06-06T13:08:44.350Z
The much easier problem of approximating Clique itself is NPComplete ( http://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.
TheoryQuest1
CC BY-SA 3.0
2017-06-06T13:16:55.080Z
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$.
holf
CC BY-SA 3.0
2017-06-06T13:18:42.097Z
I should have put it that way. Much more accessible.
TheoryQuest1
CC BY-SA 3.0
2017-06-06T12:53:19.843Z
2017-06-06T14:04:42.113Z
2017-06-06T14:04:42.113Z
TheoryQuest1
<p><strong>Restricted</strong> <strong>$k$-clique:</strong></p>

<p><strong>Input:</strong> $(G,v,k)$ where $v$ is vertex in $V$</p>

<p><strong>Output:</strong> k-clique containing vertex $v$. </p>

<p>What is the space and time complexity status of this <strong>Restricted</strong> <strong>$k$-clique</strong> problem? </p>

<p>Is it same as <strong>$k$-clique</strong> problem?</p>

<p>I trying to show this problem is in $L$ or $NL$ </p>

<ds.algorithms><graph-algorithms><time-complexity><space-complexity><logspace>
Complexity status of restricted k-clique
GOLD
# Complexity status of restricted k-clique

(Asked by: username_0 on 2017-06-06)

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

**Tags:** ds.algorithms, graph-algorithms, time-complexity, space-complexity, logspace

---

## 1 answers

### Answer by username_1 on 2017-06-06. Score: 3

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.

> **Comments:**
> **username_0**: If we solve **Restricted** **$k$-clique** problem then we can solve $k$-clique problem. But not other way round.  
> **username_1**: The much easier problem of approximating Clique itself is NPComplete ( http://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.  
> **username_2**: 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$.  
> **username_1**: I should have put it that way. Much more accessible.  

---

