Two-goal Local Search and Inference Rules for Minimum Dominating Set

1 Introduction

Given an undirected graph G = (V, E), a dominating set D is a subset of vertices such that each vertex in V \ D has at least one adjacent vertex in D. Dominating set is an important concept in graph theory, and have applications in diverse areas, especially in social networks [Wang et al., 2009; Chalupa, 2018]. One typical problem is to find a smallest group of influential individuals or a set of initial seeds in a social network, so that all participants can be reached with only one hop from the seeds. This problem is equivalent to finding a minimum dominating set (MinDS) for the network.

The MinDS problem is a classic NP-hard problem, and cannot be approximated with a constant ratio under the assumption P ̸= NP [Raz and Safra, 1997]. Moreover, negative results have been proved for the approximation of MinDS even when limited to power law graphs [Gast et al., 2015]. A number of works have been done on exact algorithms for MinDS, which mainly focus on improving the upper bound of running time. State-of-the-art exact algorithms for MinDS are based on the branch and reduce paradigm and can achieve a run time of O(1.4969n ) [van Rooij and Bodlaender, 2011]. Fixed parameterized algorithms have allowed to obtain better complexity results [Karthik C. S. et al., 2018]. The main focus of such algorithms is on theoretical aspects.

∗Corresponding author

In practice, one usually resorts to heuristic approaches to obtain good solutions within reasonable time. Although greedy algorithms are fast, the obtained dominating sets are far from satisfactory. A comparison among several greedy heuristics for MinDS can be found in [Sanchis, 2002]. Heuristic search algorithms usually return very good or even optimal solutions within a reasonable time budget. Commonly used heuristic search methods, including genetic algorithm [Hedar and Ismail, 2010] and ant colony optimization [Jovanovic et al., 2010; Potluri and Singh, 2011; Potluri and Singh, 2013], have been developed to solve MinDS. Hyper meta-heuristic algorithms combine different heuristic search algorithms and preprocessing techniques to obtain better performance [Potluri and Singh, 2013; Chaurasia and Singh, 2015; Bouamama and Blum, 2016; Lin et al., 2016; Abu-Khzam et al., 2017]. These algorithms were tested on standard benchmarks with up to thousand vertices. Recently, the configuration checking (CC) strategy [Cai et al., 2011] has been applied to MinDS and led to two local search algorithms. Wang et al. proposed the CC2FS algorithm for both unweighted and weighted MinDS [Wang et al., 2017], and obtained better solutions than ACO-PP-LS [Potluri and Singh, 2013] on standard benchmarks. Afterwards, another CC-based local search named FastMWDS was proposed, which significantly improved CC2FS on weighted massive graphs [Wang et al., 2018]. Chalupa proposed an orderbased randomised local search named RLSo [Chalupa, 2018], and achieved better results than ACO-LS and ACO-PP-LS [Potluri and Singh, 2011; Potluri and Singh, 2013] on standard benchmarks of unit disk graphs as well as some massive graphs. Very recently, Fan et. al. designed a local search algorithm named ScBppw [Fan et al., 2019], based on two ideas including score checking and probabilistic random walk.

This work develops an efficient and robust algorithm for MinDS named FastDS, which achieves best results on almost all standard and massive benchmarks, and significantly outperforms state of the art algorithms on massive benchmarks. There are two main novel ideas in FastDS. The first one is a new local search framework. A typical local search framework for MinDS, is to solve the problem by iteratively solving the k-DS problem- given an integer k, searching for a k sized dominating set [Fan et al., 2019]. Specifically, when finding a k sized feasible solution, the algorithm removes one vertex and goes on to search for a (k - 1) size solution, by exchanging a pair of vertices in each step. We propose a new local search framework. When finding a k size feasible solution, our algorithm goes on to search for a solution with (k-1) or (k-2) size. That is, our algorithm targets two goals during the search. This accelerates the convergence speed, and also expands the search region.

