In this question, "graph" means a non-oriented, simple graph with no loop and no label on the edges or vertices.
A clique in a graph $G$ is a complete subgraph of $G$. The clique number $\omega_v(G)$ of a vertex $v$ of $G$ is the maximum of the order (=number of vertices) of all cliques of $G$ that contains $v$.
Is there a good algorithm that computes the clique number of a vector $v$ in a graph?
The graphs I consider are represented by their adjacency matrix, but an algorithm that works on the list of edges of a graph would be fine too.
I know that the clique number $\omega$ of $G$ is the maximum of the order over all cliques in $G$. Therefore, $\omega_v(G)=\omega(N(v))$, where $N(v)$ is the neighborhood of $v$ ($v$ included). Also, the clique number of a graph is the independence number of its complement. But I am not sure whether these information are useful or not.
Best Answer
You've probably already figured out that this problem is NP-hard: if you could solve this problem, then you could find the clique number of a graph $G$ by just adding a vertex $v$ to $G$ and connecting it to all previously existing vertices of $G$, then finally querying what $\omega_v(G \cup v)$ is. The clique number of $G$ would then be $\omega(G \cup v) - 1$.
This gives rise to a nice heuristic (though it can still be very slow). You can first consider the induced subgraph (call it $H$) of $G$ on the vertices $v \cup N(v)$ where $N(v)$ is the neighbors of $v$. Then you could find a maximum clique $C$ for $H \setminus v$ in $O\left(3^{|V(H)| / 3}\right)$ time. Since all vertices in $H \setminus v$ are guaranteed to be connected to $V$, it follows that $C \cup v$ would be a maximum clique in $H$ (and subsequently) a maximum clique in $G$ containing $v$.
Given that the fastest maximum clique-finding algorithms we know run in $O\left(3^{V / 3}\right)$ time, the equivalence of your problem to the maximum clique problem would suggest that the best algorithm known for your problem also runs in $O\left(3^{V / 3}\right)$ time. Otherwise, we would have have just found a faster algorithm for solving the maximum clique problem, via the reduction I outlined in the first paragraph.