Solving maximum clique in sparse graphs: an O(nm + n2~(d/4)) algorithm for d-degenerate graphs

摘要

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy d. The algorithm runs in O (nm + nT_d) time, where T_d is the time to solve themaximum clique problem in an arbitrary graph on d vertices. The best bound as of now is T_d = O(2~(d/4)) by Robson. This shows that the maximum clique problem is solvable in O(nm) time in graphs for which d ≤ 4 log_2 m + O(1). The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi-Marsili power-law random graphs, it runs in 2~(O(n~(1/2))) time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.