How to find the "largest" complete subgraph in a graph?

Question

Algorithms

In other words, there is a set of points (between 250,000 and 1,000,000) that are randomly related. Among these points, you need to find such N points, each of which is connected with the remaining N-1 points, while N is maximum.

Answer 1

This is a regular task, the so-called. clique problem, NP-complete. There is nothing better than improved enumeration.
https://en.wikipedia.org/wiki/Bron_—_Kerbosh's_algorithm

Answer 2

Find all subgraphs, choose the largest one.

Answer 3

This can be done with depth first search in linear time. Select a vertex, dfs from it marking the vertices as 0, then select another (not yet labeled) vertex, and so on. Simultaneously keep track of the number of vertices in each subgraph.

Answer 4

Hmm, apparently the wrong decision (greedy) was thought up. But wondering where the problem is.
UPD: I understand where the problem is.
Lemma 1 Two complete non-intersecting subgraphs (without common vertices) of size m and n, respectively, between the vertices of which there are m*n edges, form a complete subgraph with m*n vertices.
We cram all the vertices into the SNM (System of Disjoint Sets). Each vertex is a complete subgraph of size 1. Further, in the process of traversal, we "merge" the complete subgraphs.
To do this, we store map: (subgraph1, subgraph1) -> numOfConnections. Each time we encounter an edge, we use CHM to find which subgraphs the vertices belong to and increase the value in the map (or add one if there was no key). If the value turned out to be greater than the product of the sizes of the subgraphs, we merge them.
UPD: the problem with the greedy algorithm is that we will not get the maximum subgraph. Sometimes doing another merger is not profitable. For example, there is a small subgraph A, and 2 large ones B and C. B can be merged with C or with A, but all 3 do not form a complete graph. Then if we merge B and A, then the optimal solution will no longer work.