Dynamic Local Search for the Maximum Clique Problem

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 DLSMC 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.

• Publication year

  2011

• Venue

  Journal of Artificial Intelligence Research

• Publication date

  2011-09-26

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1613/jair.1815arXiv 1109.5717
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A study of ACO capabilities for solving the maximum clique problem

  2006cited by this paper
• A new trust region technique for the maximum weight clique problem

  2006cited by this paper
• Additive versus Multiplicative Clause Weighting for SAT

  2004cited by this paper
• Stochastic Local Search: Foundations & Applications

  2004cited by this paper
• Resolvent Clause Weighting Local Search

  2004cited by this paper
• Solving the maximum clique problem by k-opt local search

  2004influential reference
• Combining Swaps and Node Weights in an Adaptive Greedy Approach for the Maximum Clique Problem

  2004influential reference
• Scaling and Probabilistic Smoothing: Dynamic Local Search for Unweighted MAX-SAT

  2003cited by this paper
• A graph theoretical approach for predicting common RNA secondary structure motifs including pseudoknots in unaligned sequences

  2003cited by this paper
• Genetic, Iterated and Multistart Local Search for the Maximum Clique Problem

  2002influential reference
• An adaptive noise mechanism for walkSAT

  2002cited by this paper
• Scaling and Probabilistic Smoothing: Efficient Dynamic Local Search for SAT

  2002cited by this paper
• Reactive Local Search for the Maximum Clique Problem1

  2001influential reference
• Local search characteristics of incomplete SAT procedures

  2000cited by this paper
• Local Search Algorithms for SAT: An Empirical Evaluation

  2000cited by this paper
• Combinatorial Approaches to Finding Subtle Signals in DNA Sequences

  2000cited by this paper
• Clique is hard to approximate withinn1−ε

  1999cited by this paper
• The Maximum Clique Problem

  1999cited by this paper
• Handbook of Combinatorial Optimization

  1998cited by this paper
• Fortran Subroutines For Approximate Solution Of Maximum Independent Set Problems Using Grasp

  1998cited by this paper
• Cliques, Coloring, and Satisfiability

  1996cited by this paper
• The Reactive Tabu Search

  1994influential reference
• Camouflaging independent sets in quasi-random graphs

  1993cited by this paper
• Approximating Maximum Independent Sets by Excluding Subgraphs 1

  1990cited by this paper
• Approximating maximum independent sets by excluding subgraphs

  1990cited by this paper
• Finding a Maximum Clique in an Arbitrary Graph

  1986cited by this paper
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• Johnson: computers and intractability: a guide to the theory of np- completeness (freeman

  1979cited by this paper

• Clique-Based Deletion-Correcting Codes via Penalty-Guided Clique Search

  2026cites this paper
• The First Hardware Demonstration of a Universal Programmable RRAM-based Probabilistic Computer for Molecular Docking

  2025influential citation
• A hardware demonstration of a universal programmable RRAM-based probabilistic computer for molecular docking

  2025cites this paper
• An Efficient Seed-Initialized Algorithm for Maximal Clique Enumeration and Its Applications

  2025cites this paper
• Convergent Functions, Divergent Forms

  2025cites this paper
• ILSGVCP: An improved local search algorithm for generalized vertex cover problem

  2023cites this paper
• Efficient Maximum Edge-Weighted Biclique Search on Large Bipartite Graphs

  2023cites this paper
• Quantum-Inspired Classical Algorithm for Graph Problems by Gaussian Boson Sampling

  2023cites this paper
• Cellular goore game with application to finding maximum clique in social networks

  2022cites this paper
• An approximation lagrangian-based algorithm for the maximum clique problem via deterministic annealing neural network

  2022cites this paper
• An Adaptive Repeated-Intersection-Reduction Local Search for the Maximum Independent Set Problem

  2022cites this paper
• A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs

  2021cites this paper
• Towards efficient local search for the minimum total dominating set problem

  2021cites this paper
• Distributed Load Identification for Uncertain Structure Based on LHS-GA and Improved L-Curve Method

  2021cites this paper
• Improving the Performance of Stochastic Local Search for Maximum Vertex Weight Clique Problem Using Programming by Optimization

  2020cites this paper
• SCCWalk: An efficient local search algorithm and its improvements for maximum weight clique problem

  2020cites this paper
• Neighbourhood Evaluation Criteria for Vertex Cover Problem

  2020cites this paper
• Circuit Synthesis of Maximum Clique Problem using Combinatorial Approach of Classical-Quantum Hybrid Model

  2020cites this paper
• Testing a Heuristic Algorithm for Finding a Maximum Clique on DIMACS and Facebook Graphs

  2020cites this paper
• An efficient local search algorithm for solving maximum edge weight clique problem in large graphs

  2020cites this paper
• Reinforcement Learning for Combinatorial Optimization: A Survey

  2020cites this paper
• Dynamic thresholding search for minimum vertex cover in massive sparse graphs

  2019cites this paper
• Incremental optimization of independent sets under the reconfiguration framework

  2019cites this paper
• MEAMCP: A Membrane Evolutionary Algorithm for Solving Maximum Clique Problem

  2019cites this paper
• Solving the Graph Problem on the Maximal Clique Problem on the P-Systems with Mitochondria Enzymes Layer

  2019cites this paper
• Digitally Annealed Solution for the Maximum Clique Problem with Critical Application in Cellular V2X

  2019cites this paper
• Applications of near-term photonic quantum computers: software and algorithms

  2019cites this paper
• A GPU based local search algorithm for the unweighted and weighted maximum s-plex problems

  2019cites this paper
• Molecular docking with Gaussian Boson Sampling

  2019cites this paper
• Gérer et analyser les grands graphes des entités nommées. (Manage and analyze large graphs of named entities)

  2019cites this paper
• A novel parallel local search algorithm for the maximum vertex weight clique problem in large graphs

  2019cites this paper
• A memory efficient maximal clique enumeration method for sparse graphs with a parallel implementation

  2019cites this paper
• An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem

  2018cites this paper
• An Efficient Local Search for the Minimum Independent Dominating Set Problem

  2018cites this paper
• GraphZIP: a clique-based sparse graph compression method

  2018cites this paper
• An Efficient Local Search for the Maximum Edge Weighted Clique Problem

  2018cites this paper
• An efficient method for mining the maximal α-quasi-clique-community of a given node in complex networks

  2018cites this paper
• Searching on Massive Graphs and Regularizing Deep Learning

  2018cites this paper
• Implementation of a maximum clique search procedure on CUDA

  2018cites this paper
• The Maximum Clique and Vertex Coloring

  2018cites this paper
• A robust and cooperative parallel tabu search algorithm for the maximum vertex weight clique problem

  2018cites this paper
• Scalable kernelization for the maximum independent set problem

  2017cites this paper
• Finding the maximum clique in massive graphs

  2017cites this paper
• On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem

  2017cites this paper
• PUSH: A generalized operator for the Maximum Vertex Weight Clique Problem

  2017cites this paper
• CHN and Swap Heuristic to Solve the Maximum Independent Set Problem

  2017cites this paper
• Clustered maximum weight clique problem: Algorithms and empirical analysis

  2017cites this paper
• Frequency-driven tabu search for the maximum s-plex problem

  2017cites this paper
• An Exact Algorithm Based on MaxSAT Reasoning for the Maximum Weight Clique Problem

  2016cites this paper
• An efficient local search for partial vertex cover problem

  2016cites this paper
• Local Search with Noisy Strategy for Minimum Vertex Cover in Massive Graphs

  2016cites this paper
• Rank metric codes

  2016cites this paper
• A new exact maximum clique algorithm for large and massive sparse graphs

  2016cites this paper
• Two Efficient Local Search Algorithms for Maximum Weight Clique Problem

  2016influential citation
• Experimental Algorithms

  2016influential citation
• Accelerating Local Search for the Maximum Independent Set Problem

  2016cites this paper
• Fast Solving Maximum Weight Clique Problem in Massive Graphs

  2016cites this paper
• A local search algorithm with tabu strategy and perturbation mechanism for generalized vertex cover problem

  2016cites this paper
• Notes on Privacy-preserving Distributed Mining and Hamiltonian Cycles

  2016influential citation
• Random Walk in Large Real-World Graphs for Finding Smaller Vertex Cover

  2016cites this paper
• An efficient local search framework for the minimum weighted vertex cover problem

  2016cites this paper
• Combining Efficient Preprocessing and Incremental MaxSAT Reasoning for MaxClique in Large Graphs

  2016cites this paper
• Diversity optimization and parameterized analysis of heuristic search methods for combinatorial optimization problems

  2016cites this paper
• Automatic determination of optimal viewing angle for the coronary lesion observation in rotationnal X-ray angiography

  2016cites this paper
• Maximal falsifiability

  2015cites this paper
• Maximum cut-clique problem: ILS heuristics and a data analysis application

  2015cites this paper
• Solving the winner determination problem via a weighted maximum clique heuristic

  2015influential citation
• Finding near-optimal independent sets at scale

  2015cites this paper
• KaMIS v1.0 – Karlsruhe Maximum Independent Sets User Guide

  2015cites this paper
• Graph Partitioning for Independent Sets

  2015cites this paper
• Distributed Algorithms for Maximum Clique in Wireless Networks

  2015cites this paper
• Two Weighting Local Search for Minimum Vertex Cover

  2015influential citation
• A novel clique formulation for the visual feature matching problem

  2015cites this paper
• COMPLEXITY ANALYSIS OF CLIQUE PROBLEM

  2015influential citation
• Community Based Information Dissemination

  2015cites this paper
• Analysis of a simultaneously clockwise and counterclockwise rotated mode stirrer in a reverberation chamber

  2015cites this paper
• Stochastic Local Search Algorithms: An Overview

  2015cites this paper
• Maximum Degree Vertex-Based Algorithm for Maximum Clique Problem

  2015cites this paper
• Survey of Algorithms on Maximum Clique Problem

  2015cites this paper
• Survey of Algorithms on Maximum Clique

  2015cites this paper
• A review on algorithms for maximum clique problems

  2015influential citation
• Integrating domain heterogeneous data sources using decomposition aggregation queries

  2014cites this paper
• An analysis of parameter adaptation in reactive tabu search

  2014cites this paper
• Improving upper bounds for the clique number by non-valid inequalities

  2014cites this paper
• Characterising fitness landscapes with fitness-probability cloud and its applications to algorithm configuration

  2014cites this paper
• A fast genetic algorithm for solving the maximum clique problem

  2014cites this paper
• Target Aware Local Search for Maximum Clique Problem

  2014cites this paper
• Combining Edge Weight and Vertex Weight for Minimum Vertex Cover Problem

  2014influential citation
• On Reducing Maximum Independent Set to Minimum Satisfiability

  2014cites this paper
• Improvements to MCS algorithm for the maximum clique problem

  2014cites this paper
• Cluster Restricted Maximum Weight Clique Problem and Linkages with Satellite Image Acquisition Scheduling

  2014cites this paper
• NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover

  2014influential citation
• Combinatorial Search: From Algorithms to Systems

  2013cites this paper
• Speeding up branch and bound algorithms for solving the maximum clique problem

  2013cites this paper
• Complete Boolean Satisfiability Solving Algorithms Based on Local Search

  2013cites this paper
• Combining MaxSAT Reasoning and Incremental Upper Bound for the Maximum Clique Problem

  2013cites this paper
• The maximum clique problems with applications to graph coloring. (Problèmes de clique maximum avec applications à la coloration de graphe)

  2013influential citation
• A New Effective Local Search Heuristic for the Maximum clique problem

  2013cites this paper
• Metaheuristics for large binary quadratic optimization and its applications. (Métaheuristiques pour l'optimisation quadratique en 0/1 à grande échelle et ses applications)

  2013cites this paper
• Computational approaches to discovering differentiation genes in the peripheral nervous system of Drosophila melanogaster

  2013cites this paper