Statistical mechanics of the vertex-cover problem

DOI10.1088/0305-4470/36/43/028zbMATH Open1077.68073arXivcond-mat/0307236OpenAlexW1978652044WikidataQ58001593 ScholiaQ58001593MaRDI QIDQ5696397FDOQ5696397

Authors: Alexander Hartmann, M. Weigt 

Publication date: 18 October 2005

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

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.

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

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

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)

Cited In (13)

• Statistical mechanics of the minimum dominating set problem
• Phase transition and finite-size scaling in the vertex-cover problem
• What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO
• Title not available (Why is that?)
• Minimal dominating set problem studied by simulated annealing and cavity method: analytics and population dynamics
• Parallel tempering for the planted clique problem
• Minimal vertex covers of random trees
• 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
• Properties of atypical graphs from negative complexities
• Measuring instance difficulty for combinatorial optimization problems
• Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs

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)