TL;DR
This paper introduces EMOS, a novel exact algorithm for the Minimum Dominating Set (MDS) problem, which is notoriously difficult due to its NP-hard nature. EMOS leverages a new "2-hop graph" based lower bound and a sophisticated branch-and-bound strategy to significantly prune the search space, outperforming existing heuristic methods on various benchmark and real-world datasets.
What Problem Does This Paper Address?
The Minimum Dominating Set (MDS) problem is a fundamental problem in graph theory with wide-ranging applications, from network routing and social network analysis to multi-document summarization. The goal is to find the smallest set of vertices in a graph such that every vertex in the graph is either in this set or adjacent to a vertex in this set. Despite its importance, solving MDS exactly is computationally challenging because it's an NP-hard problem. While theoretical research has focused on approximation ratios and worst-case time complexities, practical exact algorithms are scarce. Existing approaches often rely on heuristics that don't guarantee optimality. This paper aims to bridge this gap by developing an effective exact algorithm that can find the optimal solution for MDS instances that are intractable for current heuristic methods.
Methods
The core of the proposed solution is an exact algorithm called EMOS (Exact Minimum Dominating Set), which employs a branch-and-bound (BnB) framework. EMOS introduces two key innovations:
- A Novel Lower Bound (ISLB): The algorithm defines a "2-hop graph" where two vertices are connected if they are adjacent or share a common neighbor in the original graph. A crucial insight is that an independent set in this 2-hop graph provides a lower bound for the size of the MDS in the original graph. This is because vertices that are not 2-hop adjacent cannot be dominated by a single vertex. Finding the maximum independent set in the 2-hop graph is equivalent to finding a lower bound for MDS.
- Efficient Branch-and-Bound Search: EMOS incorporates a preprocessing step that reduces the graph and establishes an initial solution and a fixed partial solution. The BnB search procedure then uses the novel lower bound within a
ReduceBranchesfunction to intelligently select branching vertices. This function aims to identify a minimal set of vertices to branch on, significantly pruning the search tree. The algorithm also uses a reduction rule from prior work to simplify the graph before the main search.
Datasets
The paper evaluates EMOS on three types of datasets:
- UDG (Unit Disk Graphs): A set of 120 graphs generated with a specific topology generator, divided into 12 families.
- T1 (Random Connected Undirected Graphs): A set of 530 graphs with varying numbers of vertices and edges, commonly used in MDS research.
- Real-world Graphs: A collection of 400 graphs sourced from the Network Repository, representing diverse real-world applications.
The authors compare EMOS against three state-of-the-art heuristic algorithms: FastDS, ScBppw, and FastMWDS.
Key Insights and Ideas
- The Power of 2-Hop Adjacency: The concept of 2-hop adjacency proves to be a surprisingly effective tool for bounding the MDS problem. The insight that non-2-hop adjacent vertices require distinct dominators is fundamental to the new lower bound.
- ISLB as a Pruning Engine: The IS-based Lower Bound (ISLB) derived from the 2-hop graph is shown to be highly effective in reducing the search space. The paper demonstrates that this lower bound leads to significant pruning rates (often >90%), making the exact algorithm practical.
- Synergy of Reduction and BnB: The combination of an initial graph reduction step and a sophisticated branch-and-bound search, guided by the new lower bound, is critical to EMOS's performance. The preprocessing effectively simplifies the problem before the more computationally intensive search begins.
- Exact vs. Heuristic Trade-offs: While heuristics are faster for large instances, they don't guarantee optimality. EMOS demonstrates that for many instances, an exact approach can be feasible and yield superior results, especially for real-world graphs where finding optimal solutions is highly desirable.
Key Results
- Optimal Solutions: EMOS successfully finds optimal solutions for a significant number of instances across all datasets, including many that heuristic algorithms could not solve optimally within the given time limits.
- Performance on UDG: EMOS solves all instances in groups of 50, 100, and 250, and some in group 500. It outperforms heuristic algorithms in terms of optimality, with FastMWDS being the only heuristic to consistently find optimal solutions.
- Performance on T1: EMOS solves all instances in groups 50 and 100, and most in groups 150 and 200. Again, EMOS finds optimal solutions where heuristics sometimes struggle.
- Real-world Graphs: EMOS solves 203 out of 400 real-world instances. Notably, for many of these, EMOS finds the optimal solution very quickly, often within 1 second. The heuristic algorithms show weaker performance on these instances.
- Lower Bound Effectiveness: Experiments show that the ISLB is crucial for EMOS's performance. Variants of EMOS without the ISLB or without graph reduction perform significantly worse, highlighting the importance of both components. Pruning rates achieved by the ISLB are consistently high (over 80% of instances with >0.95 pruning rate).
Limitations and Future Work
- Computational Complexity: While EMOS is an effective exact algorithm, the MDS problem remains NP-hard. For extremely large or dense graphs, EMOS may still face computational limitations. The paper notes that the time complexity of the
ReduceBranchesfunction is O(|C|² · Γ(G)), where |C| is the candidate set size and Γ(G) is the maximum degree. - Scalability: The paper focuses on demonstrating the effectiveness of the exact algorithm and its components. Further research could explore optimizations for even larger-scale instances or investigate hybrid approaches that combine EMOS with heuristics for very large graphs.
- Further Lower Bound Refinements: While the 2-hop graph lower bound is effective, there might be potential for developing even tighter lower bounds or combining it with other bounding techniques to further enhance pruning.
Summary updated