A new branch-and-bound algorithm for the Maximum Weighted Clique Problem. (October 2019) - San Segundo, Pablo; Furini, Fabio; Artieda, Jorge
Highlights: A new incremental bound for the Maximum Weighted Clique Problem based on an independent set cover. A Branch-and-Bound exact algorithm for the MaximumWeighted Clique Problem. Extensive computational experiments. Abstract: We study the Maximum Weighted Clique Problem (MWCP), a generalization of the Maximum Clique Problem in which weights are associated with the vertices of a graph. The MWCP calls for determining a complete subgraph of maximum weight. We design a new combinatorial branch-and-bound algorithm for the MWCP, which relies on an effective bounding procedure. The size of the implicit enumeration tree is largely reduced via a tailored branching scheme, specifically conceived for the MWCP. The new bounding function extends the classical MWCP bounds from the literature to achieve a good trade off between pruning potential and computing effort. We perform extensive tests on random graphs, graphs from the literature and real-world graphs, and we computationally show that our new exact algorithm is competitive with the state-of-the-art algorithms for the MWCP in all these classes of instances.