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

abstract

  • We describe an algorithm for the maximum clique problem that is parameterized by the graph's degeneracy d. The algorithm runs in O(nm+n Td) 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 4 log2 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 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. 2013 Springer-Verlag Berlin Heidelberg.

published proceedings

  • Optimization Letters

author list (cited authors)

  • Buchanan, A., Walteros, J. L., Butenko, S., & Pardalos, P. M.

citation count

  • 15

complete list of authors

  • Buchanan, Austin||Walteros, Jose L||Butenko, Sergiy||Pardalos, Panos M

publication date

  • June 2014