TL;DR
This paper introduces CC2FS, a novel local search algorithm for the Minimum Weight Dominating Set (MWDS) problem. By combining a new "two-level configuration checking" strategy to avoid repetitive search paths and a "frequency-based scoring function" that leverages historical vertex behavior, CC2FS significantly outperforms existing state-of-the-art algorithms in finding high-quality solutions on a wide range of MWDS benchmarks.
What Problem Does This Paper Address?
The Minimum Weight Dominating Set (MWDS) problem is a crucial generalization of the Minimum Dominating Set (MDS) problem, with applications spanning social networks, communication systems, and industrial settings. The goal is to find a subset of vertices (a dominating set) such that every vertex in the graph is either in the set or adjacent to a vertex in the set, while minimizing the total weight of the vertices in the chosen subset. While heuristic algorithms exist, their efficiency and ability to escape local optima are often limited, especially on complex and large-scale instances. This paper aims to address these limitations by developing a more effective local search algorithm that can find better solutions more reliably.
Methods
The core of the CC2FS algorithm lies in two novel components:
- Two-Level Configuration Checking (CC2): This is a refinement of an existing "configuration checking" strategy designed to prevent algorithms from revisiting similar search states. CC2 defines a vertex's "configuration" based on its two-level neighborhood (its immediate neighbors and their neighbors). When a vertex's configuration changes (due to additions or removals from the candidate solution), it signals that this vertex might be important for exploring new solution spaces. CC2 restricts additions to only those vertices whose configurations have changed, thereby guiding the search away from previously explored paths.
- Frequency-Based Scoring Function: This function assigns a score to each vertex based on its "frequency" of being uncovered by the current candidate solution. Vertices that have been uncovered more often in the past receive a higher frequency count. This dynamic information is used to prioritize vertices that are "harder to cover" or have historically been problematic. The scoring function calculates a vertex's benefit based on how many currently uncovered vertices it would cover (if added) or how many covered vertices it would uncover (if removed), weighted by their frequencies.
These two components are integrated into a local search framework that iteratively improves a candidate solution by removing vertices with high scores and adding vertices with high scores, while adhering to the CC2 strategy and using a "forbid list" (a tabu list) to prevent immediate re-removal of recently added vertices.
Datasets
The paper evaluates CC2FS on several benchmark datasets:
- T1 and T2 instances: These are generated instances from prior work [Jovanovic et al., 2010].
- Unit Disk Graphs (UDG): Standard benchmark graphs for graph problems.
- Random Generated Instances: General random graph instances.
- DIMACS and BHOSLIB benchmarks: Classical graph algorithm benchmark collections [Johnson and Trick, 1996; Xu et al., 2007].
- Real-world massive graphs: Datasets from the Network Data Repository [Rossi and Ahmed, 2015], featuring millions of vertices and tens of millions of edges.
Key Insights and Ideas
- Configuration matters beyond immediate neighbors: The CC2 strategy's insight is that a vertex's "state" is influenced not just by its direct neighbors but also by the neighbors of its neighbors. This broader view of configuration helps in more effectively detecting and avoiding cycles.
- Historical behavior predicts future utility: The frequency-based scoring function leverages the idea that a vertex's past "uncoveredness" is a good indicator of its importance for future solutions. This dynamic scoring mechanism allows the algorithm to adapt to the evolving search landscape.
- Synergy of CC2 and frequency scoring: The combination of CC2 (to guide the search direction) and frequency scoring (to prioritize vertex selection) creates a powerful local search heuristic that can escape local optima and find better solutions.
- Effectiveness on large-scale graphs: The algorithm demonstrates strong performance not only on smaller, standard benchmarks but also on massive real-world graphs, suggesting its scalability and practical utility.
Key Results
CC2FS consistently outperforms five state-of-the-art MWDS algorithms (HGA, ACO-PP-LS, ABC, EA/G-IR, R-PBIG) across a broad range of benchmarks. The paper highlights that CC2FS achieves significantly better solution quality, often finding the best known solutions for difficult instances. For example, in Table 1 and Table 2, CC2FS's "MEAN RTime" or "MEAN FTime" values are frequently lower or achieve better solution values than its competitors, especially on larger and more complex instances. The paper states that CC2FS "significantly outperforms previous algorithms and improves the best known solution quality for some difficult instances."
Limitations and Future Work
- Limitations: While CC2FS shows excellent performance, the paper notes a few instances where its solution quality is not the absolute best (e.g., v250e250 and v800e10000 on the T2 benchmark). The "extended abstract" format means detailed analysis of these exceptions is likely deferred to a full paper.
- Future Work: The paper implicitly suggests that further exploration of different neighborhood definitions for CC2 or variations of the frequency-based scoring function could yield even better results. The success on massive graphs also opens avenues for applying CC2FS to other NP-hard problems with similar structural properties.
Summary updated