Improved Exact and Heuristic Algorithms for Maximum Weight Clique
This work addresses a well-known graph theory problem with many applications, offering incremental improvements in computational efficiency for specific graph types.
The paper tackles the maximum weight clique problem by proposing improved exact and heuristic algorithms that use novel data reduction rules to remove vertices and edges while preserving optimal solutions, resulting in orders of magnitude faster performance on medium-sized graphs and outperforming state-of-the-art methods on most inputs.
We propose improved exact and heuristic algorithms for solving the maximum weight clique problem, a well-known problem in graph theory with many applications. Our algorithms interleave successful techniques from related work with novel data reduction rules that use local graph structure to identify and remove vertices and edges while retaining the optimal solution. We evaluate our algorithms on a range of synthetic and real-world graphs, and find that they outperform the current state of the art on most inputs. Our data reductions always produce smaller reduced graphs than existing data reductions alone. As a result, our exact algorithm, MWCRedu, finds solutions orders of magnitude faster on naturally weighted, medium-sized map labeling graphs and random hyperbolic graphs. Our heuristic algorithm, MWCPeel, outperforms its competitors on these instances, but is slightly less effective on extremely dense or large instances.