Moreover, we propose inference rules for MinDS, which are used to fix vertices that must be in some optimal solution. The inference rules are particularly useful for solving massive graphs. In order to solve combinatorial optimization problems on massive graphs, reduction rules have been implemented to reduce the size of the graphs. Examples include maximum clique [Cai and Lin, 2016], vertex cover [Cai et al., 2017], k-plex [Gao et al., 2018], as well as the weighted dominating set problem [Wang et al., 2018]. Unfortunately, reduction rules become very restricted when coming to the MinDS problem, due to the special feature of the problem. For example, even if we can fix the value of a vertex to be 1 (being selected), we cannot delete it from the graph, as this vertex may be responsible for dominating other vertices in the remaining graph. Although there are some reduction rules for minimum weighted dominating set, they are based on the differentials among vertex weights [Wang et al., 2018], and cannot be applied to MinDS as all vertices have the same weight there. We propose a compromise solution to design inference rules rather than reduction rules. We fix the value of some vertices using inference, without deleting them.

We conduct extensive experiments to compare FastDS with state-of-the-art heuristic algorithms on a broad range of benchmarks, including 4 standard benchmarks and 3 massive graphs benchmarks. FastDS obtains the best results for almost all benchmarks, and significantly outperforms state-ofthe-art algorithms on the 3 massive benchmarks.

The paper is organized as follows. Section 2 presents basic definitions. Section 3 introduces the new local search framework. Sections 4 presents the inference rules. Section 5 describes our FastDS algorithm. Experimental results are shown in Section 6 and Section 7 gives concluding remarks.

2 Preliminaries

An undirected graph G = (V,E) consists of a vertex set V and an edge set E. Each edge e = (v, u) connects two vertices v and u, which are also called endpoints of e. Two vertices are neighbors if they belong to a same edge. For a vertex v, N(v) = {u ∈ V |(u, v) ∈ E} is the set of neighbors of v, and the degree of v is degree(v) = |N(v)|. The closed neighborhood of v is N[v] = N(v) ∪ {v}. Also, we use N 2 [v] to denote the set of v's closed neighborhood and its neighbors' neighbors, i.e., N 2 [v] = N[v]∪(⋃u∈N(v) N(u)). For a vertex set S ⊆ V , we use N[S] = ⋃v∈S N[v] to denote the closed neighborhood of S.

A candidate solution (also known as partial solution) for MinDS is a subset of V . Given a candidate solution D, the value of a vertex v, denoted as value(v), indicates whether it is selected in the candidate solution or not, which is 1 if v ∈ D, and 0 otherwise. A vertex v is dominated by a candidate solution D if v ∈ N[D], and is non-dominated otherwise. The cost of a candidate solution D, denoted as cost(D), is defined as the number of non-dominated vertices under D. A commonly used scoring function for MinDS is defined as

where D′ = D \ {v} if v ∈ D, and D′ = D ∪ {v} otherwise. Obviously, score(v) ≤ 0 if v ∈ D, and score(v) ≥ 0 if v /∈ D.

We use D to denote the current candidate solution, i.e., the set of vertices currently selected for dominating, and U to denote the set of non-dominated vertices. D∗ is the best solution found so far, and D∗ at the end of the algorithm is returned by the algorithm. The age of a vertex v is the number of steps that have occurred since v last changed its state.

3 Two-goal Local Search

We propose a novel local search framework for MinDS, which allows the algorithm to target two different sizes during each period of the search.

For subset problems whose goal is to find a minimum set satisfying given constraints, such as MinDS, minimum vertex cover (MinVC) and minimum set cover, a popular paradigm of local search is to iteratively find a feasible solution of a fixed size [Musliu, 2006; Richter et al., 2007; Cai et al., 2013; Gao et al., 2015; Fan et al., 2019; Li et al., 2019]. Specifically, when finding a k-sized solution, the algorithm focuses on searching for a (k-1)-sized solution by fixing the size of the partial solution to be k-1 at the end of each step. To this end, a popular local search framework is the two-stage exchanging framework [Cai et al., 2013], where one vertex is removed from the partial solution in the first stage and another vertex is added in the second stage. Because of its good performance and low complexity, the two-stage exchanging framework has been applied to local search algorithms for the MinDS problem [Fan et al., 2019].

We propose a new local search framework for MinDS (Algorithm 1). The local search starts from an initial feasible solution (line 2) and searches for a feasible solution as small as possible. Specifically, when D becomes a feasible solution, D∗ is updated (line 5) and then a vertex is removed from D (line 6). When D is not a feasible solution, the algorithm iteratively exchanges vertices until D becomes a new dominating set. It first removes vertices to make |D| = |D∗ | - 3; in the adding phase, one vertex is added to D, and after that, if D is still infeasible, another vertex is added with a certain probability. Thus, the size of D can be |D∗ | - 1 or |D∗ | - 2 at the end of a search step. Finally, the best found dominating set D∗ is returned when the time limit is reached.

