# A Dual-mode Local Search Algorithm for Solving the Minimum Dominating Set Problem

arXiv: https://arxiv.org/abs/2307.16815 · HTML: https://mlsanity.com/paper/2307.16815/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 37 references that are in the map.
- First posted on arXiv 25 Jul 2023.

## Builds on (most cited first, 6 of 6)

- [Finding Near-Optimal Independent Sets at Scale](https://mlsanity.com/paper/1509.00764/) (2015)
- [Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover](https://mlsanity.com/paper/1411.2680/) (2014)
- [Accelerating Local Search for the Maximum Independent Set Problem](https://mlsanity.com/paper/1602.01659/) (2016)
- [An Order-based Algorithm for Minimum Dominating Set with Application in Graph Mining](https://mlsanity.com/paper/1705.00318/) (2017)
- [Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function](https://mlsanity.com/paper/1702.04594/) (2017)
- [Mining Large Independent Sets on Massive Graphs](https://mlsanity.com/paper/2208.07777/) (2022)

## Built on by (most cited first, 2 of 2)

- [HyColor: An Efficient Heuristic Algorithm for Graph Coloring](https://mlsanity.com/paper/2506.07373/) (2025)
- [Dynamic Location Search for Identifying Maximum Weighted Independent Sets in Complex Networks](https://mlsanity.com/paper/2505.04674/) (2025)

## Abstract (arXiv)

Given a graph, the minimum dominating set (MinDS) problem is to identify a smallest set D of vertices such that every vertex not in D is adjacent to at least one vertex in D. The MinDS problem is a classic NP-hard problem and has been extensively studied because of its many disparate applications in network analysis. To solve this problem efficiently, many heuristic approaches have been proposed to obtain a good solution within an acceptable time limit. However, existing MinDS heuristic algorithms are always limited by various tie-breaking cases when selecting vertices, which slows down the effectiveness of the algorithms. In this paper, we design an efficient local search algorithm for the MinDS problem, named DmDS -- a dual-mode local search framework that probabilistically chooses between two distinct vertex-swapping schemes. We further address limitations of other algorithms by introducing vertex selection criterion based on the frequency of vertices added to solutions to address tie-breaking cases, and a new strategy to improve the quality of the initial solution via a greedy-based strategy integrated with perturbation. We evaluate DmDS against the state-of-the-art algorithms on seven datasets, consisting of 346 instances (or families) with up to tens of millions of vertices. Experimental results show that DmDS obtains the best performance in accuracy for almost all instances and finds much better solutions than state-of-the-art MinDS algorithms on a broad range of large real-world graphs.