An Exact Algorithm for the Minimum Dominating Set Problem

1 Introduction

Given an undirected graph G = (V, E), where V is the set of vertices and E is the set of edges. Two vertices are neighbors if there is an edge between them. A dominating set D is a subset of V such that every vertex of G is either in D or has at least one neighbor in D. The Minimum Dominating Set (MDS) problem consists in finding a dominating set D with the smallest cardinality for a given graph G.

MDS and its variants find applications in diverse areas, including multi-document summarization [Shen and Li, 2010], influences among individuals in social networks [Dinh et al., 2014], routing in ad hoc wireless networks [Dai and Wu, 2004], graph mining [Chalupa, 2018] and action recognition in computer vision [Yao and Fei-Fei, 2012].

Solving MDS in general graphs is NP-Hard [Karp, 1972; Garey and Johnson, 1979]. On the theoretical side, Rooij and Bodlaender [2011] proved that there is a branch-andreduce algorithm that solves MDS in O(1.4969n ) time and polynomial space, where n is the number of vertices. Dinur and Steurer [2014] proved that obtaining a (1 - ε) ln(n)- approximation for MDS is NP-hard for every ε > 0 unless NP ⊆ DTIME(nO(log logn) ). Gast et al. [2015] proved that MDS on power law graphs cannot be approximated within an approximation ratio of Ω(ln(n)). Raz and Safra [1997] gave a lower bound of approximation of c ln(n) under the assumption of P ̸= NP. In general, theoretical work for MDS mainly focuses on improving the approximation ratio and the upper bound of time complexity of exact algorithms.

∗Corresponding author

Due to the relevance of MDS to practical applications, there is a lot of work on heuristic algorithms for MDS. Experimental analysis and comparison of early heuristic algorithms can be found in [Sanchis, 2002]. Hybrid genetic and ant-colony optimization algorithms for MDS were proposed in [Hedar and Ismail, 2010; Potluri and Singh, 2011]. Hybrid meta-heuristic algorithms based on evolutionary and memetic approaches were proposed for the Minimum Weight Dominating Set (MWDS) problem in [Chaurasia and Singh, 2015; Lin et al., 2016], which is a generalization of MDS. In recent years, several local search algorithms were proposed for MDS and its variants. Wang et al. [2017; 2018] proposed two local search algorithms based on configuration checking strategy and frequency scoring function for MWDS. Fan et al. [2019] proposed a local search based on tabu and probabilistic walk strategy for MDS in large graphs. Cai et al. [2020] proposed a two-goal local search and inference rules for MDS. Lei and Cai formulated MDS into maximum satisfiability and proposed a specific local search to solve MDS [Lei and Cai, 2020]. Li et al. [2020] proposed a local search for the minimum connected dominating set problem.

Compared to heuristic algorithms, exact algorithms for solving MDS are almost absent in the literature. Although MDS is a subgraph problem in general, solving MDS is quite different from solving other subgraph problems, such as the Maximum Clique (MC) problem. When an algorithm searches on a partial solution for MC, those vertices that are inconsistent with the partial solution can be discarded safely, resulting in a substantial reduction of search space. Whereas, each vertex outside the partial solution for MDS could be a candidate for the final solution. The actual search space for MDS is much bigger than the search space for MC. Therefore, solving MDS exactly is more challenging than solving other subgraph problems like MC in the view of practice.

In this paper, we present an effective exact algorithm for MDS, which implements a branch-and-bound (BnB) approach. To reduce the search space, we propose a novel lower bound for MDS, which is derived from a new notion of 2-hop adjacency of vertices of G. Two vertices are 2-hop adjacent if and only if they are neighbors or have common neighbors. We prove that two vertices cannot be dominated by a single vertex if they are not 2-hop adjacent. With this property, we define a notion called 2-hop graph of G and prove that the cardinality of any independent set of the 2-hop graph is a lower bound of MDS in G. We design a sophisticated algorithm to exploit the new lower bound to reduce the number of branches at each search tree node in the BnB algorithm.

Extensive experiments were conducted to evaluate the performance of the new algorithm and the lower bound. The results show that the lower bound can reduce the search space efficiently and the proposed BnB algorithm is effective for the standard instances for MDS and even can solve MDS in real-world large graphs. To the best of our knowledge, this is the first effective BnB algorithm for MDS.

