Spanning Trees in Random Satisfiability Problems
arXiv:cond-mat/0507231 · doi:10.1088/0305-4470/39/18/008
Abstract
Working with tree graphs is always easier than with loopy ones and spanning trees are the closest tree-like structures to a given graph. We find a correspondence between the solutions of random K-satisfiability problem and those of spanning trees in the associated factor graph. We introduce a modified survey propagation algorithm which returns null edges of the factor graph and helps us to find satisfiable spanning trees. This allows us to study organization of satisfiable spanning trees in the space spanned by spanning trees.
12 pages, 5 figures, published version
References in corpus (6)
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Clustering of solutions in the random satisfiability problem
- Statistical mechanics of the random K-SAT model
- The Entropy of the K-Satisfiability Problem
- Instability of one-step replica-symmetry-broken phase in satisfiability problems
- Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms