NuCDS: An Efficient Local Search Algorithm for Minimum Connected Dominating Set

1 Introduction

Given an undirected connected graph G = (V,E), a set D ⊆ V is called a dominating set if each vertex in V either belongs to D or is adjacent to at least one vertex fromD. The minimum dominating set (MDS) problem is to find a dominating set with the minimum number of vertices in the given graph. An important generalization of MDS is the minimum connected dominating set (MCDS) problem, whose goal is to find a minimum size dominating set that forms a connected subgraph in the given graph. An important application of MCDS is generating a virtual backbone in wireless networks such as mobile ad hoc networks [Al-Karaki and Kamal, 2008], wireless sensors networks [Misra and Mandal, 2009] and vehicular ad hoc networks [Chinnasamy et al., 2019]. Applications are also found in other fields. [Milenkovi´c et al., 2011] Also, MCDS is equivalent to the maximum leaf spanning tree problem [Fernau et al., 2011].

It is well known that MCDS is NP-hard [Kann, 1992]. Several exact algorithms [Fomin et al., 2008; Simonetti et al., 2011; Fan and Watson, 2012; Gendron et al., 2014] and approximation algorithms [Cheng et al., 2003; Ruan et al., 2004; Khuller and Yang, 2019] have been designed for MCDS. Nevertheless, these algorithms are either too timeconsuming or have poor performance in practice, especially in the context of massive graphs.

∗Corresponding author

1.1 RelatedWork

Because of its NP-hardness, much of the research effort in the past decade concerned with solving MCDS has focused on heuristics with the aim of obtaining a good solution within a reasonable time. Two algorithms called MCDS/SA and MCDS/TS based on simulated annealing and tabu search were proposed [Morgan and Grout, 2007]. Hedar and Ismail [2012] designed a simulated annealing algorithm with stochastic local search for MCDS. Later, Jovanovic and Tuba [2013] designed an ant colony optimization algorithm with a so-called pheromone correction strategy. A greedy random adaptive search procedure that incorporated a local search procedure based on a greedy function and tabu search was described in [Li et al., 2017]. Wu et al. [2017] used a restricted swap-based neighborhood to improve the tabu search procedure, resulting in the RNS-TS algorithm. Two metaheuristics based on genetic algorithms and simulated annealing were designed to solve MCDS [Hedar et al., 2019]. Li et al. [2019] presented a multi-start local search algorithm called MSLS based on three mechanisms including a vertex score, configuration checking, and vertex flipping. Finally, a meta-heuristic algorithm called ACO-RVNS [Bouamama et al., 2019] was proposed, based on ant colony optimization and reduced variable neighborhood search. Experiments show that, for classic graphs with fewer than 5000 vertices, RNS-TS, MSLS, and ACO-RVNS obtain similar state-of-theart performance.

1.2 Contributions and Paper Organization

Although previous MCDS algorithms have made progress in solving classic graphs, these algorithms still cannot handle massive graphs with millions of vertices. In this work, we focus on solving MCDS on massive graphs, and develop a local search algorithm called NuCDS. The algorithm is based on two novel ideas that are important for dealing with the connectivity constraint and for vertex selection in local search respectively.

The first idea is a hybrid dynamic connectivity maintenance method called HDC. Previous connectivity maintenance methods make the algorithm explore rather large parts of the search space, but they become futile when faced with very large search space. To overcome this issue, we propose a novel tree-based connectivity maintenance (TBC for short) method, which is inspired by spanning trees. Compared to previous methods, the TBC method has a very low complexity, while limiting the algorithm to explore a relatively small part of the search space. To obtain a balance between diversification and intensification, we design the HDC method to alternately switch between previous connectivity maintenance methods and TBC during the search process.

The second idea is a safety-based vertex selection heuristic. We define a new vertex property called safety, which takes into account the differences among dominated vertices. We propose a novel vertex selection rule based on different scoring functions, one of which is safety-based. This is in contrast to previous MCDS algorithms which only use one scoring function. In some sense, the safety-based scoring function can be used as a supplement of traditional scoring functions.

Extensive experiments are carried out to evaluate NuCDS on classical benchmarks used in previous literature and on massive graphs from real-world applications. Experimental results indicate that NuCDS performs better than four stateof-the-art MCDS heuristic algorithms for most instances.

Section 2 introduces preliminary knowledge. In Sections 3 and 4, we describe the hybrid dynamic connectivity maintenance method and the safety-based vertex selection heuristic. Section 5 presents the NuCDS algorithm. Experiments are presented in Section 6, and Section 7 concludes the paper.

