• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

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

Optimization Letters. 2014. Vol. 8. No. 5. P. 1611-1617.
Buchanan A., Walteros J. L., Butenko S., Pardalos P. M.

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy d. The algorithm runs in O(nm+nTd) time, where Td is the time to solve the maximum clique problem in an arbitrary graph on d vertices. The best bound as of now is Td=O(2d/4)by Robson. This shows that the maximum clique problem is solvable in O(nm) time in graphs for which d≤4log2m+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 2O(√n)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.