The paper is organized as follows: Section 2 gives basic graph notations and definitions. Section 3 presents the new lower bound. Section 4 gives a BnB algorithm for MDS. Section 5 reports on the empirical results. Section 6 concludes.

2 Preliminaries

Let G = (V, E) be an undirected graph with n vertices and m edges. Two vertices u and v are neighbors or adjacent, if there is an edge between u and v, i.e., (u, v) ∈ E. We use NG(v) to denote the set of neighbors of a vertex v in G, i.e., NG(v) = {u|(u, v) ∈ E}. NG(v) is also denoted by N(v) if the context is clear. The degree of a vertex v, denoted by deg(v), is the cardinality of NG(v). Following previous literature, NG[v] is defined as NG(v) ∪ {v} in this paper. Let S be a subset of V , NG[S] is defined as ⋃v∈S NG[v].

A subset D of V is a dominating set of G if and only if it holds that N(v) ∩D ̸= ∅ for each vertex v ∈ V \D. A dominating set D of the smallest size is the minimum dominating set in G. If a vertex u is adjacent to v, we say that u can dominate v in G, vice versa. Moreover, we give a definition of subset dominating.

Definition 1 (Subset Dominating). Let G = (V,E), D and U be two subsets of V . We say D can dominate U if it holds that u ∈ D or N(u) ∩ D ̸= ∅ for each u ∈ U.

A subset of V is an Independent Set (IS) if every pair of vertices in the set is nonadjacent. An IS becomes conflicting if it contains adjacent vertices and the adjacent vertices are called conflicting vertices. We use G[S] to denote the subgraph of G = (V,E) induced by a subset S ⊆ V , i.e., G[S] = (S, E′ ), where E′ = {(u, v)|u, v ∈ S, (u, v) ∈ E}.

3 ANew Lower Bound for MDS

In this section, we propose a novel lower bound for MDS. The lower bound is based on a notion called 2-hop adjacent. We first give the definitions of 2-hop adjacent and 2-hop graphs, then introduce the new lower bound for MDS.

Definition 2 (2-hop adjacent). Given a graph G = (V,E), two vertices u and v are 2-hop adjacent in G if and only if u and v are adjacent or they have common neighbors, i.e., (u, v) ∈ E or NG(u) ∩ NG(v) ̸= ∅.

We call u and v 2-hop adjacent because the distance between u and v is smaller than or equal to 2 (hops) in G.

Definition 3 (2-hop graphs). Given a graph G = (V,E), we define a new graph G2 = (V,E2 ) for G, where E2 = {(u, v)|(u, v) ∈ E or NG(u)∩NG(v) ̸= ∅}, i.e., two vertices u and v are adjacent in G2 if and only if u and v are 2-hop adjacent in G. G2 is called the 2-hop graph of G.

We use G2 [U] to denote the subgraph of G2 induced by U and G[U]2 to denote the 2-hop graph of the induced subgraph G[U]. With Definition 2, we introduce the following lemma.

Lemma 1. Given a graph G = (V, E), two vertices u and v cannot be dominated by a single vertex if they are not 2-hop adjacent in G.

Proof. If u and v are not 2-hop adjacent in G, then u and v are not adjacent and cannot be dominated by each other. If there is a vertex w that can dominate both u and v, w must be adjacent to u and v simultaneously, which is inconsistent with that u and v are not 2-hop adjacent in G. Thus, u and v cannot be dominated by a single vertex.

With the definition of 2-hop graphs and Lemma 1, we have the following lemma to derive a lower bound for MDS.

Lemma 2. Given a graph G = (V,E), let G2 be the 2-hop graph of G. If S is an IS of G2 , then the cardinality of S is a lower bound of the minimum dominating set of G.

Proof. Since S is an IS in G2 , any two vertices u and v in S are not 2-hop adjacent in G. According to Lemma 1, u and v cannot be dominated by a single vertex. Thus, it needs |S| different vertices to dominate vertices in S. Note that S is a subset of V , thus the size of any dominating set to dominate all the vertices of G is not smaller than |S|. Therefore, |S| is a lower bound of the minimum dominating set of G.

We call the lower bound in Lemma 2 the IS-based Lower Bound (ISLB). Figure 1 illustrates the new lower bound.