2 Preliminaries

An undirected graph G = (V,E) consists of a vertex set V and an edge set E. For an edge e = {u, v}, vertices u and v are the endpoints of the edge. For a vertex v, its neighborhood is NG(v) = {u ∈ V |{u, v} ∈ E}, and its closed neighborhood is NG[v] = NG(v) ∪ {v}. The degree of a vertex v, denoted as dG(v), is defined as |NG(v)|, and ∆G is the maximum number of dG(v) for ∀v ∈ V . Given a vertex set S ⊆ V , NG(S) = ⋃v∈S NG(v) \ S and NG[S] = ⋃v∈S NG[v] stands for the neighborhood and closed neighborhood of S, respectively. G[S] = (VS,ES) is a subgraph in G induced by S such that VS = S and ES consists of all the edges in E whose endpoints are in S.

An undirected graph G = (V, E) is connected when it has at least one vertex and there is a path between every pair of vertices. For convenience, we use G to denote an undirected connected graph in the following parts.

Definition 1. Given an undirected connected graph G, a vertex in G is an articulation vertex iff removing it, together with the edges connected to it, disconnects the graph. The articulation vertex set of G is denoted as art(G).

Given a vertex set D ⊆ V , a vertex v ∈ V is dominated by D if v ∈ N[D], and is non-dominated otherwise. We use D ⊆ V to denote a candidate solution. If G[D] is connected and D dominates all vertices, then D is a connected dominating set (CDS). For a given graph G, the aim of the minimum connected dominating set (MCDS) problem is to find the connected dominating set D with the smallest size.

3 The HDCMethod

In order to solve the performance bottleneck problem caused by the connectivity constraint of MCDS, we introduce a hybrid dynamic connectivity maintenance method (HDC for short). After reviewing two main previous connectivity maintenance methods, we propose our novel tree-based connectivity maintenance method, and finally give the HDC method. For convenience of discussions on complexity, we will use notations m = |VD| and n = |ED|, where G[D] = (VD, ED) is the induced subgraph of current candidate solution D.

3.1 Previous ConnectivityMaintenance Methods

Before introducing HDC, we review two previous methods to handle the connectivity constraint, namely the substractionbased and addition-based methods.

The substraction-based method is used by previous stateof-the-art MCDS algorithms such as RNS-TS [Wu et al., 2017]. In order to keep the connectivity of candidate solution D, during each iteration of local search, the algorithm maintains the candidate removal vertex set, defined as candRemoval(D)=D \ art(G[D]). The traditional approach to computing art(G[D]) is called Tarjan's algorithm [Hopcroft and Tarjan, 1973]. It works as follow: depth first search (DFS for short) is used to determine whether the child vertex of a vertex u can access the ancestor vertex of u without passing through u. 1 If so, then u is not an articulation vertex, and otherwise it is an articulation vertex. The complexity of the substraction-based method is O(m + n).

The addition-based method has two versions. The first version, used in ACO-RVNS [Bouamama et al., 2019] and in MCDS/TS [Morgan and Grout, 2007], works as follow: during each iteration, the algorithm starts from an empty candidate solution D, and iteratively adds a vertex from NG(D) to D until D becomes a feasible solution. The second version, used in GRASP [Li et al., 2017] and MSLS [Li et al., 2019], works as follow: the algorithm allows removing articulation vertices of D, so D may become disconnected. Thus, before vertex u is selected to be added, DFS is used to calculate the number of connected subgraphs of D that v ∈ N(u) belongs to, and the vertex with the largest number is preferred. The complexity of both versions is O(m).

The complexity of the above two methods is at least O(m). This indicates a high commutation time when applied to massive graphs, hindering the performance on masive graphs.

3.2 Tree-based ConnectivityMaintenance Method

To lower the time complexity of connectivity maintenance, we present a novel tree-based connectivity maintenance (TBC for short) method, which is inspired by spanning trees.

1 The child vertex of u is the vertex visited directly after u, while father and ancestor vertices of u are the vertices visited directly and indirectly before u by DFS.

v1

For this purpose, we first introduce the definitions of a spanning tree and a leaf vertex. Given a connected graph G = (V,E), a spanning tree T = (V ′ ,E′ ) is defined as a connected subgraph of G with V ′ = V , E′ ⊆ E, and without any cycles. Given a spanning tree T = (V ′ , E′ ), a vertex v ∈ V ′ is called a leaf vertex if dT (v) = 1 and the leaf set is defined as LS(T ) = {v|dT (v) = 1, v ∈ V ′ }.

