Statistical mechanics of the vertex-cover problem

DOI10.1088/0305-4470/36/43/028MaRDI QIDQ5696397zbMATH OpenOpenAlexWikidataFDO

Authors Alexander Hartmann, M. Weigt

Publication date 18 October 2005

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0307236

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20)

Abstract: We review recent progress in the study of the vertex-cover problem (VC). 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 an 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 VC to a hard-core lattice gas, and then applying techniques like the replica trick or the cavity approach. Using these methods, the phase diagram of VC could be obtained exactly for connectivities $c<e$, where VC is replica symmetric. Recently, this result could be confirmed using traditional mathematical techniques. For $c>e$, the solution of 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 VC. Finally, we describe recent results for VC when studied on other ensembles of finite- and infinite-dimensional graphs.

Recommendations

• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs
• Solving vertex cover in polynomial time on hyperbolic random graphs
• Phase transition and finite-size scaling in the vertex-cover problem
• Dynamical replica analysis of processes on finitely connected random graphs: I. Vertex covering
• Analysis and comparison of three algorithms for the vertex cover problem on large graphs with low memory capacities

Cited in

(16)

• scientific article; zbMATH DE number 2046081 (Why is no real title available?)
• Organization mechanism and counting algorithm on vertex-cover solutions
• Typical performance of approximation algorithms for NP-hard problems
• Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics
• Parallel tempering for the planted clique problem
• Graphical representation and hierarchical decomposition mechanism for vertex-cover solution space
• Properties of atypical graphs from negative complexities
• What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
• Statistical mechanics of the minimum dominating set problem
• Measuring instance difficulty for combinatorial optimization problems
• Minimal vertex covers of random trees
• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs
• Phase transition and finite-size scaling in the vertex-cover problem
• Directed dominating set problem studied by cavity method: warning propagation and population dynamics
• Two faces of greedy leaf removal procedure on graphs
• Dynamical replica analysis of processes on finitely connected random graphs: I. Vertex covering

This page was built for publication: Statistical mechanics of the vertex-cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5696397)