Statistical Mechanics of the Minimum Dominating Set Problem

Abstract

The minimum dominating set problem has wide applications in network science and related fields. It consists of assembling a node set of global minimum size such that any node of the network is either in this set or is adjacent to at least one node of this set. Although this is a difficult optimization problem in general, we show it can be exactly solved by a generalized leaf-removal process if the network contains no core. If the network has an extensive core, we estimate the size of minimum dominating sets by a mean-field theory and implement a belief-propagation algorithm to obtain near-optimal solutions. Our algorithms also perform well on real-world network instances.

Extensively revised (final version to be published in Journal of Statistical Physics). 19 pages in total

References in corpus (28)

• Statistical mechanics of complex networks
• Universal Behavior of Load Distribution in Scale-free Networks
• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Mapping the Gnutella Network: Properties of Large-Scale Peer-to-Peer Systems and Implications for System Design
• Graph Evolution: Densification and Shrinking Diameters
• Lattice Glass Models
• Robust network community detection using balanced propagation
• Reconstruction on trees and spin glass transition
• Core percolation in random graphs: a critical phenomena analysis
• Optimizing spread dynamics on graphs by message passing
• Inducing Effect on the Percolation Transition in Complex Networks
• Minimum Dominating Sets in Scale-Free Network Ensembles
• Network Observability Transitions
• Analytic solution of a static scale-free network model
• Large deviations of cascade processes on graphs
• Distance-d covering problems in scale-free networks with degree correlations
• Minimal contagious sets in random regular graphs
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Statistical mechanics of the vertex-cover problem
• Region graph partition function expansion and approximate free energy landscapes: Theory and some numerical results
• Partition function loop series for a general graphical model: free energy corrections and message-passing equations
• Suppressing epidemics on networks by exploiting observer nodes
• The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
• Observability transitions in correlated networks
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm

Cited by in corpus (23)

• Vital nodes identification in complex networks
• Control Principles of Complex Networks
• Local structure can identify and quantify influential global spreaders in large scale social networks
• Covering Problems and Core Percolations on Hypergraphs
• Generalization of core percolation on complex networks
• Controllability and maximum matchings of complex networks
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
• Minimum Long-Loop Feedback Vertex Set and Network Dismantling
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Two faces of greedy leaf removal procedure on graphs
• Generalized minimum dominating set and application in automatic text summarization
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Observability transitions in clustered networks
• Typical Performance of Approximation Algorithms for NP-hard Problems
• Target observation of complex networks
• K-core attack, equilibrium K-core, and kinetically constrained spin system
• Two-distance minimal dominating set problem studied by statistical mechanics and simulated annealing
• Optimal Disruption of Complex Networks
• A local algorithm and its percolation analysis of bipartite $z$-matching problem
• Statistical Mechanics of the L-Distance Minimal Dominating Set problem
• The Directed Dominating Set problem studied by cavity method: Warning propagation and population dynamics
• Zero forcing number of graphs with a power law degree distribution