Example 1. In Figure 1, the right subfigure b is the corresponding 2-hop graph G2 of G in the left subfigure a. The dashed lines denote the new added edges in G2 . The subset {v1, v2, v9} is an IS of G2 . According to Lemma 2, its cardinality of 3 is a lower bound of MDS of G in subfigure a. In fact, 3 is a tight lower bound for MDS of G, because {v2, v3, v7} is a minimum dominating set of G.

Further, we give the following lemma, which is a generalization of Lemma 2. It gives a lower bound of dominating sets that can dominate a given subset of vertices of G.

Lemma 3. Given a graph G = (V, E) and its G2 . Let U be a subset of V and S be an IS in G2 [U]. For any subset D ⊆ V that can dominate U in G, it holds that |D| ≥ |S| .

Proof. Since S is an IS of G2 [U], then any two vertices u and v in S are not 2-hop adjacent in G. According to Lemma 1, there is no single vertex that can dominate both u and v. Therefore, it needs |S| different vertices to dominate vertices in S. Since S ⊆ U, |S| is a lower bound of the cardinality of any subset D that can dominate U, i.e., |D| ≥ |S|.

Note that the computation of the optimal ISLB for a graph G is equivalent to solving the Maximum Independent Set (MIS) problem in its G2 , which is NP-hard [Garey and Johnson, 1979]. In the next section, we will present a sophisticated algorithm that exploits ISLB to reduce the number of branches in BnB algorithms rather than to compute a lower bound for the subproblem of each search tree node.

4 An Exact Algorithm for MDS

We present an exact algorithm for MDS, called EMOS (Exact Minimum dOminating Set), which is depicted in Algorithm 1. EMOS first calls a preprocessing procedure to compute an initial solution D0 and a fixed partial solution Df , and to reduce the input graph G to G′ . Then, the algorithm calls a BnB search procedure to search for an optimal solution in the reduced graph G′ with Df as the starting partial solution and D0 as the incumbent solution D∗ . We first describe the preprocessing procedure, then the BnB search algorithm.

4.1 The Preprocessing Procedure

The preprocessing procedure performs three tasks: compute an initial solution D0, reduce the input graph G and obtain a fixed partial solution Df .

To compute an initial solution D0 for a graph G = (V, E), we adopt the following heuristic: Let D0 be an empty set at the beginning, select a vertex v that can dominate the most number of undominated vertices, mark v and its neighbors as dominated and insert it into D0. The selection step executes iteratively till all the vertices of V have been dominated. Then, D0 is an initial solution. Using a maximum heap, the process can be done in O((|E| + |V |) · log |V |) time.

Reduction has been proven to be an effective strategy for solving subgraph problems in real-world graphs [Jiang et al., 2017; Gao et al., 2018; Zhou et al., 2021]. To reduce the input graph G, we employ the reduction rule for MDS proposed in [Alber et al., 2004]. The rule identifies vertices that must be in an optimal solution of MDS by exploiting local structures of graphs. We implement the rule in our preprocessing procedure, which partitions the set N(v) of vertex v into three different subsets N1(v), N2(v) and N3(v).

• N1(v), the set of neighbors of v that have at least one neighbor not in N[v].
• N2(v), the set of neighbors of v that are not in N1(v) but have at least one neighbor in N1(v).
• N3(v), the set of neighbors of v not in N1(v) ∪N2(v).

Algorithm 1 EMOS(G), an exact algorithm for MDS

Input: A graph G = (V, E)

Output: a minimum dominating set D∗ in G.

• 1: (D0,Df ,G′ = (V ′ ,E′ )) ←Preprocessing(G);
• 2: Let U = V ′ \NG′ [Df ];
• 3: return BnBSearch(G′ , Df , U, D0);

For a vertex v ∈ V , if N3(v) is not empty, the rule removes those vertices in N2(v) and N3(v) from G and adds a new vertex v′ to G as a neighbor of v. Alber et al. [2004] proved that the optimality of MDS is preserved and v must be in an optimal solution after the transformation. We take v as a fixed vertex and insert it into the fixed partial solution Df .

After the rule is applied to every vertex in G, we obtain a fixed partial solution Df and the reduced graph G′ . We use Df as the starting point of the following search in G′ . Time complexity of the reduction is O(|V |3 ).

4.2 The Branch-and-Bound Search Procedure

Algorithm 2 describes the BnB search procedure for MDS, BnBSearch(G, D, U, D∗ ), where D is the partial solution and U is the set of vertices that haven't been dominated by D. The procedure explores the search space to find a minimum dominating set of containing D and size smaller than the incumbent D∗ to dominate all the vertices in G.

