Search

The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT) phase when the clause density a exceeds a critical value αs ≈ 4.267. Rigorously proving the unsatisfiability of a given large 3-SAT instance is, however, extremely difficult. In this paper we apply the mean-field theory of statistical physics to the unsatisfiability problem, and show that a reduction to 3-XORSAT, which permits the construction of a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses), is possible when the clause density α > 19. We then construct Feige-Kim-Ofek witnesses for single 3-SAT instances through a simple random sampling algorithm and a focused local search algorithm. The random sampling algorithm works only when a scales at least linearly with the variable number N, but the focused local search algorithm works for clause density a > cNb with b≈0.59 and prefactor c ≈ 8. The exponent b can be further decreased by enlarging the single parameter 5 of the focused local search algorithm. [ABSTRACT FROM AUTHOR]

Network dismantling aims at breaking a network into disconnected components and attacking vertices that intersect with many loops has proven to be a most efficient strategy. Yet existing loop-focusing methods do not distinguish the short loops within densely connected local clusters (e.g., cliques) from the long loops connecting different clusters, leading to lowered performance of these algorithms. Here we propose a new solution framework for network dismantling based on a two-scale bipartite factor-graph representation, in which long loops are maintained while local dense clusters are simplistically represented as individual factor nodes. A mean-field spin-glass theory is developed for the corresponding long-loop feedback vertex set problem. The framework allows for the advancement of various existing dismantling algorithms; we developed the new version of two benchmark algorithms BPD (which uses the message-passing equations of the spin-glass theory as the solver) and CoreHD (which is fastest among well-performing algorithms). New solvers outperform current state-of-the-art algorithms by a considerable margin on networks of various sorts. Further improvement in dismantling performance is achievable by opting flexibly the choice of local clusters.

The planted p-spin interaction model is a paradigm of random-graph systems possessing both a ferromagnetic phase and a disordered phase with the latter splitting into many spin-glass states at low temperatures. Conventional simulated annealing dynamics is easily blocked by these low-energy spin-glass states. Here we demonstrate that actually this planted system is exponentially dominated by a microcanonical polarized phase at intermediate energy densities. There is a discontinuous microcanonical spontaneous symmetry breaking transition from the paramagnetic phase to the microcanonical polarized phase. This transition can serve as a mechanism to avoid all the spin-glass traps, and it is accelerated by the restart strategy of microcanonical random walk. We also propose an unsupervised learning problem on microcanonically sampled configurations for inferring the planted ground state.

We propose a method for solving statistical mechanics problems defined on sparse graphs. It extracts a small feedback vertex set (FVS) from the sparse graph, converting the sparse system to a much smaller system with many-body and dense interactions with an effective energy on every configuration of the FVS, then learns a variational distribution parametrized using neural networks to approximate the original Boltzmann distribution. The method is able to estimate free energy, compute observables, and generate unbiased samples via direct sampling without autocorrelation. Extensive experiments show that our approach is more accurate than existing approaches for sparse spin glasses. On random graphs and real-world networks, our approach significantly outperforms the standard methods for sparse systems, such as the belief-propagation algorithm; on structured sparse systems, such as two-dimensional lattices our approach is significantly faster and more accurate than recently proposed variational autoregressive networks using convolution neural networks.

Random K-satisfiability (K-SAT) is a paradigmatic model system for studying phase transitions in constraint satisfaction problems and for developing empirical algorithms. The statistical properties of the random K-SAT solution space have been extensively investigated, but most earlier efforts focused on solutions that are typical. Here we consider maximally flexible solutions which satisfy all the constraints only using the minimum number of variables. Such atypical solutions have high internal entropy because they contain a maximum number of null variables which are completely free to choose their states. Each maximally flexible solution indicates a dense region of the solution space. We estimate the maximum fraction of null variables by the replica-symmetric cavity method, and implement message-passing algorithms to construct maximally flexible solutions for single K-SAT instances.

We introduce two generalizations of core percolation in graphs to hypergraphs, related to the minimum hyperedge cover problem and the minimum vertex cover problem on hypergraphs, respectively. We offer analytical solutions of these two core percolations for uncorrelated random hypergraphs whose vertex degree and hyperedge cardinality distributions are arbitrary but have nondiverging moments. We find that for several real-world hypergraphs their two cores tend to be much smaller than those of their null models, suggesting that covering problems in those real-world hypergraphs can actually be solved in polynomial time.

