Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function (Extended Abstract)

1 Introduction

Given an undirected graph G, a dominating set D is a subset of vertices such that every vertex not in D is adjacent to at least one member of D. The Minimum Dominating Set (MDS) problem consists in identifying the smallest dominating set in a graph. The Minimum Weight Dominating Set (MWDS) problem is a generalized version of MDS. In the MWDS problem, each vertex is associated with a positive value as its weight, and the task is to find a dominating set that minimizes the total weight of the vertices in it. The MWDS problem has played a prominent role in various real-world domains [Shen and Li, 2010; Golovach et al., 2013], such as social networks, communication networks, and industrial applications.

Most practical algorithms for solving the MWDS problem are heuristic algorithms [Jovanovic et al., 2010; Potluri and Singh, 2013; Nitash and Singh, 2014; Chaurasia and Singh, 2015; Bouamama and Blum, 2016]. However, the efficiency of existing heuristic algorithm are still not satisfactory, especially for hard and large-scaled instances (as will be shown in our experiments). The reason may be that the heuristic functions used in previous algorithms do not have enough information during the search procedure, and the cycling search problems can not be overcome by most algorithms as well.

∗This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Wang et al., 2017]

In this paper, we develop a novel local search algorithm for the MWDS problem based on two new ideas. The first idea is a new variant of the Configuration Checking (CC) strategy. Initially proposed in [Cai et al., 2011], the CC strategy aims to reduce the cycling phenomenon in local search, by considering the circumstance of the solution components, which is formally defined as the configuration. The CC strategy has been successfully applied to a number of wellknown combinatorial optimization problems [Li et al., 2016; Wang et al., 2016b; 2016a; Luo et al., 2015; Cai et al., 2015]. In this work, we propose a variant of the CC strategy based on a new definition of configuration. In this strategy, the configuration of a vertex v refers to its two-level neighborhood, which is the union of the neighborhood N(v) and the neighborhood of each vertex in N(v). This new strategy is thus called two-level configuration checking (abbreviated as CC2 ).

The second idea is a frequency based scoring function for vertices, according to which the score of each vertex is calculated. Local search algorithms for the MWDS problem maintain a candidate solution, which is a set of vertices selected for dominating. Then the algorithms will use a scoring function to decide which vertices will be selected to update the candidate solution, where the scores of vertices indicate the benefit (which may be positive or negative) produced by adding (or removing) a vertex to the candidate solution. In this work, we introduce a scoring function based on dynamic information of vertices, i.e., the frequency of being uncovered by the candidate solution. This scoring function exploits the information of the search process and that of the candidate solution.

By incorporating these two ideas, we develop a local search algorithm for the MWDS problem termed CC2FS. We carry out experiments to compare CC2FS with five state-of-the-art MWDS algorithms on benchmarks in the literatures including unit disk graphs and random generated instances, as well as two classical graphs benchmarks namely BHOSLIB [Xu et al., 2007] and DIMACS [Johnson and Trick, 1996], and a broad range of real world massive graphs with millions of vertices and dozens of millions of edges [Rossi and Ahmed, 2015]. Experimental results show that CC2FS significantly outperforms previous algorithms and improves the best known solution quality for some difficult instances.

2 Preliminaries

An undirected graph G = (V,E) comprises a vertex set V = {v1, v2, . . . , vn} of n vertices together with a set E = {e1, e2, . . . , em} of m edges, where each edge e = {v, u} connects two vertices u and v, and these two vertices are called the endpoints of edge e. The distance between two vertices u and v, denoted by dist(u, v), is the number of edges in a shortest path from u to v, and dist(u, u) = 0 particularly. For a vertex v, we define its ith level neighborhood as Ni(v) = {u|dist(u, v) = i}, and we denote N k (v) = ⋃ki=1 Ni(v). The first-level neighborhood N1(v) is usually denoted as N(v) as well, and we denote Ni[v] = Ni(v)∪{v}. Also, we define the closed neighborhood of a vertex set S, N[S] = ⋃v∈S N[v].

A dominating set of G is a subset D ⊆ V such that every vertex in G either belongs to D or is adjacent to a vertex in D. The Minimum Dominating Set (MDS) problem calls for finding a dominating set of minimum cardinality. In the MinimumWeight Dominating Set (MWDS) problem, each vertex v is associated with a positive weight w(v), and the task is to find a dominating set D which minimizes the total weight of vertices in D (i.e., min∑v∈D w(v)).

3 Two-Level Configuration Checking

In this section, we define the CC2 strategy and present an implementation for it. We start from the formal definition of the configuration of a vertex v.

Definition 1 Given an undirected graph G = (V, E) and S the candidate solution, the configuration of a vertex v ∈ V is a vector consisting of state of all vertices in N 2 (v).

