1,721,034 research outputs found
Dynamics of heuristic optimization algorithms on random graphs
No full textIn this paper, the dynamics of heuristic algorithms for constructing
small vertex covers (or independent sets) of finite-connectivity
random graphs is analysed. In every algorithmic step, a vertex is
chosen with respect to its vertex degree. This vertex, and some
environment of it, is covered and removed from the graph. This graph
reduction process can be described as a Markovian dynamics in the
space of random graphs of arbitrary degree distribution. We discuss
some solvable cases, including algorithms already analysed using
different techniques, and develop approximation schemes for more
complicated cases. The approximations are corroborated by numerical
simulations
Computational complexity arising from degree correlations in networks
No full textWe apply a Bethe-Peierls approach to statistical-mechanics models defined on random networks of arbitrary degree distribution and arbitrary correlations between the degrees of neighboring vertices. Using the nondeterministic polynomial time hard optimization problem of finding minimal vertex covers on these graphs, we show that such correlations may lead to a qualitatively different solution structure as compared to uncorrelated networks. This results in a higher complexity of the network in a computational sense: Simple heuristic algorithms fail to find a minimal vertex cover in the highly correlated case, whereas uncorrelated networks seem to be simple from the point of view of combinatorial optimization
Approximation schemes for the dynamics of diluted spin models: the Ising ferromagnet on a Bethe lattice
No full textWe discuss analytical approximation schemes for the dynamics of diluted spin models. The original dynamics of the complete set of degrees of freedom is replaced by a hierarchy of equations including an increasing number of global observables, which can be closed approximately at different levels of the hierarchy. We illustrate this method on the simple example of the Ising ferromagnet on a Bethe lattice, investigating the first three possible closures, which are all exact in the long time limit, and which yield more and more accurate predictions for the finite-time behaviour. We also investigate the critical region around the phase transition, and the behaviour of two-time correlation functions. We finally underline the close relationship between this approach and the dynamical replica theory under the assumption of replica symmetry
Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
No full textWe analytically describe the typical solution time needed by a backtracking algorithm to solve the vertex-cover problem on finite-connectivity random graphs. We find two different transitions: The first one is algorithm dependent and marks the dynamical transition from linear to exponential solution times. The second one gives the maximum computational complexity, and is found exactly at the threshold where the system undergoes an algorithm-independent phase transition in its solvability. Analytical results are corroborated by numerical simulations
Statistical mechanics of the vertex-cover problem
No full textWe review recent progress in the study of the vertex-cover problem (VC). The VC belongs to the class of NP-complete graph theoretical problems, which plays a central role in theoretical computer science. On ensembles of random graphs, VC exhibits a coverable-uncoverable phase transition. Very close to this transition, depending on the solution algorithm, easy-hard transitions in the typical running time of the algorithms occur. We explain a statistical mechanics approach, which works by mapping the VC to a hard-core lattice gas, and then applying techniques such as the replica trick or the cavity approach. Using these methods, the phase diagram of the VC could be obtained exactly for connectivities c e, the solution of the VC exhibits full replica symmetry breaking. The statistical mechanics approach can also be used to study analytically the typical running time of simple complete and incomplete algorithms for the VC. Finally, we describe recent results for the VC when studied on other ensembles of finite- and infinite-dimensional graphs
A hard-sphere model on generalized Bethe lattices: dynamics
No full textWe analyse the dynamics of a hard-sphere lattice gas on generalized Bethe lattices using a projective approximation scheme ( PAS). The latter consists in mapping the system's dynamics to a finite set of global observables; closure of the resulting equations is obtained by approximating the true non-equilibrium state by a pseudo-equilibrium based only on the value of the observables under consideration. We study the liquid - crystal as well as the liquid - spin-glass transitions; special attention is given to the prediction of equilibration times and their divergence close to the phase transitions. Analytical results are corroborated by Monte Carlo simulations
Number of guards needed by a museum: A phase transition in vertex covering of random graphs
No full textIn this Letter we study the NP-complete vertex cover problem on finite connectivity random graphs. When the allowed size of the cover set is decreased, a discontinuous transition in solvability and typical-case complexity occurs. This transition is characterized by means of exact numerical simulations as well as by analytical replica calculations. The replica symmetric phase diagram is in excellent agreement with numerical findings up to average connectivity e, where replica symmetry becomes locally unstable
Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picture
No full textThe minimal vertex-cover (or maximal independent-set) problem is studied on random graphs of finite connectivity. Analytical results are obtained by a mapping to a lattice gas of hard spheres of (chemical) radius 1, and they are found to be in excellent agreement with numerical simulations. We give a detailed description of the replica-symmetric phase, including the size and entropy of the minimal vertex covers, and the structure of the unfrozen component which is found to percolate at a connectivity c similar or equal to 1.43. The replica-symmetric solution breaks down at c = e similar or equal to 2.72. We give a simple one-step replica-symmetry-broken solution, and discuss the problems in the interpretation and generalization of this solution
A hard-sphere model on generalized Bethe lattices: statics
No full textWe analyse the phase diagram of a model of hard spheres of chemical radius one, which is defined over a generalized Bethe lattice containing short loops. We find a liquid, two different crystalline, a glassy and an unusual crystalline glassy phase. Special attention is also paid to the close-packing limit in the glassy phase. All analytical results are cross-checked by numerical Monte Carlo simulations
Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
No full textStochastic local search algorithms are frequently used to numerically solve hard combinatorial optimization or decision problems. We give numerical and approximate analytical descriptions of the dynamics of such algorithms applied to random satisfiability problems. We find two different dynamical regimes, depending on the number of constraints per variable: For low constraintness, the problems are solved efficiently, i.e., in linear time. For higher constraintness, the solution times become exponential. We observe that the dynamical behavior is characterized by a fast equilibration and fluctuations around this equilibrium. If the algorithm runs long enough, an exponentially rare fluctuation towards a solution appears
- …