Theoretically, every vertex outside the partial solution D could be a candidate of the final solution, resulting in a huge search space for solving MDS. To prune the search space, Algorithm 2 first calls a function ReduceBranches to identify a minimal set B of branching vertices. Let b1 > b2 > · · · > b|B| be the decreasing ordering of vertices of B w.r.t. the number of undominated neighbors of each bi. The algorithm branches only on each bi ∈ B from i = 1 to |B|. Once it branches on bi, bi is marked as branched status. When all the vertices in B have branched, they resume to unbranched status before the algorithm backtracks to the upper level of the search tree. Obviously, the smaller the branching set B, the less search space needs to be explored.

We divide the set V \ D into following four subsets, according to the branching and dominating status of vertices.

• S1: the set of unbranched and undominated vertices
• S2: the set of unbranched but dominated vertices
• S3: the set of branched but undominated vertices
• S4: the set of branched and dominated vertices

At the current search tree node, all the vertices in S1 and S2 could join in the partial solution D. The vertices in S3 cannot join in D but must be dominated by the vertices in S1 ∪ S2. The vertices in S4 can be omitted completely. Thus, C = S1 ∪ S2 is the entire candidate set of branching vertices.

To reduce the number of branches, we adopt the BnB search approach proposed in [Jiang et al., 2016]. The function ReduceBranches is designed to partition the union S1 ∪ S2 ∪S3 into B and P . Let UP ⊆ P be the set of undominated vertices in P . The partition of B and P satisfies that the cardinality of the minimum dominating set in G[P ] for dominating the subset UP is greater than or equal to |D∗ | - |D|, which

Algorithm 2 BnBSearch(G, D, U, D∗ )

Input: A graph G=(V ,E), a partial solution D, the set of undominated vertices U and the best solution D∗ found so far Output: the best solution D∗ in G

1: if U is empty then 2: return D; 3: end if 4: B ←ReduceBranches(G, D, U, D∗ ); 5: if B is empty then 6: return D∗ ; 7: end if 8: sort vertices in B as b1 > b2 >...> b|B| in decreasing ordering w.r.t. the number of undominated neighbors. 9: for i = 1 to |B| do 10: Let U ′ = U \N[bi]; 11: mark bi as branched; 12: D′ ←BnBSearch(G, D∪ {bi}, U ′ , D∗ ); 13: if |D′ | < |D∗ | then 14: D∗ ←D′ ; 15: end if 16: end for 17: mark every bi ∈ B as unbranched; 18: return D∗ ;

implies that it is impossible to derive a dominating set of containing D and size smaller than D∗ to dominate the whole G using vertices in P solely. Consequently, B = C \ P is the set of branching vertices of the current search tree node.

The function ReduceBranches is depicted in Algorithm 3, which employs the new lower bound ISLB to implement the partition. Let U = S1∪S3 be the set of undominated vertices. At the beginning, P is an empty set. The algorithm constructs the partition in two steps. At the first step (line 3-22), the algorithm tries to identify a subset P ⊆ U such that the lower bound of MDS of G[P ] is greater than or equal to |D∗ |-|D|. If such a set P cannot be identified, the whole candidate set C is returned as the branching set (line 24). In this case, the number of branches of the current search tree node has not been reduced. Otherwise, algorithm 3 conducts the second step (line 26-36) to further enlarge P by inserting more vertices in S2 into P, subject to the lower bound of dominating sets for dominating all the undominated vertices in G[P] is still not smaller than |D∗ |-|D|. Finally, Algorithm 3 returns C \ P as the branching set B.

The First Step to Identify P

The essence of the first step of Algorithm 3 is to construct a subgraph G[P] (P ⊆ U) with a MDS of size greater than or equal to |D∗ |-|D|. According to Lemma 2, the cardinality of any IS of G[P ]2 is a lower bound of MDS of G[P ]. To obtain an IS of G[P]2 as big as possible, we maintain a set Π of at most k ISs of G[P]2 during the contruction. Let u1 < u2 < · · · < u|U| be the natural ordering of vertices in U. We try to insert each ui ∈ U into P from i = |U| to 1 and construct ISs in Π. A vertex ui is allowed to join into many ISs of Π.

