My naive maximum click algorithm is faster than Bron Kerbosch. What's wrong?

Question

In short, my naive code (in Ruby) looks like this:

# $seen is a hash to memoize previously seen sets # $sparse is a hash of usernames to a list of neighboring usernames # $set is the list of output clusters $seen = {} def subgraph(set, adj) hash = (set + adj).sort return if $seen[hash] $sets.push set.sort.join(", ") if adj.empty? and set.size > 2 adj.each {|node| subgraph(set + [node], $sparse[node] & adj)} $seen[hash] = true end $sparse.keys.each do |vertex| subgraph([vertex], $sparse[vertex]) end 

And my implementation of Bron Kerbosch:

 def bron_kerbosch(set, points, exclude) $sets.push set.sort.join(', ') if set.size > 2 and exclude.empty? and points.empty? points.each_with_index do |vertex, i| points[i] = nil bron_kerbosch(set + [vertex], points & $sparse[vertex], exclude & $sparse[vertex]) exclude.push vertex end end bron_kerbosch [], $sparse.keys, [] 

I also tweaked the rotation and degeneration, which reduced the runtime of bron_kerbosch, but not enough to overtake my original solution. That seems to be the case; What kind of algorithmic insight do I miss? Below is a writeup with more details if you need to see fully working code. I tested this on pseudo-random settings up to a million or so in size.

Answer 1

I don’t know how you generate random graphs for your tests, but I assume that you are using a function that generates a number according to the uniform distribution, and thus you get a graph that is very uniform. This is a common problem when testing algorithms on graphs, it is very difficult to create good test cases (this is often as difficult as solving the original problem).

The max-clique problem is a well-known NP problem, and both algorithms (naive and Bron Kerbosch) have the same complexity, so we cannot expect global improvement in all test scenarios, but simply improvements for some special cases. But since you used uniform distribution to generate your schedule, you do not have this particular case.

This is why the performance of both algorithms is very similar to your data. And since the Bron Kerbosch algorithm is a bit more complicated than the naive, the naive is faster.