What algorithm is clique_number using?

Question

What is the algorithm behind python-igraph's clique_number() function? It is obviously not a brute-force method given it's good performance.

Even clicking on the "source code" link does not seem to reveal it. Is this explained somewhere in the documentation?

"It is obviously not a brute-force", don't be so sure. Getting cliques is an NP-complete problem, no polynomial time solution exists. — cs95
– cs95, Commented May 11, 2018 at 20:24
@cᴏʟᴅsᴘᴇᴇᴅ If it was a brute-force method, there would be absolutely no chance for it to finish on million-scale graphs in reasonable time which it currently does, exactly for the reason you mention. — salpha
– salpha, Commented May 11, 2018 at 20:28
Nice, did not know that! Graph modules are a wonderful thing... — cs95
– cs95, Commented May 11, 2018 at 20:30
@cᴏʟᴅsᴘᴇᴇᴅ Indeed :-) Hence, I really wonder what the algorithm used is. It compares very well against branch and bound and other methods as well. — salpha
– salpha, Commented May 11, 2018 at 20:31

Community · Accepted Answer · 2020-06-20 09:12:55Z

1

clique_number corresponds to the C igraph_clique_number, with worst-case complexity O(3^(|V|/3)). igraph_clique_number iterates over all maximal cliques and finds the biggest size.

The algorithm used for finding all maximal cliques is version-dependent. The docs for the related igraph_maximal_cliques say

The current implementation uses a modified Bron-Kerbosch algorithm to find the maximal cliques, see: David Eppstein, Maarten Löffler, Darren Strash: Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. Algorithms and Computation, Lecture Notes in Computer Science Volume 6506, 2010, pp 403-414.

The implementation of this function changed between igraph 0.5 and 0.6 and also between 0.6 and 0.7, so the order of the cliques and the order of vertices within the cliques will almost surely be different between these three versions.

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered May 11, 2018 at 20:41

user2357112

286k32 gold badges490 silver badges571 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

What algorithm is clique_number using?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related