The Directed Dominating Set problem studied by cavity method: Warning propagation and population dynamics

Abstract

The minimal dominating set for a digraph(directed graph)is a prototypical hard combinatorial optimization problem. In a previous paper, we studied this problem using the cavity method. Although we found a solution for a given graph that gives very good estimate of the minimal dominating size, we further developed the one step replica symmetry breaking theory to determine the ground state energy of the undirected minimal dominating set problem. The solution space for the undirected minimal dominating set problem exhibits both condensation transition and cluster transition on regular random graphs. We also developed the zero temperature survey propagation algorithm on undirected Erdős-Rényi graphs to find the ground state energy. In this paper we continue to develop the one step replica symmetry breaking theory to find the ground state energy for the directed minimal dominating set problem. We find the following. (1)The warning propagation equation can not converge when the connectivity is greater than the core percolation threshold value of 3.704. Positive edges have two types warning, but the negative edges have one. (2)We determine the ground state energy and the transition point of the Erdős-Rényi random graph. (3)The survey propagation decimation algorithm has good results comparable with the belief propagation decimation algorithm. Keywords: directed minimal dominating set , replica symmetry breaking, Erdős-Rényi graph, warning propagation, survey propagation decimation.

arXiv comment22pages,2figures

References in corpus (12)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The Entropy of the K-Satisfiability Problem
• Network Observability Transitions
• Statistical Mechanics of the Minimum Dominating Set 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
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Theoretical analysis of optimization problems - Some properties of random k-SAT and k-XORSAT