Abstract Dominating set is a set of vertices of a graph such that all other vertices have a neighbour in the dominating set. We propose a new order-based randomised local search (RLS o ) algorithm to solve minimum dominating set problem in large graphs. Experimental evaluation is presented for multiple types of problem instances. These instances include unit disk graphs, which represent a model of wireless networks, random scale-free networks, as well as samples from two social networks and real-world graphs studied in network science. Our experiments indicate that RLS o performs better than both a classical greedy approximation algorithm and two metaheuristic algorithms based on ant colony optimisation and local search. The order-based algorithm is able to find small dominating sets for graphs with tens of thousands of vertices. In addition, we propose a multi-start variant of RLS o that is suitable for solving the minimum weight dominating set problem. The application of RLS o in graph mining is also briefly demonstrated.
In the application of a similar idea to the minimum weight dominating set problem, a preprocessing phase has been added to a similar algorithm called ACO-PP-LS @cite_3 . This algorithm extended ACO-LS by adding a routine of generating @math maximal independent sets using a greedy algorithm and improving the pheromone values of vertices in these independent sets. These independent sets were constructed by using a list of vertices available for adding to the independent set. In the beginining, a random vertex is added to the independent set. This vertex and its neighbours are then excluded from the list of available vertices. This is process iterated until there are no more vertices available. This preprocessing routine helps the algorithm to start with a probabilistic model that is not entirely random, leading to more rapid convergence for some instances. In ACO-PP-LS, slighly different values of parameters @math and @math have also been used. These were @math and @math . We will use the original parameterisations of ACO-LS @cite_42 and ACO-PP-LS @cite_3 in our further experimental investigations.
@cite_42 @cite_3
43777471 2010300491
Minimum dominating set, which is an NP-hard problem, finds many practical uses in diverse domains. A greedy algorithm to compute the minimum dominating set is proven to be the optimal approximate algorithm unless P=NP. Meta-heuristics, generally, find solutions better than simple greedy approximate algorithms as they explore the search space better without incurring the cost of an exponential algorithm. However, there are hardly any studies of application of meta-heuristic techniques for this problem. In some applications it is important to minimize the dominating set as much as possible to reduce cost and or time to perform other operations based on the dominating set. In this paper, we propose a hybrid genetic algorithm and an ant-colony optimization (ACO) algorithm enhanced with local search. We compare the performance of these two hybrid algorithms against the solutions obtained using the greedy heuristic and another hybrid genetic algorithm proposed in literature. We find that the ACO algorithm enhanced with a minimization heuristic performs better than all other algorithms in almost all instances. Minimum weight dominating set (MWDS) finds many uses in solving problems as varied as clustering in wireless networks, multi-document summarization in information retrieval and so on. It is proven to be NP-hard, even for unit disk graphs. Many centralized and distributed, greedy and approximation algorithms have been proposed for the MWDS problem. However, all the approximation algorithms are limited to unit disk graphs which are primarily used to model wireless networks. This assumption fails when applied to other domains. In this paper, we present two metaheuristic algorithms - a hybrid genetic algorithm and a hybrid ant colony optimization algorithm - for the problem of computing minimum weight dominating set. We compare our results with that of a greedy heuristic as well as the only other metaheuristic algorithm proposed so far in the literature and show that our algorithms are far better than these algorithms.