Find maximal clique consisting of at least half of the vertices

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.

• A graph $G=(V,E)$ has a $k$-clique if and only if $K_{|V|} \bowtie G$ has a $k+|V|$-clique. Jan 7, 2021 at 2:17
• Can you elaborate on this? I am not familiar with this notation.
– mgus
Jan 7, 2021 at 6:17
• It's just to show that it is NP-complete. $G_1 \bowtie G_2$ is intended to mean the graph join, i.e. the graph on vertex set $V(G_1) \cup V(G_2)$ with edges $E(G_1) \cup E(G_2) \cup \{ v_1v_2 \mid v_1 \in V(G_1) \text{ and } v_2 \in V(G_2) \}$. Jan 7, 2021 at 10:07

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

• Thanks for the resource. I will look more into it soon. But, I have a quick question regarding the preprocessing optimization. Do you think of the removal as a BFS or a DFS? In other words, say that you remove $v$ since it has degree $<c-1$. Assume that, after this removal, a neighbor $u$ of $v$ has also degree $<c-1$ and you remove it too. Then, do you continue with other neighbors of $u$ (BFS) or other neighbors of $v$ (DFS)?
– mgus
Jan 7, 2021 at 19:10
• @mgus It doesn't matter, whenever a vertex gets a degree $\lt c-1$, remove it and keep that graph erosion process going until there are no more vertices below the boundary. The order of removals won't change the output. The algorithm presented in the paper applies indirectly such erosion by applying a "min degree ordering" on the vertices before doing the actual maximum clique searching. Jan 8, 2021 at 2:08

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.