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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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