This approach works because the 'real' graphs used are very sparse and the maximum clique size is tiny. (in the examples in the original post, the largest cliqu

This approach works because the 'real' graphs used are very sparse and the maximum clique size is tiny. (in the examples in the original post, the largest clique size over all the graphs is 6) See also: http://en.wikipedia.org/wiki/Treewidth http://en.wikipedia.org/wiki/Treewidth