Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics. (30th October 2017)

• Record Type: Journal Article
• Authors: Habibulla, Yusupjan
• Is Part Of: Journal of statistical mechanics. (2017:Oct.)
• Publication Date: 2017-10-30
• Subjects: 7 -- 11; Statistical mechanics -- Periodicals; Mechanics -- Statistical methods -- Periodicals; 530.1305
• DOI: 10.1088/1742-5468/aa8c1e
• Languages: English
• ISSNs: 1742-5468

Abstract

Abstract: The minimal dominating set (MDS) problem is a prototypical hard combinatorial optimization problem. We recently studied this problem using the cavity method. Although we obtained a solution for a given graph that gives a very good estimation of the minimal dominating size, we do not know whether there is a ground state solution or how many solutions exist in the ground state. We have therefore continued to develop a one-step replica symmetry breaking theory to investigate the ground state energy of the MDS problem. First, we find that the solution space for the MDS problem exhibits both condensation transition and cluster transition on regular random graphs, and prove this using a simulated annealing dynamical process. Second, we develop a zero-temperature survey propagation algorithm on Erdős–Rényi random graphs to estimate the ground state energy, and obtain a survey propagation decimation algorithm that achieves results as good as the belief propagation decimation algorithm.