To obtain an IS of G[P]2 of size greater than or equal to |D∗ |-|D|, we define a score for each vertex u and nonempty IS Sj ∈ Π, denoted by δ(Sj , u), to measure the impact on the Algorithm 3 ReduceBranches(G, D, U, D∗ ), algorithm to identify a branching set B

Input: A graph G=(V ,E), a partial solution D, the set of undominated vertices U and the best solution D∗ found so far Output: A branching set B 1: Let P=∅, C=S1 ∪ S2, U=S1 ∪ S3={u1, u2, . . . , u|U|}; 2: Let Π = {S1, S2, . . . , Sk} be the set of k ISs of G[P]2 , each Si is initialized to ∅ at the beginning; 3: for i = |U| to 1 do 4: Let totalScore = 0; 5: for each nonempty IS Sj ∈ Π do 6: totalScore ← totalScore + δ(Sj , ui); 7: end for 8: if totalScore ≥ 0 then 9: P ←P ∪ {ui}; 10: for each nonempty Sj ∈ Π do 11: if δ(Sj , ui) > 0 then 12: insert ui into Sj; 13: end if 14: if δ(Sj , ui) < 0 then 15: remove |N(ui) ∩ Sj |-1 conf. vertices from Sj 16: end if 17: end for 18: if ui hasn't been inserted into any nonempty IS then 19: insert ui into the first empty IS Si; 20: end if 21: end if 22: end for 23: Let lb =max{|Sj| | Sj ∈ Π}; 24: if lb < |D∗ | - |D| then return C; 25: Let S2 = {d1, d2, . . . , d|S2|}; 26: for i = |S2| to 1 do 27: Let Π′ ←Π, P ←P ∪ {di}; 28: for each nonempty Sj ∈ Π do 29: if δ(Sj , di) < 0 then 30: remove |N(di) ∩ Sj |-1 conf. vertices from Sj 31: end if 32: end for 33: if max{|Sj | | Sj ∈ Π} < |D∗ | - |D| then 34: Π←Π′ , P ←P \ {di}; 35: end if 36: end for 37: return C \ P ;

size of Sj by the insertion of u into P .

Let N1 = NG(u) ∩ Sj be the set of neighbors of u in Sj and N2 = NG[u] ∩ NG[Sj] ∩ P ∩ C be the set of common and unbranched neighbors of u and vertices of Sj in P. If N1 is empty, Sj is still an IS of G[P] after inserting u into P. If u is undominated and N2 is empty, u can be inserted into Sj . The score δ(Sj , u) is defined in Equation 1.

If u is unbranched (u ∈ S1), it could be selected to dominate other vertices in the following search. Thus, u is used to determine the 2-hop adjacency of vertices in G[P], i.e., any two neighbors of u in P are adjacent in G[P ]2 if u is inserted into P. If N1 is not empty, the neighbors of u in Sj will become conflicting after inserting u into P. To keep Sj as an IS, |N1| - 1 neighbors of u must be removed from Sj . Thus, we define the score as 1 - |N1| because the size of Sj is decreased by |N1| - 1. Note that u is undominated thus u can join into Sj if N1 and N2 are empty, the score is defined as 1. The score is defined as 0 if N1 is empty but N2 is not empty.

If u is branched (u ∈ S3), the 2-hop adjacency between vertices in G[P] will not change after the insertion of u into P, because u will not be selected as a candidate to dominate other vertices in the following search. In this case, we only need to consider whether u can join into Sj . If N2 is empty, u can join into Sj and the size of Sj is increased by 1, the score is defined as 1; Otherwise, the score is defined as 0.

If the total score of u, defined as the sum of δ(Sj, u) for every non-empty Sj ∈ Π, is greater than or equal to 0, Algorithm 3 inserts u into P, because it is expected to bring positive impacts on the maximum cardinality of ISs in Π. It inserts u into the ISs of positive scores and removes the conflicting vertices from ISs of negative scores. If u couldn't be inserted into any nonempty IS and there exists empty ISs, u is inserted into the first empty IS. If the total score is smaller than 0, Algorithm 3 does not insert u into P at the first step.

Let lb be the maximum cardinality of ISs in Π after the first step. If lb ≥ |D∗ | - |D|, it guarantees that using vertices in P solely cannot obtain a dominating set of containing D and size smaller than D∗ to dominate G. In this case, Algorithm 3 takes the second step to insert more vertices of S2 into P to further reduce the number of branches.