Proposition 1. Given a spanning tree T = (V ′ ,E′ ) and its corresponding leaf set LS(T) of graph G = (V,E), LS(T) is a subset of V \ art(G).

Proof: For any vertex v ∈ LS(T), after removing v and relevant edges through v from T, the remaining graph is still a spanning tree of G[V \ {v}]. So G[V \ {v}] remains connected, which means that v is not an articulation vertex of G, inducing that v ∈ V \ art(G). Thus, we can conclude that LS(T) ⊆ V \ art(G). □

Based on the definition and proposition above, we describe TBC as follows. Given a candidate solution D, we maintain a spanning tree T of G[D] and its corresponding leaf set LS(T) during the search process. Each vertex v ∈ LS(T) is allowed to be removed fromD. All other vertices are forbidden to be removed. In contrast to the previous substractionbased method, given a current solution D, TBC calculates an approximate candRemoval(D) = LS(T), which is a subset of D \ art(G[D]). In order to dynamically update candRemoval(D), three updating rules of TBC are described as follows.

Construction Rule: At the initialization phase, both T and LS(T) with respect to G[D] are constructed according to the initial candidate solution D by using breadth first search.

Removing Rule: When vertex v is selected to be removed, its father vertex u needs to be found. If dT (u) = 2, meaning that u becomes a leaf vertex after removing v, LS(T) = LS(T ) \ {v} ∪ {u}. Otherwise, LS(T ) = LS(T ) \ {v}.

Adding Rule: When vertex v is added to the candidate solution D, one vertex u ∈ N(v) ∩ T needs to be selected as the father vertex of v. In order to render larger candRemoval(D), we prefer not to select a leaf vertex in LS(T), and thus we pick the vertex u with the maximum dT (u) among ∀u ∈ N(v) ∩T . If u is a leaf vertex, LS(T ) = LS(T) \ {u} ∪ {v}, else LS(T) = LS(T) ∪ {v}. Lastly, v is set as the child of u in T .

The complexity of the construction rule is O(m + n). When adding or removing a vertex v based on the removing and adding rules, N(v) has to be searched to update T

Algorithm 1: the HDC heuristic

and LS(T ), which has a complexity of O(∆G). To make the TBC method more comprehensive, we present its example in Figure 1 regarding to removing v10 and then adding v1.

3.3 The Main Framework of HDCMethod

For large graphs, TBC is substantially faster than previous connectivity maintenance methods. However, since TBC does not consider all candidate removal vertices, it may miss some high-quality options. As an extreme example, a candidate solution D with a vertex v ∈ D such that D \ {v} is also a connected dominating set. TBC, however, does not consider this option if v is not a leaf vertex of the current spanning tree. In contrast, the substraction-based method using Tarjan's algorithm potentially considers more options for removal because it accurately determines the complete candidate removal vertex set, but its complexity is higher.

In order to take profit from the respective advantages of both methods, a balance must be achieved between the complexity and the accuracy of determining the candidate removal vertex set. We propose a heuristic called hybrid dynamic connectivity maintenance method (HDC) to switch between the two methods. We first define three parameters of the heuristic: 1) parameter NoImpr denotes the maximum number of steps without improving the candidate solution, where NoImpr ∈ [MinNoImpr,MaxNoImpr]; 2) parameter MinNoImpr denotes the minimum value of NoImpr, and it is also adopted as the absolute value of the change on NoImpr in each step; 3) parameter MaxNoImpr denotes the maximum number of steps using the current connectivity maintenance method.

Considering the difference of complexity between the two connectivity maintenance methods, two sets of parameters are respectively set for SUB and TBC.

A formal description of the HDC heuristic is given in Algorithm 1. stepNoImpr and stepOneCon denote the number of non-improving steps and the number of steps adopting one current connectivity maintenance method, respectively.

When the candidate solution has not been improved for Noimpr iterations or the current method has been used for MaxNoImpr iterations (line 1), the algorithm switches from the current connectivity maintenance method to the other one (lines 2-5). In particular, after switching to TBC, a spanning tree T of D and its corresponding leaf set LS(T) need to be constructed (line 4). After the switching operation, NoImpr needs to be updated (line 6). Specifically, if stepNoimp > NoImpr, then the algorithm increases NoImpr by MinNoImpr so that it can search more exhaustively for better candidate solutions. Otherwise, if stepOneCon > MaxNoImpr, the algorithm decreases NoImpr by MinNoImpr in order to accelerate the search. Both stepNoimpr and stepOneCon should be reset to 0 (line 7). Lastly, the algorithm uses the selected connectivity maintenance method to calculate the candidate removal vertex set candRemoval(D) and returns it (lines 8-12).

