Find maximal clique consisting of at least half of the vertices
Each time you remove a vertex $v$ with degree $&lt;c−1$, the degree of all its neighbours will be reduced by 1, so if any neighbor $u$ gets a degree $&lt;c−1$ after removing $v$, remove $u$ as well; don't stop on $v$. Once you are done you will get what is called the ($c−1$)-core of the graph, which is the induced subgraph where all of its vertices has a degree $\geq c−1$. The maximum clique will be a subset of such core.
Besides that, $c$ is just a lower bound on the maximum clique size, which doesn't change the fact your problem is NP-hard but over a much tinier graph (if you are minimally lucky).
Also, given the maximal $d$ such as the $d$-core exists (the degeneracy of the graph), $d+1$ is an upper bound to the maximum clique size.
With $c$ and $d+1$ as bounds, your maximal clique will probably be found very efficiently by the algoritm introduced in this paper, where all of the above is explained very well (there are a link to github with the implementation in C++): http://www.optimization-online.org/DB_FILE/2018/07/6710.pdf
If you have remove enough vertices, maybe your $c$, which is at least a 50% in the original graph, becomes even higher after the previous erosion of the graph, so you could start looking for algorithm variants specialized for dense graphs.