The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
arXiv:1505.03537 · doi:10.1007/978-3-319-19647-3_8
Abstract
A minimum dominating set for a digraph (directed graph) is a smallest set of vertices such that each vertex either belongs to this set or has at least one parent vertex in this set. We solve this hard combinatorial optimization problem approximately by a local algorithm of generalized leaf removal and by a message-passing algorithm of belief propagation. These algorithms can construct near-optimal dominating sets or even exact minimum dominating sets for random digraphs and also for real-world digraph instances. We further develop a core percolation theory and a replica-symmetric spin glass theory for this problem. Our algorithmic and theoretical results may facilitate applications of dominating sets to various network problems involving directed interactions.
11 pages, 3 figures in EPS format
References in corpus (8)
- Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design
- Graph Evolution: Densification and Shrinking Diameters
- Core percolation on complex networks
- Network Observability Transitions
- Statistical Mechanics of the Minimum Dominating Set Problem
- Statistical Mechanics of the Hyper Vertex Cover Problem
- Suppressing epidemics on networks by exploiting observer nodes
- Statistical physics of hard combinatorial optimization: The vertex cover problem
Cited by in corpus (10)
- Statistical Mechanics of the Minimum Dominating Set Problem
- Controllability and maximum matchings of complex networks
- Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
- Two faces of greedy leaf removal procedure on graphs
- Group polarization, influence, and domination in online interaction networks: A case study of the 2022 Brazilian elections
- Generalized minimum dominating set and application in automatic text summarization
- A local algorithm and its percolation analysis of bipartite -matching problem
- Optimal Disruption of Complex Networks
- Parametrised Algorithms for Directed Modular Width
- The Directed Dominating Set problem studied by cavity method: Warning propagation and population dynamics