Local Search for Maximum Weight Clique Problem

The maximum clique problem (MCP) consists in finding a clique with maximum number of vertices. An important generalization of MCP is the maximum weight clique problem (MWCP), in which each vertex is associated with a non-negative integer, and the goal is to find a clique with the largest total weight.

Local search solvers for MWCP

I have developed two local search solvers for MWCP. The executable files are available below.

l LSCC and LSCC+BMS 

Strong configuration checking (SCC) is a new variant of a recent powerful strategy called configuration checking (CC) for reducing cycling in local search. Based on the SCC strategy, we develop a local search algorithm named LSCC.

A low-complexity heuristic called Best from Multiple Selection (BMS) is used to select the swapping vertex pair quickly and effectively on massive graphs. The BMS heuristic is used to improve LSCC, resulting in the LSCC+BMS algorithm.

---Reference: Wang Yiyuan, Cai Shaowei, & Yin Minghao. Two Efficient Local Search Algorithms for Maximum Weight Clique Problem. Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 2016, 805-811.