Find maximal clique consisting of at least half of the vertices

Question

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.

Answer 1

Each time you remove a vertex $v$ with degree $<c−1$, the degree of all its neighbours will be reduced by 1, so if any neighbor $u$ gets a degree $<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.

Answer 2

The problem is NP-hard, so you shouldn't expect any efficient algorithm that will always work. You can look for heuristics, or approximation algorithms, or sometimes-efficient algorithms.

If I had to solve it in practice, probably the first thing I would try would be to use a SAT solver. Introduce a boolean variable $x_v$ for each vertex $v$; then add constraints $x_v \implies x_w$ for each edge $(v,w)$; and add a constraint requiring there to be at least $c$ variables set to true. Ask the SAT solver to find a satisfying assignment.