The Second Step to Enlarge P

The vertices in S2 (dominated but unbranched) can join in P but cannot be inserted into ISs of Π to estimate the lower bound. Let Up be the set of undominated vertices that are inserted into P in the first step. At the second step, we compute the lower bound of dominating sets for dominating the subset Up. Since the ISs in Π only contain vertices in Up, according to Lemma 3, the cardinality of the maximum IS in Π is the lower bound of dominating sets for dominating Up. Therefore, to guarantee that a dominating set of containing D and size smaller than D∗ couldn't be derived with vertices in P solely, we only insert those vertices that satisfy that the cardinality of the maximum IS in Π is still greater than or equal to |D∗ | - |D| after the insertion.

Finally, Algorithm 3 returns the set of candidate vertices that have not been inserted into P as the branching set B, i.e., C \ P. We use Figure 1 to illustrate How Algorithm 3 identifies a minimal branching set B.

Example 2. Suppose k is 4, the partial solutionD={v4}, the size of D∗ is 4 and only v4 is branched, then we have lb=|D∗ |- |D|=3, S1={v1, v6, v7, v8, v9, v10}, S2={v2, v3, v5}, S3=∅, S4=∅ and U=S1 ∪ S3={v1, v6, . . . , v10}. At the first step, Algorithm 3 constructs P={v10, v9, v7, v6, v1} and obtains a

Π={{v10, v9, v1}, {v7, v1}, {v6, v1}, ∅}. It does not insert v8 into P, because its score is negative. The computed lower bound of MDS for G[P] is 3, which is greater than or equal to lb. At the second step, v5, v3 and v2 are inserted into P because they do not change the 2-hop adjacency of vertices in the maximum IS {v10, v9, v1}. Finally, Algorithm 3 derives a minimal branching set B = {v8}. The number of branches is reduced from 9 to 1.

According to our experiments, k is fixed to 16 in Algorithm 3. Let Γ(G) be the maximum degree of vertices in G. The time complexity of determining the 2-hop adjacency of two vertices is O(Γ(G)). The time complexity of the computation of the total score for each u is O(|C| ·Γ(G)). Thus, the total time complexity of Algorithm 3 is O(|C|2 · Γ(G)).

5 Experimental Evaluations

We implemented the new algorithm EMOS 1 in C and complied it with GNU gcc -O3. Extensive experiments were conducted to evaluate the performance of EMOS and the effectiveness of the new lower bound ISLB for pruning branches. Experiments were performed on AMD EPYC CPUs 7702 @2.0GHz under Linux with 128GB of memory.

Since there is no available exact algorithm for MDS. We compared EMOS with three state-of-the-art heuristic algorithms, FastDS [Cai et al., 2020], ScBppw [Fan et al., 2019] and FastMWDS [Wang et al., 2018], which are incomplete and cannot guarantee the optimality of solutions. The three algorithms implement local search approach and employ different heuristic strategies to escape from local minimums. The source code of the three algorithms was kindly provided by their authors and was compiled using GNU g++ -O3.

Experiments were conducted on two standard datasets UDG and T1 and a dataset of real-world graphs, which are widely used to evaluate algorithms for MDS [Jovanovic et al., 2010; Hedar and Ismail, 2010; Potluri and Singh, 2013; Wang et al., 2018; Fan et al., 2019; Cai et al., 2020].

• UDG. The set contains 120 unit disk graphs, which are generated with the topology generator described in [Potluri and Singh, 2013] and divided into 12 families, each containing 10 different graphs.
• T1. The set contains 530 random connected undirected graphs with vertices ranging from 50 to 1000 [Jovanovic et al., 2010]. The set is divided into 53 groups, each containing 10 different graphs.
• Real-world graphs. The set contains 400 real-world graphs which we select from Network Repository 2 . We use this set to evaluate the performance of our algorithm for graphs encoding from real-world applications.

5.1 The Total Performance

In the first experiment, we evaluated the total performance of EMOS and compared it with the three heuristic algorithms in terms of quality of solutions.

1 Published at https://github.com/huajiang-ynu/ijcai23-mds/

2 http://networkrepository.com/networks.php