Previous local search algorithms focus on seeking a (k-1)- sized solution after finding a k-sized solution. Differently, our framework searches for a (k-1)-sized or (k-2)-sized solution after it finds a k-sized solution. This has two advantages. (1) It accelerates the converge of the search, as the algorithm sometimes directly finds a (k-2)-sized solution without finding a (k-1)-sized one. Note that if we set the goal to be (k-2) after finding a k-sized solution, we would fail to find the optimal solution if its size is (k-1). Our framework with two goals can improve the search efficiency without losing the ability to find the optimal solution. (2) It expands the search region for

Input: An undirected graph G = (V, E) Output: A dominating set D of G 1 begin 2 D←ConstructDS(); 3 while elapsed time < cutoff do 4 if all vertices are dominated then 5 D∗ ← D; 6 remove a vertex from D; 7 continue; 8 Remove vertices from D until |D| = |D∗ | - 3; 9 Add one vertex to D; 10 if ∃ non-dominated vertices then 11 if with certain probability then 12 Add another vertex to D; 13 return D∗ ;

the adding stage by keeping a smaller candidate solution at the end of the removing stage. A smaller candidate solution leads to a larger N[U] (U is the set of non-dominated vertices), which implies more candidate adding vertices in the adding stage. Finally, we note that our local search framework can be applied to other subset problems.

4 Inference Rules for MinDS

To improve the performance of local search for MinDS on large instances, we propose three inference rules, which can fix a considerable portion of the vertices for massive graphs.

Isolated vertex rule: If a vertex v is not adjacent to any other vertices, or all its neighbors have a fixed value 0 (not selected), then v's value is fixed to 1.

This rule is obvious: in order to make the vertex v dominated, there is only one option - including v in the solution.

Leaf rule: If a vertex v is adjacent to only one vertex u, or all its neighbors but u have a fixed value 0, then value(u) is fixed to 1 and value(v) is fixed to 0.

The reasoning of this rule is as follows. In order to dominate vertex v, at least one of u and v should be selected, and we prove that the best way to do so is to choose u and not choose v. (1) If both u and v are selected in a dominating set D, then D\{v} is a smaller dominating set; (2) If v is selected and u is not, i.e., v ∈ D and u /∈ D, then we can exchange u and v and the resulting set D\ {v}∪{u} is still a dominating set, as removing v can only have impact on vertices u and v, and by adding v we dominate both of them.

Triangle rule: For a triangle {u, v,w} in the graph, where N(u) = {v,w}, N(v) = {u,w} and N(w) ⊃ {u, v}, value(w) is fixed to 1 while value(u) and value(v) are fixed to 0.

The reasoning follows as this: For any dominating set D, in order to dominate vertices u and v, at least one vertex from {u, v,w} is in D. Now, since N[u] = N[v] = {u, v,w} ⊂ N[w], we know that, any vertex that can be dominated by u and v can be dominated by w, but not vice versa.

We can generalize the Triangle rule as follows. However, due to the high computation cost, the generalized rule is not implemented in our algorithm.

Generalized Triangle rule: For a vertex w and a vertex set S ⊆ N(w), if N[S] ⊂ N[w], then value(w) is fixed to 1, and the value of any vertex in S is fixed to 0.

5 The FastDS Algorithm

We develop a local search algorithm for MinDS named FastDS (Algorithm 3), which is based on our two-goal framework and employs inference rules.

5.1 Initial Construction

In the beginning, the algorithm constructs an initial solution by a greedy construction procedure, making use of the inference rules. A key concept of the algorithm is the nondominated neighborhood and non-dominated degree.

Definition 1. Given a graph G = (V, E) and a vertex subset D, the non-dominated neighborhood of a vertex v is Nr[v] = {u|u ∈ N[v], N[u] ∩D = ∅}, and the non-dominated degree of v is degreer(v) = |Nr[v]|.

Intuitively, the set Nr[v] includes all the vertices that are currently non-dominated and would be dominated if v is added to the candidate solution D. Thus, degreer(v) measures the benefits of adding vertex v.

The construction procedure fist traverses all vertices and employs inference rules to fix the vertices satisfying at least one of the rules. Then, it utilizes a greedy strategy based on non-dominated degrees to iteratively add vertices until a dominating set is obtained. At the end of the construction, redundant vertices are removed from D to make it minimal.

