Fast Solving Maximum Weight Clique Problem in Massive Graphs / 568
Shaowei Cai, Jinkun Lin

This paper explores techniques for fast solving the maximum weight clique problem (MWCP) in very large scale real-world graphs. Because of the size of such graphs and the intractability of MWCP, previously developed algorithms may not be applicable. Although recent heuristic algorithms make progress in solving MWCP in massive graphs, they still need considerable time to get a good solution. In this work, we propose a new method for MWCP which interleaves between clique construction and graph reduction. We also propose three novel ideas to make it efficient, and develop an algorithm called FastWClq. Experiments on massive graphs from various applications show that, FastWClq finds better solutions than state of the art algorithms while the run time is much less. Further, FastWClq proves the optimal solution for about half of the graphs in an averaged time less than one second.

PDF