Source-linked AI summary
Dynamic Local Search for the Maximum Clique Problem
H. H. Hoos, W. Pullan
TL;DR
MAX-CLIQUE requires effective heuristic search, but comparisons across algorithms are complicated by differing experimental protocols and hardware. The paper introduces DLS-MC, which combines iterative improvement, plateau search, dynamic vertex penalties, and perturbation. Experiments report improved performance over state-of-the-art methods across DIMACS benchmarks, while penalty-delay tuning remains instance-family dependent.
Problem
MAX-CLIQUE heuristic comparisons are difficult because studies use different experimental protocols and computing hardware.
Method
DLS-MC alternates iterative improvement and plateau search, selects vertices using dynamic penalties, and perturbs the clique to avoid stagnation.
Results
DLS-MC outperforms state-of-the-art MAX-CLIQUE algorithms across a broad range of DIMACS benchmark instances and dominates DAGS and GRASP on the listed Table 4 instances.
Takeaways & Limitations
The results provide evidence that dynamic local search with non-monotone penalty dynamics is effective and broadly applicable to MAX-CLIQUE.
Takeaways & Limitations
Penalty delay must be tuned to an instance family or sub-family, although fine-tuning may yield only minor improvements.
Abstract
from arXiv · showhide
In this paper, we introduce DLS-MC, a new stochastic local search algorithm for the maximum clique problem. DLS-MC alternates between phases of iterative improvement, during which suitable vertices are added to the current clique, and plateau search, during which vertices of the current clique are swapped with vertices not contained in the current clique. The selection of vertices is solely based on vertex penalties that are dynamically adjusted during the search, and a perturbation mechanism is used to overcome search stagnation. The behaviour of DLS-MC is controlled by a single parameter, penalty delay, which controls the frequency at which vertex penalties are reduced. We show empirically that DLS-MC achieves substantial performance improvements over state-of-the-art algorithms for the maximum clique problem over a large range of the commonly used DIMACS benchmark instances.
1. Introduction
MAX-CLIQUE seeks the largest pairwise-adjacent vertex subgraph and supports applications across several fields. DLS-MC applies dynamic local search to improve heuristic solving performance on benchmark instances.
- MAX-CLIQUE seeks the maximum-sized subgraph whose vertices are pairwise adjacent.
- MAX-CLIQUE is relevant to information retrieval, experimental design, signal transmission, computer vision, and bioinformatics.
- Existing MAX-CLIQUE algorithms include greedy construction, stochastic local search, reactive local search, iterated greedy methods, and variable-depth search.
- Experimental comparisons are difficult because studies use different protocols and runtime environments, and no single algorithm is consistently best.
- DLS-MC combines constructive and perturbative local search with dynamically determined vertex penalties to reduce search stagnation.
- Extensive experiments report that DLS-MC outperforms state-of-the-art algorithms, particularly DAGS, across a broad range of benchmark instances.
2. The DLS-MC Algorithm
DLS-MC alternates greedy clique expansion with plateau swaps, selecting candidates by dynamically adjusted vertex penalties. Penalty updates, occasional decreases, and perturbations provide diversification while a single penalty-delay parameter controls forgetting.
- DLS-MC starts from a randomly chosen vertex, initializes penalties to zero, and alternates iterative improvement with plateau search.
- The expand procedure adds vertices adjacent to every vertex in the current clique, while plateauSearch swaps a clique vertex using level neighbours adjacent to all but one clique vertex.
- Both subsidiary procedures select uniformly among minimum-penalty candidate vertices, using penalties rather than direct clique-size maximization.
- After plateau search, penalties of current-clique vertices increase by one, while every penalty-delay cycle decrements all non-zero penalties.
- Penalty decreases prevent values from becoming too large and allow DLS-MC to forget penalty history over time.
- When penalty delay exceeds one, perturbation reduces the clique to its last added vertex, making previously removed vertices less likely to return immediately.
- Implementation uses array-based set representations and pointer access to keep individual search steps efficient.
3. Empirical Performance Results
DLS-MC was evaluated extensively on the 80 DIMACS MAX-CLIQUE instances and generally achieved strong solution quality and comparative performance. Its results were especially competitive against DAGS, GRASP, k-opt, RLS, GENE, ITER, and QUALEX-MS, although hardware-based runtime comparisons have limitations.
- DLS-MC Performance: 100% success was achieved on 77 of the 80 DIMACS instances across 100 runs per instance.The three exceptions were C2000.9, MANN, and a81.
- DLS-MC Performance: Less than 1 CPU second was expected to reach the target clique size on 67 of the 80 instances.For the remaining instances, expected runtimes exceeded 10 CPU seconds for only 8 of 13 cases.
- DLS-MC Performance: 189 235 search steps per CPU second were achieved on C2000.9, while search-step throughput decreased as graph size and neighborhood-set sizes increased.For C∗.9 instances, throughput was approximated by 9 · 10^7 · n^-0.8266 with R2 = 0.9941.
- Comparative Results: Runtime comparisons are constrained because hardware differences were approximated mainly through CPU-speed scaling, omitting factors such as caching, memory, and architecture.The paper notes that this scaling was sometimes the only realistic comparison available.
- Comparative Results: DLS-MC dominated GRASP and DAGS on the selected Table 4 instances, and dominated k-opt on the selected Table 7 instances.Across broader comparisons, DLS-MC dominated QUALEX-MS on 76 of 80 instances and was dominant on the remaining 72 instances in another ranking comparison.
- Comparative Results: DLS-MC dominated DAGS on all but one directly compared DIMACS instance, with san1000 as the exception.In the literature-based comparison, CPU times were scaled by 0.64 under an assumed linear relationship with CPU clock speed.
- Comparative Results: DLS-MC was not uniformly dominant: RLS, k-opt, QUALEX-MS, and DAGS each led on specified instances or subsets.The reported exceptions include MANN a45, keller6, san1000, and brock4003.
4. Discussion
The discussion examines DLS-MC’s runtime variability, penalty-delay effects, and perturbation behavior on C1000.9 and brock800. Penalties reduce degree-driven bias and diversify search, but their best delay depends on the instance family.
- Runtime behavior: DLS-MC showed large runtime variability across 100 independent runs on both reference instances, with runtime distributions well approximated by exponentials.The runs all reached the respective best known clique size.
- Penalty dynamics: Penalty delay controls how often non-zero penalties are decreased, allowing the search to forget accumulated penalties over time.Penalties increase for clique vertices after plateau search, while every pd update cycles all non-zero penalties decrease by one.
- Penalty effects: For pd = 45 on brock800, clique presence immediately before perturbation was almost independent of vertex degree, unlike the high-degree preference observed at pd = 1.This indicates that larger delays can neutralize degree-based selection bias rather than identify vertices that belong in an optimal clique.
- Parameter dependence: Penalty delay must currently be tuned to an instance family or brock sub-family, although DLS-MC remains reasonably robust to the exact parameter value.The authors suggest adaptive delay mechanisms and further tuning based on runtime-distribution data as future improvements.
- Penalty dynamics: At pd = 45, approximately 90% of vertices were penalised on average, corresponding to the empirically identified optimal delay for the brock800 analysis.The penalty-delay analysis links this setting to the frequency of penalty accumulation and reduction.
- Penalty effects: Increasing penalty delay reduces the bias toward high-degree vertices, which is useful for brock800 because its optimal clique contains many lower-than-average-degree vertices.Without penalties, high-degree vertices are preferred; penalties counteract this misleading bias in brock800.
- Perturbation behavior: The more radical perturbation used for pd > 1 is better suited to brock800’s low fitness-distance correlation, whereas C1000.9’s landscape favors less radical perturbation.C1000.9 has many optimal solutions and higher-degree optimal vertices; brock800 appears to have one optimum and many near-optimal solutions.
5. Conclusions and Future Work
DLS-MC applies dynamic local search to maximum clique and improves the state of the art, while demonstrating the value of dynamic local search with non-monotone penalty dynamics. Future work includes alternative penalty updates and implementation optimization.
- DLS-MC applies dynamic local search to maximum clique and improves the state of the art in MAX-CLIQUE solving.
- DLS-MC and DAGS both use vertex penalties to guide heuristic vertex selection when searching for maximum cliques.
- The results demonstrate the value of dynamic local search with non-monotone penalty dynamics for CLIQUE algorithms.
- Future work includes investigating multiplicative penalty updates instead of DLS-MC’s current additive mechanism.
- The current DLS-MC implementation may be further optimized.