4 Safety-based Vertex Selection Heuristic

In this section, we introduce a novel vertex selection heuristic by considering the safety of vertices. Before proposing our selection rule, we introduce a previous scoring function.

4.1 Scoring Functions

Local search algorithms typically use scoring functions to choose an operation to execute in each step. In the context of the MCDS problem, a scoring function is used to choose a vertex u ∈ D for removal and a vertex v ∈ N(D) for addition. Our algorithm adopts the frequency based scoring function [Wang et al., 2017] for this purpose. For each vertex v ∈ V , the frequency of v is denoted as freq[v]. It works as follow: 1) before the local search process, freq[v] = 1 for ∀v ∈ V ; 2) at the end of each iteration of local search, freq[v] = freq[v]+1 for each non-dominated vertex v ∈ V .

The scoring function, denoted as score, is calculated as follow: If u ∈ D, score(u) = - ∑v∈C1 freq[v], and otherwise score(u) = ∑v∈C2 freq[v], where C1 is the set of dominated vertices that would become non-dominated by removing u from D and C2 is the set of non-dominated vertices that would become dominated by adding u to D.

4.2 The Safety-based Selection Rule

In addition to considering the score value, we also observe that some dominated vertices are more "endangered" than others, in the sense that they may become non-dominated more easily. An extreme case is a vertex that is dominated just by one vertex (either by itself or by one of its neighbors). Such vertices may become non-dominated due to an exchanging step. Based on this consideration, we define the safety of vertices, taking into account the differences among dominated vertices. We first give the definition of the domination degree.

Definition 2. Given a connected graph G = (V,E) and a candidate solution D, the domination degree of vertex v is defined as ddG(v) = |NG[v] ∩ D|, for each vertex v ∈ V .

This means that a vertex v with ddG(v) = d is dominated by d vertices. Thus, the larger the domination degree, the safer the corresponding vertex. Thus, we define the safety of a vertex v, denoted as sf(v), which measures the accumulative effectiveness of the domination degree. For each v ∈ V , sf(v) = -ddG(v) if v ∈ D, or sf(v) = ddG(v) if v /∈ D.

Different from score, the safety of a vertex measures the domination degree by removing or adding this vertex. For large graphs, ties w.r.t. score frequently occur during vertex selection, that is, more than one vertex has the highest score. In such a situation, we can use the safety as a secondary criterion for further measurement. By doing this, the local search process can be more considerate in vertex selection. In addition, considering the property age 2 is usually used to break ties for the sake of diversification, we propose to use safety and age separately as the secondary criterion for vertex selection. The safety-based vertex selection heuristic in our algorithm is described as follows.

Selection Rule: Select the vertex v with the greatest score, breaking ties by preferring the one with the greatest sf(v). Further ties are broken by picking the one with greatest age if more than one vertex has the greatest score and sf(v) values.

This idea is inspired by the concept of subscore for the SAT problem [Cai and Su, 2013] which considers the satisfaction degree of clauses. Moreover, as far as we know, it is the first time that the definition of safety is considered to be applied into solving a graph optimization problem.

5 NuCDS Algorithm

Based on HDC and the safety-based vertex selection heuristic, we develop a local search algorithm for the MCDS problem named NuCDS. To avoid visiting previous candidate solutions, we use the CC2 strategy [Wang et al., 2017] in the adding process, and use the tabu strategy [Glover and Laguna, 1998] recording the adding operations to prevent removing a just added vertex for the next tt iterations. In our work, tt = 5 + rand(10). The pseudo code of NuCDS is shown in Algorithm 2.

In the beginning, NuCDS initializes score and sf (line 1), and sets curMethod = TBC which means that the TBC method is selected as the initial connectivity maintenance method (line 2). The non-improvement step stepNoimpr and the number of steps used by the current connectivity maintenance method stepOneCon are both set to 0 (line 2). Then, the algorithm constructs the initial candidate solution D using the approximation algorithm in [Khuller and Yang, 2019] (line 3). According to the construction rule, the algorithm builds a spanning tree T of D (line 4), and then the candidate removal vertex set candRemoval(D) is initialized to LS(T) (line 5).

