Re^3: Sub set where all are connected

If you are really looking for cliques - i.e. complete sub-graphs - than my approach won't be of great help. (Though not useless in reducing complexity)

> I expect cliques of hundreds of members, if not thousands.

Wait ... How many nodes does your graph have?

😳

Probably you are better off investigating the complement graph.

You could also sort all nodes by the number of their neighbours.

An n-clique is only possible if there are at least n nodes with at least n-1 neighbors.

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery
FootballPerl is like chess, only without the dice}

Comment on Re^3: Sub set where all are connected

Replies are listed 'Best First'.
Re^4: Sub set where all are connected by Sanjay (Sexton) on Nov 29, 2019 at 15:11 UTC
The average number of nodes in a "problem set" is around 15. The maximum is around 100,000++. Currently my project has about 37,000 problem sets.	[reply]
Re^5: Sub set where all are connected by LanX (Saint) on Nov 29, 2019 at 15:23 UTC
Try the approach described here Re^3: Sub set where all are connected for the "average" case. The complexity depends on (is related to) the max size of a clique. So better be prepared to kill long calculations with a timeout. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery FootballPerl is like chess, only without the dice}	[reply]