We tested EMOS on the three datasets with a cutoff time of 5 hours for each instance. For those instances that EMOS can solve within the cutoff time, we ran the heuristic algorithms on them 10 times using random seeds 1 to 10 and a cutoff time of 1800s for each run. So, the total running time of heuristic algorithms for each instance is also 5 hours. We report the running time (time) in seconds and the optimal solution (opt) of EMOS and the best and the average of solutions of 10 runs of heuristic algorithms for each instance in Table 1-3. The average is put in brackets if it is not equal to the best.

For UDG instances, EMOS solves all of the instances in groups of 50, 100 and 250 and a few of instances in group 500. To save space, we discard group 50 and report the remaining 45 instances in Table 1. For the heuristic algorithms, FastMWDS finds the optimum at each run for every instance. FastDS and ScBppw find 40 (24) and 24 (2) optimums in terms of best (average) solutions, respectively.

For T1 instances, EMOS solves all of the instances in group 50 and 100 and most instances in group 150 and a few of instances in group 200. The results of group 150 and 200 are reported in Table 2. For the heuristic algorithms, FastMWDS can find the optimum at each run for the 44 instances. FastDS and ScBppw find 38 (31) and 36 (14) optimums in terms of best (average) solutions, respectively.

For the real-world instances, EMOS solves 203 instances out of the total 400 instances. Moreover, among the 203 solved instances, there are 162 instances for which the initial solutions derived by EMOS are the optimal solutions and EMOS can solve most of them within 1s. We exclude those easy instances and report the remaining 41 instances. Results are shown in Table 3. From the table, we can see that among the 41 instances solved by EMOS, there are 31 instances that can be solved by EMOS within 100s. However, FastDS, ScBppw and FastMWDS can only find 24 (21), 19 (12) and 31(27) optimums in terms of best (average) solutions respectively, showing a weak performance for real-world graphs.

In general, the empirical results show that EMOS is effective on the three datasets. Especially, EMOS shows a promising performance for graphs from real-world applications.

5.2 Effects of the Lower Bound and Graph Reduction

To investigate the effects of the new lower bound ISLB for pruning branches and the reduction rule for graph reduction in the preprocessing. We compared EMOS with the following two variants using the 130 instances reported in Table 1-3.

• EMOS\islb. It is EMOS but the partition of C in function ReduceBranches is disabled. It uses the whole set C as the branching set B.
• EMOS\reduction. It is EMOS but the reduction rule in the preprocessing is disabled, i.e., no vertices are removed and fixed. It uses ∅ as the initial partial solution.

Figure 2 plots the cumulative numbers of instances solved by EMOS and the two variants. Compared to EMOS, EMOS\reduction fails to solve 38 instances (24 from realworld dataset and 14 from UDG and T1) in 1800s and the performance of EMOS\islb declines dramatically, showing that the reduction rule in the preprocessing is very effective and the lower bound is crucial to the performance of EMOS.

To investigate the efficiency of the new lower bound ISLB for reducing the number of branches in EMOS, we compute the sum of the size of the branching set B, denoted by Σ|B|, and the sum of the size of the candidate set C, denoted by Σ|C|, of every search tree node for each instance in Table 13. We call the ratio of (Σ|C| - Σ|B|) to Σ|C| the pruning rate of instances by ISLB. We report the percentages of the numbers of instances with different pruning rates in Table 4.

It is easy to see that for more than 80% instances, the pruning rates are greater than or equal to 0.95, and for 93% instances, the pruning rates are greater than or equal to 0.90, showing that the new lower bound ISLB is very efficient for pruning branches and is crucial to the performance of EMOS.

6 Conclusions

MDS is extremely challenging in computation. In this paper, we propose a novel lower bound and an exact algorithm for MDS. The algorithm implements a branch-and-bound approach and employs the new lower bound to reduce search space. Empirical results show that the new lower bound is very efficient in reducing the number of branches and the new algorithm EMOS is very effective for the tested instances, especially for instances encoding from real-world applications. To the best of our knowledge, this is the first effective branchand-bound algorithm for MDS.

Acknowledgments

This work is funded by the National Natural Science Foundation of China (Grant NO. 62162066, 62162064 and 62162067), and in part supported by the project of Research and Application of Object Detection Based on Artificial Intelligence, by the project of Research on Data Driven Intelligent Logistics System Construction and Key Technologies (Grant NO. 202302AD080006), Science and Technology Department of Yunnan Province. The experiments were performed on Hefei advanced computing center.