Directed dominating set problem studied by cavity method: warning propagation and population dynamics

DOI10.1088/0253-6102/70/6/785MaRDI QIDQ3387676zbMATH OpenOpenAlexFDO

Authors Yusupjan Habibulla

Publication date 13 January 2021

Published in Communications in Theoretical Physics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.06974

zbMATH Keywords

directed minimal dominating setErdős-Rényi graphreplica symmetry breakingsurvey propagation decimationwarning propagation

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Symmetry breaking in quantum theory (81R40) Social networks; opinion dynamics (91D30) Population dynamics (general) (92D25)

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 ErdH{o}s-R'enyi 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 ErdH{o}s-R'enyi 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, ErdH{o}s-R'enyi graph, warning propagation, survey propagation decimation.

Recommendations

• Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics
• The directed dominating set problem: generalized leaf removal and belief propagation
• Statistical mechanics of the directed 2-distance minimal dominating set problem
• Statistical mechanics of the minimum dominating set problem
• Dominating sets of random 2-in 2-out directed graphs

Cites work

• Dominating Set and Converse Dominating Set of a Directed Graph
• Dominating sets in directed graphs
• Entropy of theK-Satisfiability Problem
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Information, Physics, and Computation
• Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics
• Observability of complex systems
• Region graph partition function expansion and approximate free energy landscapes: theory and some numerical results
• Spin Glass approach to the feedback vertex set problem
• Statistical mechanics of the minimum dominating set problem
• Statistical mechanics of the vertex-cover problem
• The directed dominating set problem: generalized leaf removal and belief propagation
• Two solutions to diluted p-spin models and XORSAT problems

Cited in

(3)

• Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics
• Statistical mechanics of the directed 2-distance minimal dominating set problem
• The directed dominating set problem: generalized leaf removal and belief propagation

This page was built for publication: Directed dominating set problem studied by cavity method: warning propagation and population dynamics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3387676)