# What is the complexity of k-clique problem with a predetermined vertex in the solution?

Clique (from WikiPedia):

Clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete.

K-Clique problem: Finding a clique of size K. This is NP-complete according to Wiki,

Cliques have also been studied in computer science: finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.

Let us consider a "constrained k-clique problem" - which is a k-clique problem with a constraint of having a predetermined vertex included in the solution. What would be the complexity of this problem? Is it a known problem in the literature?

It is still $$\mathsf{NP}$$-complete. Consider the following reduction from the normal $$\mathrm{Clique}$$ problem: Given a graph $$G$$ and some desired clique size $$k$$, add a new vertex $$v^\ast$$ which is connected to all vertices of $$G$$ to obtain a new graph $$G^\ast$$. Then $$(G^\ast, k + 1, v^\ast)$$ is a yes-instance of your modified $$\mathrm{Clique}$$ problem if and only if $$(G, k)$$ is a yes-instance of $$\mathrm{Clique}$$.