Title: The Directed Dominating Set problem studied by cavity method: Warning propagation and population dynamics Show Chinese title

Title: 通过腔方法研究的有向支配集问题：警告传播和群体动力学

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\H{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 Erd\H{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, Erd\H{o}s-R\'enyi graph, warning propagation, survey propagation decimation. Show Chinese abstract

Abstract: 有向图的最小支配集是一个典型的难以解决的组合优化问题。 在之前的一篇论文中，我们使用腔方法研究了这个问题。 尽管我们找到了一个给定图的解，该解能够很好地估计最小支配集的大小，但我们进一步发展了一步复制对称性破缺理论，以确定无向最小支配集问题的基态能量。 无向最小支配集问题的解空间在规则随机图上表现出凝聚相变和簇相变。 我们还在无向Erdős-Rényi图上开发了零温度调查传播算法来寻找基态能量。 在本文中，我们继续发展一步复制对称性破缺理论，以找到有向最小支配集问题的基态能量。 我们发现以下结果。 (1)当连通性大于核心渗流阈值3.704时，警告传播方程无法收敛。 正边有两种类型的警告，但负边只有一种。 (2)我们确定了Erdős-Rényi随机图的基态能量和转变点。 (3)调查传播消减算法的结果良好，与信念传播消减算法相当。 关键词：有向最小支配集，复制对称性破缺，Erdős-Rényi图，警告传播，调查传播消减。