During the local search procedure (lines 6-19), the algorithm first uses the HDC heuristic to update candRemoval(D) (line 7). If D is a feasible solution, which means that the algorithm has already found a connected dominating set of size |D|, D∗ is updated to D and stepNoimpr is set to 0 (line 9). Then, the algorithm continues to find a solution of size (|D| - 1), i.e., by removing a vertex v from D using the BMS heuristic [Cai, 2015] (lines 10-11).

2 The age of a vertex v is the number of steps that have occurred since v last changed its state.

Specifically, the algorithm randomly selects k vertices from candRemoval(D) and picks from this set the removal vertex u according to the selection rule (in our work, k is set to 45). If the algorithm selects the TBC method as the current connectivity maintenance method, the corresponding spanning tree T and its leaf set LS(T) should be updated based on the removing rule (line 12).

If D is still an infeasible solution, the algorithm tries to exchange two vertices (lines 14-17), i.e., removing a nontabu vertex u ∈ candRemoval(D) from D via the BMS heuristic and the selection rule, and then adding a vertex v ∈ N(D) ∩ N(G \ N[D]) to D via the CC 2 strategy and the selection rule, where G \ N[D] is the non-dominated vertex set and N(D) contains vertices maintaining connectivity. Finally, the algorithm needs to update T, LS(T), stepOneCon, and stepNoimpr accordingly (lines 18-19). When the time limit is reached, the best solution found (D∗ ) will be returned. The complexity of each iteration in the local search process is O(|D|) or O(∆G) when using SUB or TBC methods respectively.

Moreover, we make use of a trick for adopting the HDC heuristic. If |D| < 100 ( that is, if the complexity of the SUB method is acceptable), using TBC becomes trivial and thus we only use the SUB method under such a situation.

6 Experimental Evaluation

We carry out extensive experiments to evaluate the performance of NuCDS. We compare NuCDS with four state-ofthe-art heuristic algorithms: MSLS [Li et al., 2019], ACORVNS [Bouamama et al., 2019], ACO-efficient 3 and RNSTS [Wu et al., 2017]. The codes of all competitors were kindly provided by the authors. RNS-TS was implemented in Java while NuCDS and the other competitors were implemented in C++ and complied by g++ with '-O3'. Data structure was modified to handle massive graph. Moreover, ACOefficient was modified by the author of ACO, specialized for massive graphs. All experiments were run on a server with Intel Xeon E7-4830 v4 2.00GHz with 256GB RAM under Ubuntu 16.04.5.

For our experiments, we adopt several popular benchmarks which are divided into two groups, including classical benchmarks and massive graphs. First we considered 121 classical benchmarks, which are mainly divided into five groups: the instances of the maximum leaf spanning tree problem [Lucena et al., 2010], bus power flow test cases 4 , random geometric graphs [Jovanovic and Tuba, 2013], and random graphs from [Erdem et al., 2009] and from [Bouamama et al., 2019]. All these classical instances have already been used for testing the effectiveness of the competitors [2019].

We also evaluated NuCDS on massive graphs, including massive real-world graphs from the Network Data Repository (NDR) [Rossi and Ahmed, 2015] and Stanford Large Network Dataset Collection (SNAP) 5 , as well as large in-

3 We contacted the author of ACO-RVNS to get an improved version called ACO-efficient, which performs better than ACO-RVNS on most large instances.

4 http://labs.ece.uw.edu/pstca

5 http://snap.stanford.edu/data

Algorithm 2: the NuCDS algorithm

Input: An undirected graph G = (V, E), the cutoff time Output: An obtained best connected dominating set D∗ 1 initialize score(v), sf(v), for ∀v ∈ V ; 2 curMethod :=TBC, stepNoimpr := stepOneCon := 0; 3 D := ConstructCDS(G), D∗ :=D; 4 build a spanning tree T according to Construction Rule; 5 candRemoval(D) := LS(T); 6 while elapsed time < cutoff do 7 candRemoval(D) :=HDC(D); 8 if D is a connected dominating set then 9 D∗ :=D, stepNoimpr := 0; 10 select a vertex u ∈ candRemoval(D) by BMS according to Selection Rule; 11 D := D \ {u}; 12 if curMethod==TBC then update T and LS(T ) according to Removing Rule; 13 continue; 14 select a vertex u ∈ candRemoval(D) by BMS according to Selection Rule; 15 D :=D \ {u}; 16 choose a vertex v ∈ N(D) ∩ N(G \ N[D]) according to Selection Rule; 17 D :=D∪ {v}; 18 if curMethod==TBC then update T and LS(T) according to Removing and Adding Rules; 19 stepNoimpr++, stepOneCon++;

