Planted vertex cover problem on regular random graphs and nonmonotonic temperature-dependence in the supercooled region
We introduce a planted vertex cover problem on regular random graphs and study it by the cavity method of statistical mechanics. Different from conventional Ising models, the equilibrium ferromagnetic phase transition of this binary-spin two-body interaction system is discontinuous, as the paramagnetic phase is separated from the ferromagnetic phase by an extensive free energy barrier. The free energy landscape can be distinguished into three different types depending on the two degree parameters of the planted graph. The critical inverse temperatures at which the paramagnetic phase becomes locally unstable towards the ferromagnetic phase ($\beta_{\textrm{pf}}$) and towards spin glass phases ($\beta_{\textrm{pg}}$) satisfy $\beta_{\textrm{pf}} > \beta_{\textrm{pg}}$, $\beta_{\textrm{pf}} < \beta_{\textrm{pg}}$ and $\beta_{\textrm{pf}} = \beta_{\textrm{pg}}$, respectively, in these three landscapes. A locally stable anti-ferromagnetic phase emerges in the free energy landscape if $\beta_{\textrm{pf}} < \beta_{\textrm{pg}}$. When exploring the free energy landscape by stochastic local search dynamics, we find that in agreement with our theoretical prediction, the first-passage time from the paramagnetic phase to the ferromagnetic phase is nonmonotonic with the inverse temperature. The potential relevance of the planted vertex cover model to supercooled glass-forming liquids is briefly discussed.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fixed-Parameter Tractability of the (1+1) Evolutionary Algorithm on Random Planted Vertex Covers
We present the first parameterized analysis of a standard (1+1) Evolutionary Algorithm on a distribution of vertex cover problems. We show that if the planted cover is at most logarithmic, restarting the (1+1) EA every $…
Found Graph Data and Planted Vertex Covers
A typical way in which network data is recorded is to measure all the interactions among a specified set of core nodes; this produces a graph containing this core together with a potentially larger set of fringe nodes th…
Preferential Attachment Graphs with Planted Communities
A variation of the preferential attachment random graph model of Barab\'asi and Albert is defined that incorporates planted communities. The graph is built progressively, with new vertices attaching to the existing ones …
Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
We consider two problems that arise in machine learning applications: the problem of recovering a planted sparse vector in a random linear subspace and the problem of decomposing a random low-rank overcomplete 3-tensor. …
Tensor DecompositionSQ Lower Bounds for Random Sparse Planted Vector Problem
Consider the setting where a $\rho$-sparse Rademacher vector is planted in a random $d$-dimensional subspace of $R^n$. A classical question is how to recover this planted vector given a random basis in this subspace. A r…