Towards efficient local search for the minimum total dominating set problem

摘要

Given an undirected graph G(V,E), the minimum total dominating set (MTDS) problem consists of finding a subset \(D \subseteq V\) with the minimum vertices such that every vertex v ∈ V is adjacent to at least one vertex in D. That is, even for the vertices in D there should at least one neighbor in D. In this paper, we develop an efficient local search framework called LS_DTR to solve MTDS, which is with dynamic scoring function, tabu combined with configuration check, and balanced random walk. Firstly, a dynamic scoring function is presented to guide the search towards the promising solution space. Subsequently, the TaCC2 strategy combining tabu with two-level configuration checking is implemented to avoid visiting solutions repeatedly. Further, the balanced random walk strategy is applied to introduce the diversity into the search. Based on the three components, an efficient vertex selecting strategy is proposed. Finally, the vertex selecting strategy is applied to select the vertex to perform the remove or add operator during the local search. We use the commercial exact solver as the baseline and compare with the-state-of-art algorithm. Meanwhile, in order to verify the effectiveness of LS_DTR, we not only test on the DIMACS instances, but also extend the benchmark to the random general graphs and unit disk graphs. The results show that our algorithm LS_DTR outperforms the other algorithms on most instances.