A Fast Local Search Algorithm for Minimum Weight Dominating Set Problem on Massive Graphs

A Fast Local Search Algorithm for Minimum Weight Dominating Set Problem on Massive Graphs

Yiyuan Wang, Shaowei Cai, Jiejiang Chen, Minghao Yin

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 1514-1522. https://doi.org/10.24963/ijcai.2018/210

The minimum weight dominating set (MWDS) problem is NP-hard and also important in many applications. Recent heuristic MWDS algorithms can hardly solve massive real world graphs effectively. In this paper, we design a fast local search algorithm called FastMWDS for the MWDS problem, which aims to obtain a good solution on massive graphs within a short time. In this novel local search framework, we propose two ideas to make it effective. Firstly, we design a new fast construction procedure with four reduction rules to cut down the size of massive graphs. Secondly, we propose the three-valued two-level configuration checking strategy to improve local search, which is interestingly a variant of configuration checking (CC) with two levels and multiple values. Experiment results on a broad range of massive real world graphs show that FastMWDS finds much better solutions than state of the art MWDS algorithms.
Keywords:
Heuristic Search and Game Playing: Heuristic Search
Heuristic Search and Game Playing: Combinatorial Search and Optimisation