Algorithm 2: FastDS

Input: An undirected graph G = (V, E) Output: A dominating set D∗ of G 1 begin 2 D←ConstructDS(G); 3 while elapsed time < cutoff do 4 if U = ∅ then 5 remove redundant vertices fromD; 6 D∗ ← D; 7 remove a vertex with highest score from D; 8 u1 ← a vertex in D according to BMS heuristic; 9 D ← D \ {u1}; 10 if |D| = |D∗ | - 2 then 11 u2 ← a random vertex from D; 12 D ← D \ {u2}; 13 v1 ← a vertex in N[U] with highest score, breaking ties by age; 14 D ← D ∪ {v1}; 15 if U ̸= ∅ then 16 if with probability α then 17 v2 ← a vertex in N[U] with highest score, breaking ties by age; 18 D ← D ∪ {v2}; 19 return D∗ ;

5.2 Local Search

The constructed initial solution is then fed to the local search phase for improving. During the local search process, whenever D becomes a feasible solution, redundant vertices (if any) are first removed fromD, and D∗ is updated to D. After that, a vertex with the maximum score (i.e., the minimum loss) is removed. Then, the local search iteratively executes exchanging steps until D becomes a feasible solution.

Each exchanging step consists of a removing stage and an adding stage. In the removing stage (lines 8-12), one or two vertices are removed from D. The first vertex u1 is selected from D according to a sampling heuristic named Best fromMultiple Selections (BMS) [Cai, 2015], which randomly samples t vertices in D and picks the one with the maximum score to remove (t is suggested near 50 [Cai, 2015] and is set to 45 in this work). If there is more than one such vertex, the vertex with the largest age is selected to remove. Additionally, after u1 is removed fromD, if |D∗ |-|D| equals 2 rather than 3, one more vertex is removed, to ensure |D| = |D∗ | - 3 at the end of the removing stage.

In the adding stage (lines 13-18), one or two vertices are added into D. First, a vertex v1 ∈ N[U] (U is the set of nondominated vertices) with the highest score is added to D, breaking ties by preferring the one with largest age1 . Then, if there are non-dominated vertices, with a probability of α, a second vertex v2 is selected in the same way as the first one and added to D.

An important implementation detail is that, when removing or adding a vertex x, the score of vertices in N 2 [x] may change, and should be updated accordingly.

6 Experiments

We evaluate FastDS on 7 benchmarks, including 4 standard benchmarks in the literatures and 3 massive benchmarks.

UDG: This is a widely used standard benchmark for MinDS [Hedar and Ismail, 2010; Potluri and Singh, 2011; Potluri and Singh, 2013; Chalupa, 2018]. UDG contains 120 instances generated by the topology generator 2 . UDG is divided into 12 families, each of which has 10 instances.

T1: This data set consists of 520 instances where each instance has two different weight functions [Jovanovic et al., 2010]. We select these original graphs where the weight of each vertex is set to 1. There are 52 families, each of which contains 10 instances with the same size. To save space, we do not report the results on graphs with 50 vertices.

DIMACS: This benchmark is from the Second DIMACS Implementation Challenge (1992-1993) 3 , including problems from real applications and randomly generated graphs.

BHOSLIB: This benchmark are generated based on the RB model [Xu et al., 2007] near the phase transition. It is a popular benchmark for graph theoretic problems.

1 In practice, acceleration can be gained for the classic benchmarks by picking a random non-dominated vertex with a small probability such as 0.005 here.

2 http://www.michelemastrogiovanni.net/software/download/

3 ftp://dimacs.rutgers.edu/pub/challenges

SNAP: This benchmark is from Stanford Large Network Dataset Collection 4 . It is a collection of real world graphs from 104 vertices to 107 vertices.

DIMACS10: This benchmark is from the 10th DIMACS implementation challenge (2010) 5 , which aims to provide large challenging instances for graph theoretic problems.

Network Repository: The Network Data Repository [Rossi and Ahmed, 2015] collects massive graphs from various areas. Many of the graphs have 100 thousands or millions of vertices. This benchmark has been widely used for graph theoretic problems including vertex cover, clique, coloring, and dominating set problems.