20 return D∗ ;

stances from the 10th DIMACS implementation challenge (DIMACS10) 6 . As in previous work [Lin et al., 2017], we only report the results on graphs from the SNAP and DIMACS10 benchmarks with at least 30,000 vertices (with the exception of a few cases with fewer vertices). Moreover, due to space limitations, we do not report the results on graphs from the NDR benchmark with fewer than 100,000 vertices or fewer than 1,000,000 edges. Hence, we picked 22, 31 and 65 instances from SNAP, DIMACS10, and NDR benchmarks respectively, leading to totally 118 massive graphs.

All algorithms were executed 10 times on each instance independently. The cutoff time was set to 1000 seconds for the classical benchmarks, and 3600 seconds for massive graphs. We report the the best size (min) and the average size (avg) of the solutions found. If an algorithm fails to find a solution within the time limit, this is indicated by 'N/A'.

In preliminary experiments we found that NuCDS is not very sensitive to parameter settings. According to these experiemnts we set MinNoImpr=100 when using SUB, and MinNoimpr=100000 when using TBC. NoImpr and MaxNoImpr were set as 2×MinNoImpr and 10×MinNoImpr, respectively.

6 https://www.cc.gatech.edu/dimacs10/

6.1 Results on Classical Benchmarks

Most instances of classical benchmarks are so easy that all algorithms obtain the same solution quality very quickly. We ignore these instances, but we report the average run time when all algorithms obtain the same minimal and average values in Figure 2, which shows the effectiveness of NuCDS.

We present the results for the remaining 55 classical instances in Table 1. NuCDS obtains better solutions than MSLS, ACO-efficient, ACO-RVNS and RNS-TS for 31, 33, 19 and 25 instances, respectively, while NuCDS fails to match the solutions obtained by some competitors only on 6 instances. For the instances where NuCDS generates a solution with the same value as the best competitor, NuCDS obtains better average size for 8 instances with 3 exceptions.

6.2 Results onMassive Graphs

Tables 2 and 3 show the results of NuCDS and all competitors on massive graphs. Once again, the results of NuCDS are significantly better than those of all competitors for most of the considered graphs. This is with the exception of only five graphs. Moreover, NuCDS can solve all these 118 instances within the time limit, while MSLS, ACO-efficient, ACO-RVNS and RNS-TS can only solve 45, 48, 18, and 26 instances, respectively. Among all those solvable instances, the best solution values obtained by NuCDS are on average 1.79%, 7.38%, 0.51%, and 85.77% smaller than these found by MSLS, ACO-efficient, ACO-RVNS, and RNS-TS, respectively. The excellent results of NuCDS on massive graphs can mainly be attributed to the power of the HDC heuristic.

Two reasons account for why competitors cannot output feasible solutions on some instances: 1) The construction processes of MSLS, ACO and ACO-efficient have a complexity of O(|V |2 ). They are essential parts of multi-restart and ACO framework, so we reserve them; 2) The complexity of each step is O(|V |2 ) in RNS, often trapping in the first iteration. Because |V | of some instances reaches to 107 , competitors fail to output feasible solution.

6.3 Effectiveness of Proposed Strategies

As shown in Table 4, three modified versions of NuCDS are proposed to verify the effectiveness of HDC and safety, especially on massive graphs. We compared NuCDS with NuCDS1 to show the effectiveness of safety, and with NuCDS2 and NuCDS3 to show the effectiveness of HDC. The results in Table 5 confirm that both strategies are effective. Moreover, when compared with SUB, HDC improves the average best solution by 17.285% on massive graphs.

7 Conclusion

We proposed two new algorithmic components, namely the hybrid dynamic connectivity maintenance heuristic and the safety-based vertex selection heuristic, for MCDS. Both components were used to develop an efficient local search algorithm named NuCDS. We conducted extensive benchmarks to evaluate the performance of NuCDS and the experimental results showed that our algorithm significantly outperforms its competitors on almost all the instances of any size.

Acknowledgements

This work was supported by Beijing Academy of Artificial Intelligence (BAAI), Youth Innovation Promotion Association, Chinese Academy of Sciences [No. 2017150], and NSFC Grant 61806050.