Spontaneous symmetry breaking (SSB) in statistical physics is a macroscopic collective phenomenon. For the paradigmatic Q-state Potts model it means a transition from the disordered color-symmetric phase to an ordered phase in which one color dominates. Existing mean field theories imply that SSB in the microcanonical statistical ensemble (with energy being the control parameter) should be a continuous process. Here we study microcanonical SSB on the random-graph Potts model and discover that the entropy is a kinked function of energy. This kink leads to a discontinuous phase transition at certain energy density value, characterized by a jump in the density of the dominant color and a jump in the microcanonical temperature. This discontinuous SSB in random graphs is confirmed by microcanonical Monte Carlo simulations, and it is also observed in bond-diluted finite-size lattice systems.

Previously, the controllability problem of a linear time-invariant dynamical system was mapped to the maximum matching (MM) problem on the bipartite representation of the underlying directed graph, and the sizes of MMs on random bipartite graphs were calculated analytically with the cavity method at zero temperature limit. Here we present an alternative theory to estimate MM sizes based on the core percolation theory and the perfect matching of cores. Our theory is much more simplified and easily interpreted, and can estimate MM sizes on random graphs with or without symmetry between out- and in-degree distributions. Our result helps to illuminate the fundamental connection between the controllability problem and the underlying structure of complex systems.

Lower temperature leads to a higher probability of visiting low-energy states. This intuitive belief underlies most physics-inspired strategies for addressing hard optimization problems. For instance, the popular simulated annealing (SA) dynamics is expected to approach a ground state if the temperature is lowered appropriately. Here, we demonstrate that this belief is not always justified. Specifically, we employ the cavity method to analyze the minimum strong defensive alliance problem and discover a bifurcation in the solution space, induced by an inflection point in the entropy-energy profile. While easily accessible configurations are associated with the lower-free-energy branch, the low-energy configurations are associated with the higher-free-energy branch within the same temperature range. There is a discontinuous phase transition between the high-energy configurations and the ground states, which generally cannot be followed by SA. We introduce an energy-clamping strategy to obtain superior solutions by following the higher-free-energy branch, overcoming the limitations of SA.

A feedback vertex set (FVS) of an undirected graph contains vertices from every cycle of this graph. Constructing a FVS of sufficiently small cardinality is very difficult in the worst cases, but for random graphs this problem can be efficiently solved by converting it into an appropriate spin-glass model [H.-J. Zhou, Eur. Phys. J. B 86, 455 (2013)EPJBFY1434-602810.1140/epjb/e2013-40690-1]. In the present work we study the spin-glass phase transitions and the minimum energy density of the random FVS problem by the first-step replica-symmetry-breaking (1RSB) mean-field theory. For both regular random graphs and Erdös-Rényi graphs, we determine the inverse temperature β_{l} at which the replica-symmetric mean-field theory loses its local stability, the inverse temperature β_{d} of the dynamical (clustering) phase transition, and the inverse temperature β_{s} of the static (condensation) phase transition. These critical inverse temperatures all change with the mean vertex degree in a nonmonotonic way, and β_{d} is distinct from β_{s} for regular random graphs of vertex degrees K>60, while β_{d} are identical to β_{s} for Erdös-Rényi graphs at least up to mean vertex degree c=512. We then derive the zero-temperature limit of the 1RSB theory and use it to compute the minimum FVS cardinality.

For a network formed by nodes and undirected links between pairs of nodes, the network optimal attack problem aims at deleting a minimum number of target nodes to break the network down into many small components. This problem is intrinsically related to the feedback vertex set problem that was successfully tackled by spin-glass theory and an associated belief propagation-guided decimation (BPD) algorithm [Zhou, Eur. Phys. J. B 86, 455 (2013)EPJBFY1434-602810.1140/epjb/e2013-40690-1]. In the present work we apply the BPD algorithm (which has approximately linear time complexity) to the network optimal attack problem and demonstrate that it has much better performance than a recently proposed collective information algorithm [Morone and Makse, Nature 524, 65 (2015)NATUAS0028-083610.1038/nature14604] for different types of random networks and real-world network instances. The BPD-guided attack scheme often induces an abrupt collapse of the whole network, which may make it very difficult to defend.