For SNAP and DIMACS10 benchmarks, as in previous literatures [Lin et al., 2017; Verma et al., 2015], we only report the results on graphs with at least 30000 vertices. For Repository benchmark, we choose the graphs with at least 105 vertices. This results in 22, 31 and 65 graphs in SNAP, DIMACS10, and Repository, respectively.

6.1 Experiment Setup

FastDS is implemented in C++ and complied by g++ with '- O3' option, and the parameter α is set to 0.6. All experiments are run on a server with Intel Xeon E5-2640 v4 2.40GHz with 128GB RAM under CentOS 7.5.

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

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

We compare FastDS with four state-of-the-art heuristic algorithms, including CC2FS [Wang et al., 2017], FastMWDS [Wang et al., 2018], RLSo [Chalupa, 2018] and ScBppw [Fan et al., 2019]. CC2FS is good at solving standard benchmarks, while FastMWDS and ScBppw are designed to solve massive graphs, and RLSo is a recent algorithm that outperforms previous ant optimization and hyper meta-heuristic algorithms. The codes of CC2FS, FastMWDS and RLSo were kindly provided by their authors while the codes of ScBppw were open online 6 . All of them are implemented in C++ and complied by g++ with '-O3' option.

For each instance, all algorithms are executed 10 times with random seeds 1,2,3...10. The time limit of each run is 1000 seconds. For each instance, we report the best size (Dmin) and the average size (Davg) of the solutions found over the 10 runs. When Davg = Dmin, we do not report Davg. For UDG and T1, we report for each family the averaged value of Dmin, denoted as Dmin. When failing to find a solution in time limit, the cell is marked as 'N/A'.

6.2 Results on Standard Benchmarks

Results on UDG, T1 and BHOSLIB benchmarks are reported in Tables 1, 2 and 3 respectively. The DIMACS instances are so easy that CC2FS, FastMWDS and FastDS find the same solutions on all the instances quickly, but RLSo and ScBppw are worse. For all standard benchmarks, FastDS has the best performance in terms of solution quality, except slightly worse than CC2FS and FastMWDS on UDG benchmark. Over all standard benchmarks, CC2FS, FastMWDS and FastDS are essentially better than the other algorithms. We compare the averaged run time of these three algorithms on these benchmarks (Table 4), where the run time of each run of an algorithm is the time to reach the final solution.

6 https://github.com/Fan-Yi/

6.3 Results onMassive Benchmarks

Results on SNAP and DIMACS10 benchmarks are reported in Table 5, and results on Repository benchmarks are reported in Table 6. CC2FS is dominated by FastMWDS on all the instances and not reported in Tables 5 and 6. FastDS performs best for all the massive benchmarks. It obtains the best solutions for 19 (out of 22) SNAP instances, 28 (out of 31) DIMACS10 instances and 63 (out of 65) Repository instances. On average, the best solutions found by FastDS have 1320 and 23732 fewer vertices than the strongest competitor FastMWDS for SNAP and DIMACS10 benchmarks, and have 14150 fewer vertices than the strongest competitor ScBppw for Repository benchmark. Table 7 summarizes the comparison results on all the benchmarks.

6.4 Analysis of Underlying Ideas

We calculate the portion of vertices fixed by inference rules among all vertices, and compare the run time of the construction procedure with and without the rules (Table 8). The inference rules are effective on the massive benchmarks with little overhead. FastDS without the rules degrades obviously on the massive benchmarks. It gets worse solutions on half Repository instances. However, the rules have little impact on the standard benchmarks.

We also test a variant of FastDS (denoted as FastDS g1) that uses the one-goal framework (targeting size of (k-1) after finding a k sized solution) to replace our two-goal framework. FastDS finds better solutions than FastDS g1 on 12, 48 and 31 instances for UDG, T1 and BHOSLIB benchmarks respectively, and worse on none of the instances. For massive benchmarks, FastDS finds better solutions on 11, 25 and 39 instances for SNAP, DIMACS10 and Repository respectively, while worse than FastDS g1 only on 3 and 9 instances in DIMACS10 and Repository benchmarks respectively.

7 Conclusions

We proposed a two-goal local search framework for MinDS and proposed three inference rules. The resulting algorithm FastDS is robust and efficient on standard benchmarks and massive benchmarks, and significantly outperforms state-ofthe-art algorithms on massive benchmarks. We would like to study the ideas for other subset problems.

Acknowledgements

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