Not examined the number of edges. As a wild guess I would say the 100,000 node case may have 200,000 to 400,000 edges. Ever since I learnt that it is a hard problem, I lost interest. I am using another method (linear programming) to get (sub)-cliques optimized to maximize some objective function. Works for around 98+% cases. Times out or unfeasible for the rest because of problems with the (free) software or insufficient resources. I was thinking of cliques to offer an alternative solution. Now I will specify that an optimized solution cannot be found. Good luck to my client!