Fast Algorithms for the Maximum Clique Problem on Massive Sparse Graphs
This addresses the challenge of efficiently solving an NP-hard problem for large-scale data in fields like data mining and network analysis, representing a strong specific gain rather than an incremental improvement.
The researchers tackled the maximum clique problem on massive sparse graphs by developing a new exact algorithm with novel pruning techniques, achieving up to several orders of magnitude faster performance than existing algorithms in experiments on synthetic and real-world graphs.
The maximum clique problem is a well known NP-Hard problem with applications in data mining, network analysis, informatics, and many other areas. Although there exist several algorithms with acceptable runtimes for certain classes of graphs, many of them are infeasible for massive graphs. We present a new exact algorithm that employs novel pruning techniques to very quickly find maximum cliques in large sparse graphs. Extensive experiments on several types of synthetic and real-world graphs show that our new algorithm is up to several orders of magnitude faster than existing algorithms for most instances. We also present a heuristic variant that runs orders of magnitude faster than the exact algorithm, while providing optimal or near-optimal solutions.