Based on the above definition, we can define an important vertex in local search as follows.

Definition 2 Given an undirected graph G = (V, E) and S the candidate solution, for a vertex v /∈ S, v is configuration changed if at least one vertex in N 2 (v) has changed its state since the last time v is removed from S.

In the CC2 strategy, only the configuration changed vertices are allowed to be added to the candidate solution S.

We implement CC2 with a Boolean array ConfChange whose size equals the number of vertices in the input graph. For a vertex v, the value of ConfChange[v] is an indicator - ConfChange[v]=1 means v is a configuration changed vertex and is allowed to be added to the candidate solution S; otherwise, ConfChange[v]=0 and it cannot be added to S. During the search procedure, the ConfChange array is maintained as follows.

• CC2 -RULE1. At the start of search process, for each vertex v, ConfChange[v] is initialized as 1.
• CC2 -RULE2. When removing a vertex v from the candidate solution S, ConfChange[v] is set to 0, and for each vertex u ∈ N 2 (v), ConfChange[u] is set to 1.
• CC2 -RULE3. When adding a vertex v into the candidate solution S, for each vertex u ∈ N 2 (v), ConfChange[u] is set to 1.

To understand RULE2 and RULE3, we note that if u ∈ N 2 (v), then v ∈ N 2 (u). Thus, if a vertex v changes its state (i.e., either being removed or added w.r.t. the candidate solution), the Configuration of any vertex u ∈ N 2 (v) is changed.

The details of the relationship between CC and CC2 strategies are presented in [Wang et al., 2017].

4 The Frequency based Scoring Function

In this paper, we introduce a novel scoring function by taking into account of the vertices' frequency, which can be viewed as some kind of dynamic information indicating the accumulative effectiveness that the search has on the vertex. Intuitively, if a vertex is usually uncovered, then we should encourage the algorithm to select a vertex to make it covered.

In detail, in a graph, each vertex v ∈ V has an additional property, frequency, denoted by freq[v]. The freq of each vertex is initialized to 1. After each iteration of local search, the freq value of each uncovered vertex is increased by one. During the search process, we apply the freq of vertex to decide which vertex to be added or removed. Based on this consideration, we propose a new score function, which is formally defined as below.

Definition 3 For a graph G = (V,E), and a candidate solution S, the frequency based scoring function denoted by scoref , is a function such that

where C1=N[u] \ N[S] and C2=N[u] \N[S \ {u}].

Remark that, in the above definition, C1 is indeed the set of uncovered vertices that would become covered by adding u into S and C2 is the set of covered vertices that would become uncovered by removing u from S.

5 The Selection Vertex Strategy

During the search process, for preventing visiting previous candidate solutions, we not only use the CC2 strategy in the adding process, but also use the forbidding list in the removing process. The forbid_list used here is a tabu list which keeps track of the vertices added in the last step, and these vertices are prevented from being removed within the tabu tenure. In this sense, this frequency based prohibition mechanism can be viewed as an instantiation of the longer term memory tabu search, and the main difference is that our method also consider the information from the CC 2 strategy.

The algorithm picks a vertex to add or remove, using the frequency based scoring function and the above two strategies. Firstly, we give two rules for removing vertices.

REMOVE-RULE1. Removing one vertex v, which has the highest value of scoref (v), breaking ties by selecting the oldest one.

REMOVE-RULE2. Removing one vertex v, which is not in forbid_list and has the highest value of scoref (v), breaking ties by selecting the oldest one.

When the algorithm finds a solution, it removes one vertex from the solution and continues to search for a solution with smaller weight. In this process, we use REMOVE-RULE1 to pick the vertex. During the search for a solution, the algorithm exchanges some vertices, i.e., removing one vertex from the candidate solution and then iteratively adding vertices into the candidate solution. In this case, we select one vertex to remove according to REMOVE-RULE2.

The rule to select the adding vertices is given below.

ADD-RULE. Adding one vertex v with ConfChange[v] ̸= 0, which has the greatest value scoref (v), breaking ties by selecting the oldest one.

When adding one vertex into the candidate solution, we try to make the resulting candidate solution's cost (i.e., the total weight of uncovered vertices) as small as possible. When adding one configuration changed vertex with the highest value scoref (v), breaking ties by preferring the oldest vertex.

6 CC2FS Algorithm

Based on CC2 and the frequency based scoring function, we develop a local search algorithm named CC2FS. During the process of local search, we maintain a set from which the vertex to be added is chosen. The set for finding a vertex to be removed from the candidate solution is simply S.

