Heuristics for the weighted total domination problem

Abstract

The weighted total domination problem (WTDP) belongs to the family of dominating set problems. Given an edge- and vertex- weighted graph, the WTDP consists in selecting a total dominating set D, such that the sum of vertices and edges weights of the subgraph induced by D plus, for each vertex not in D, the minimum weight of its edge to a vertex in D is minimized. A total dominating set D is a subset of the graph’s vertices, such that every vertex, including those in D, is at least adjacent to one vertex in D. This problem arises in many real-life applications closely related to covering and independent set problems; however, it remains computationally challenging due to its N P-hardness. This work presents a variable neighborhood search (VNS) procedure to tackle the WTDP, and investigates the advantages and disadvantages of a multi-start strategy within VNS methodology. In addition, we develop a biased greedy randomized adaptive search procedure (Biased GRASP) that keeps adding elements once a feasible solution is found to produce high-quality initial solutions. We perform extensive numerical analysis to look into the influences of the algorithmic components and to disclose the contribution of the elements and strategies of our method. Finally, the empirical analysis shows that our proposal outperforms the state-of-art results, and the statistical analysis confirms the superiority of our proposal to find the best total dominating sets.

Cite This Publication

Casado, A., Sánchez-Oro, J. & Martínez-Gavara, A. (2025). Heuristics for the weighted total domination problem. TOP 33, 395–436.