Efficient algorithms for clique problems
The k-clique problem is a cornerstone of NP-completeness and parametrized complexity. When k is a fixed constant, the asymptotically fastest known algorithm for finding a k-clique in an n-node graph runs in O (n(0.792k)) time (given by Nesetril and Poljak). However, this algorithm is infamously inapplicable, as it relies on Coppersmith and Winograd's fast matrix multiplication. We present good combinatorial algorithms for solving k-clique problems. These algorithms do not require large constants in their runtime, they can be readily implemented in any reasonable random access model. and are very space-efficient compared to their algebraic counterparts. Our results are the following: We give an algorithm for k-clique that runs in O(n(k)/(epsilon log n)(k-1)) time and O(n(epsilon)) space, for all epsilon > 0, on graphs with n nodes. This is the first algorithm to take o(n(k)) time and O(n(c)) space for c independent of k. Let k be even. Define a k-semiclique to be a k-node graph G that can be divided into two disjoint subgraphs U = {u(1),...,u(k/2)} and V = (v(1),...,v(k/2)} such that U and V are cliques, and for all i <= j, the graph G contains the edge {u(i), v(j)). We give an (O) over bar (k2(k)n(k/2+1)) time algorithm for determining if a graph has a k-semiclique. This yields an approximation algorithm for k-clique, in the following sense: if a given graph contains a k-clique, then our algorithm returns a subgraph with at least 3/4 of the edges in a k-clique. (C) 2008 Elsevier B.V. All rights reserved.
algorithms clique combinatorial problems graph algorithms