TL;DR
This paper introduces FastMWDS, a novel local search algorithm designed to efficiently find near-optimal solutions for the Minimum Weight Dominating Set (MWDS) problem on massive graphs. By employing a fast graph reduction technique and a new three-valued configuration checking strategy, FastMWDS significantly outperforms existing state-of-the-art algorithms in both solution quality and runtime on large, real-world datasets.
What Problem Does This Paper Address?
The Minimum Weight Dominating Set (MWDS) problem is a crucial optimization challenge with applications in areas like data retrieval and network design. It involves finding a subset of vertices in a weighted graph such that every vertex is either in the subset or adjacent to a vertex in the subset, and the total weight of the chosen vertices is minimized. While MWDS is NP-hard, meaning finding the absolute optimal solution is computationally intractable for large instances, existing heuristic algorithms struggle to provide good solutions within a reasonable time frame, especially for "massive graphs" (graphs with a very large number of vertices and edges). This paper aims to bridge this gap by developing an algorithm that can effectively tackle these large-scale instances.
Methods
The core of FastMWDS lies in two key innovations:
- Fast Construction Phase (ConstructDS): Before the main local search begins, ConstructDS rapidly reduces the size of the input graph. It uses four novel "reduction rules" (Weighted-Degree-0, Weighted-Degree-1 Rule1, Weighted-Degree-1 Rule2, and Weighted-Degree-2) that leverage vertex weights and neighborhood structures to fix certain vertices in the dominating set or eliminate redundant vertices. This pre-processing step significantly simplifies the graph for the subsequent local search.
- Three-Valued Two-Level Configuration Checking (CC2V3): Local search algorithms often get stuck in cycles or explore unproductive search spaces. To combat this, the paper introduces CC2V3, an enhancement of the existing two-level configuration checking (CC2) strategy. Unlike CC2, which uses a binary (changed/unchanged) state for vertices, CC2V3 employs three states: "forbidden to add," "clearly dominated," and "uncertain dominated state." This finer-grained state representation allows the algorithm to make more informed decisions about which vertices to consider adding or removing, thereby improving exploration and avoiding premature convergence.
The algorithm then proceeds with a local search phase that iteratively refines the candidate solution, incorporating a variant of the "best from multiple selection" (BMS) heuristic to introduce diversification.
Datasets
The experiments were conducted on 187 massive real-world graphs from the Network Data Repository [Rossi and Ahmed, 2015]. The paper notes that a few bipartite graphs were excluded. For generating vertex weights, a simple scheme was used: for the i-th vertex v<sub>i</sub>, w(v<sub>i</sub>) = (i mod 200) + 1.
Key Insights and Ideas
- Graph Reduction is Crucial for Scale: The paper demonstrates that aggressive, yet effective, graph reduction techniques are essential for making MWDS algorithms practical on massive graphs. The proposed reduction rules are shown to significantly shrink the problem size.
- Finer-Grained State Tracking Improves Local Search: The CC2V3 strategy's three-valued state representation is a key differentiator. By distinguishing between vertices that are "clearly dominated" and those with an "uncertain dominated state," the algorithm can better prioritize exploration and avoid getting trapped in local optima.
- Balancing Greediness and Exploration: The BMS heuristic, with its probabilistic parameter
k, allows FastMWDS to balance greedy moves (focusing on high-scoring vertices) with random exploration, which is vital for navigating complex search spaces.
Key Results
FastMWDS consistently outperformed existing state-of-the-art algorithms, including CC2FS (a previous best for MWDS) and three Weighted Partial Maximum Satisfiability (WPMS) solvers (MaxHS, OpenWBO, WPM3-2015-in), on the tested massive graphs.
- Runtime: FastMWDS achieved significantly faster initialization times compared to CC2FS, with some instances being 1000x faster.
- Solution Quality: For many instances, FastMWDS found better solutions (lower weights) than its competitors. Notably, CC2FS and the WPMS solvers failed to find solutions for a considerable number of graphs within the 1000-second time limit, while FastMWDS successfully found solutions for all tested graphs.
- Construction Effectiveness: The ConstructDS procedure alone managed to dominate over 59% of vertices on average across massive graphs, and in 41 instances, it dominated more than 50% of vertices.
Limitations and Future Work
- Limitations: While FastMWDS performs exceptionally well on massive graphs, the paper acknowledges that for some specific instances (e.g.,
inf-germany_osmandrec-epinions), it did not find strictly better solutions than its competitors. The paper also notes that for a few graphs, CC2FS failed to complete its initialization within the time limit, making direct comparison difficult for those specific cases. - Future Work: The authors suggest further improving FastMWDS by exploring additional ideas and applying it to an even wider range of massive graph instances.
Summary updated