The pseudo code of CC2FS is shown in Algorithm 2. At first, CC2FS initializes ConfChange, forbid_list and the frequency and scoref of vertices. Then it gets an initial candidate solution S greedily by iteratively adding the vertex that covers the most remaining uncovered vertices until S covers all vertices. At the end of initialization, the best solution S∗ is updated by S.

After initialization, the main loop from lines 3 to 16 begins by checking whether S is a solution (i.e., covers all vertices). When the algorithm finds a better solution, S∗ is updated. Then one vertex with the highest scoref value in S is selected to be removed, breaking tie in favor of the oldest one. Finally, the values of ConfChange are updated by CC2 -RULE2.

If there are uncovered vertices, CC2FS first picks one vertex to remove from S with the highest value scoref , breaking tie in favor of the oldest one. Note that when choosing a vertex to remove, we do not consider those vertices in forbid_list, as they are forbidden to be removed by the forbidden list. After removing a vertex, CC2FS updates the ConfChange values according to CC2 -RULE2, and clear forbid_list. Additional, since the tabu tenure is set to be 1, the forbid_list shall be cleared to allow previous forbidden vertices to be added in subsequent loop.

After the removing process, CC2FS iteratively adds one vertex into S until it covers all vertices, i.e. the candidate solution is a dominating set. CC2FS first selects v ∈ CCV 2 with the greatest scoref (v), breaking ties in favor of the oldest one. When the picked uncovered vertex is added into the candidate solution, the ConfChange values are updated according to CC2 -RULE3 and this added vertex is added into the forbid_list. After adding an uncovered vertex each time, the frequency of uncovered vertices is increased by one. When the time limit reaches, the best solution will be returned. For each iteration, the local search stage of CC2FS has a time complexity of O(max{∆(G)|V |, ∆(G)3 }), where ∆(G) = max{|N[v]||v ∈ V, G = (V, E)}.

7 Empirical Results

We compare CC2FS with five competitors on a broad range of benchmarks, with respect to both solution quality and run time. The run time is measured in CPU seconds. We run CC2FS on a broad range of test instances, namely T1, T2, UDG, DIMACS, BHOSLIB, as well as many real world massive graphs. For T1 and T2 instances [Jovanovic et al., 2010], we note that ten instances are generated for each combination of number of nodes and transmission range.

We compare CC2FS with HGA [2013], ABC [2014], ACO-PP-LS [2013], EA/G-IR [2015], and R-PBIG [2016]. Among them, R-PBIG and ACO-PP-LS are the best available algorithms for solving MWDS.

We implement CC2FS in C++ and compile it by g++ with the -O2 option. All the experiments are run on Ubuntu Linux, with 3.1 GHZ CPU and 8GB memory. For T1 and T2 instances, CC2FS and ACO-PP-LS are performed once, where one run is terminated upon reaching a given time limit. Among this, the parameter time limit is set to 50 seconds when the number of vertices is less than 500, otherwise the time limit is set to 1000 seconds. We report the real time RTime of ACO-PP-LS and CC2FS, while we also give the finial execution time FT ime of EA/G-IR and R-PBIG. The real time is a time when ACO-PP-LS and CC2FS obtain the best solution respectively. The MEAN contains the average solution values for each of the ten instances of graphs of a particular size.

The performance results of previous algorithms on the T1 benchmark are displayed in Table 1. More importantly, this table also summarizes the experimental results on the first benchmark for our algorithm.

Among previous algorithms, for most instances, R-PBIG and ACO-PP-LS can find better solutions than HGA, ABC and EA/G-IR, with only a few exceptions.

For our algorithm, we show the minimum solution value and the run time. As is clear from the Table 1, CC2FS shows significant superiority on the T1 benchmark, except v50e750. By comparing these algorithms, we can easily conclude that CC2FS outperforms other algorithms.

The experimental results on the T2 benchmark are presented in Table 2. The quality of the solutions found by CC2FS is always much smaller than those found by other algorithms on all instances with 2 exceptions, i.e. v250e250 and v800e10000. Details of the experiemental results as well as the analysis based on benchmarks of the DIMACS, BHOSLIB, and real world massive graphs are presented in [Wang et al., 2017].

8 Conclusions

This paper presented a local search algorithm called CC2FS for solving the minimum weight dominating set (MWDS) problem. We proposed a new configuration checking strategy namely CC2 based on the two-level neighborhood of vertices to remember the relevant information of removed and added vertices and prevent visiting the recent paths. Moreover, we introduced a new frequency based scoring function for solving MWDS. The experimental results showed that CC2FS performs essentially better than state of the art algorithms on almost all instances in terms of solution quality and run time.

Acknowledgments

This work was supported in part by NSFC (under Grant Nos. 61370156, 61503074, 61502464, 61402070, and 61403077).