Introduction
The Maximum Clique Problem (MCP) is a cornerstone of computer science, requiring the identification of the largest set of vertices in a graph where every vertex is connected to every other. While the unweighted version is well-understood, real-world applications in bioinformatics, computer vision, and robotics often necessitate weights.
There are two primary weighted variants: the Maximum Vertex-Weighted Clique Problem (MVWCP), where weights are assigned to vertices, and the Maximum Edge-Weighted Clique Problem (MEWCP), where weights are assigned to the connections (edges). Despite its practical importance, MEWCP is significantly more complex and less studied than its vertex-weighted counterpart. This research introduces MEWCat, a novel exact solver designed to bridge this gap through tighter theoretical bounds and superior empirical performance.
Theoretical Complexity and the Hardness Gap
A key contribution of this work is the formal distinction between the computational complexity of MVWCP and MEWCP. The researchers proved that MEWCP remains NP-hard even in extremely dense graphs (where the minimum degree is $n-2$). In contrast, MVWCP becomes solvable in polynomial time under similar conditions.
This "hardness gap" suggests that edge weights introduce a layer of combinatorial complexity that makes the problem fundamentally more difficult to simplify, even when the graph is nearly complete.
The MEWCat Algorithm
To address this difficulty, the authors developed MEWCat, a branch-and-bound algorithm. The efficiency of such solvers relies heavily on "pruning"—the ability to skip sections of the search tree that cannot possibly contain an optimal solution.
MEWCat introduces several core innovations:
- Tighter Upper Bound: By sorting vertices and treating them as the "maximum" element in potential cliques, the authors created a mathematical bound for subgraph weights that is significantly more accurate than previous methods.
- Theoretical Guarantee: The algorithm achieves a worst-case running time of $O^*(1.4423^n)$. This is a major milestone, representing the first time a practical MEWCP solver has been proven to break the trivial $O^*(2^n)$ time barrier.
Experimental Results
The researchers evaluated MEWCat against two state-of-the-art solvers, BBEWC and MECQ, across DIMACS benchmarks, synthetic random graphs, and large-scale real-world networks.
Real-World Performance
On real-world datasets from the Network Repository—including social and technological networks with up to 95,000 vertices—MEWCat demonstrated exceptional speed. It was, on average, over 36x faster than MECQ and 47x faster than BBEWC.
Benchmark Efficiency
On the "hard" DIMACS instances, MEWCat solved every problem within the 7,200-second limit, including 16 instances where the previous best solver (BBEWC) failed to finish. The reduction in search tree size (the number of nodes explored) confirms that the new upper bound is highly effective at pruning the search space, leading to direct computational savings.
Conclusion and Future Work
MEWCat represents a significant advancement in exact solvers for weighted clique problems, successfully bridging the gap between theoretical bounds and practical performance. While MEWCP remains inherently difficult for extremely dense or massive graphs, this work provides a robust framework for future optimization. Potential next steps include developing even tighter bounds for dense graphs, exploring parallelization, and extending the framework to the Maximum Total-Weighted Clique Problem (MTWCP), where both vertices and edges carry weights.
Summary updated