Exactly Solving Minimum Dominating Set and Its Generalization

Ziliang Xiong, Mingyu XiaoIJCAI 2024

Abstract

The Minimum Dominating Set Problem (MDSP) is a fundamental NP-hard challenge in graph theory with critical applications in social network analysis, facility location, and wireless sensor network design. This paper introduces two high-performance exact algorithms, BIBCO and BIBLP, which leverage a generalized problem framework (EMDSP) and novel reduction rules. By combining sophisticated combinatorial and LP-based lower bounds, the proposed methods achieve a 1,000x speedup over the previous state-of-the-art, solving complex instances in seconds that previously required hours.

Introduction

Finding the smallest set of vertices that dominates a graph—ensuring every vertex is either in the set or adjacent to a member—is a classic problem with significant real-world utility. While approximation algorithms are common due to the problem's NP-hard nature, many applications require exact optimal solutions. However, exact solvers typically hit a "computational wall" as graph size or density increases. This work pushes this boundary further by making the Branch-and-Bound (B&B) framework significantly more efficient through improved reduction rules and tighter lower bounds.

Methodology

The authors generalize the standard MDSP into the Extended Minimum Dominating Set Problem (EMDSP). This framework allows vertices to be categorized as selected, excluded, or ignored, providing a more flexible structure for the recursive steps of a B&B algorithm.

Reduction Rules and Lower Bounds

A core contribution is a set of three powerful reduction rules: Single Dominator, Subset Coverage, and Ignorable Vertices. These rules prune the search space by identifying vertices that must be included or can be safely excluded based on neighborhood properties.

Algorithm for the proposed reduction rules in the EMDSP framework.

To further optimize the search, two B&B variants were developed to handle different graph characteristics:

  • BIBCO (Combinatorial): Utilizes fast combinatorial lower bounds (Disjoint Dominators and Maximum Coverage Size). It is computationally inexpensive per node, making it suitable for very dense graphs.
  • BIBLP (LP-Relaxation): Employs Linear Programming relaxations to obtain tighter lower bounds. Although solving an LP at each node is more costly, the resulting search tree is significantly smaller, leading to superior performance on sparse and medium-density graphs.

Experimental Results

The algorithms were benchmarked against diverse datasets, including Unit Disk Graphs (UDG), real-world networks from the Network Repository, and dense random graphs.

Performance comparison showing the number of solved instances versus running time for various algorithms.

The results demonstrate a massive performance leap. As shown in the performance analysis, the new algorithms provide a staggering speedup over the previous state-of-the-art (EMOS). In many cases where EMOS solved 294 instances within a 5-hour limit, the new algorithms solved over 300 instances in less than one second. BIBLP emerged as the dominant approach for most graph types, while BIBCO maintained an edge in extremely high-density scenarios (density ~0.9) where LP relaxations are less effective.

Conclusion

This work significantly advances the state-of-the-art in exact MDSP solving. The combination of powerful reduction rules and tight lower bounds allows for the resolution of previously intractable instances. Future research will explore hybrid approaches that dynamically select the most appropriate lower bound based on local graph properties during the search process.

Summary updated

BibTeX
@inproceedings{xiong2024exactly,
  author = {Ziliang Xiong and Mingyu Xiao},
  title = {{Exactly Solving Minimum Dominating Set and Its Generalization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure