Assume that we are given an undirected graph $G$ of n vertices. For this graph, we also know that there is a clique of size $c$, for some $c\geq \lfloor n/2 + 1\rfloor$. In other words, the majority of the vertices will belong to this clique. This clique may or may not be maximal; however, given these assumptions it will definitely be a subgraph of the maximum clique of $G$.
My goal is to find the most efficient algorithm to find the maximum clique of the graph. If the maximum clique is not unique, finding one of them is fine.
In general, $G$ won't be planar or perfect graph and to the best of my knowledge there is no exponential or linear-time algorithm to solve this problem.
I thought that, one way is to do an exhaustive search of all $n\choose c$ induced subgraphs until I find a clique $C$. Then, one can keep adding vertices to $C$ such that they connect to all vertices currently in $C$ until this clique cannot be enlarged anymore. Then, $C$ will be one maximum clique. Assuming that $n$ is not too large, maybe $n < 50$, do you think that this is a reasonable method given that $n\choose c$ is large? Is there a more efficient algorithm?
One small optimization is to exclude all vertices with degree $< c-1$ from consideration.