Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs.

M Weigt1, A K Hartmann

  • 1Institute for Theoretical Physics, University of Göttingen, Bunsenstrasse 9, 37073 Göttingen, Germany.

Physical Review Letters
|April 6, 2001
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

In and beyond the Griffiths phase: A large-deviation study of the magnetic susceptibility of the two-dimensional bond-diluted Ising model.

Physical review. E·2024
Same author

Author Correction: Understanding epistatic networks in the B1 β-lactamases through coevolutionary statistical modeling and deep mutational scanning.

Nature communications·2024
Same author

Understanding epistatic networks in the B1 β-lactamases through coevolutionary statistical modeling and deep mutational scanning.

Nature communications·2024
Same author

Statistical methods for linking material composition to recombination losses in optoelectronic devices.

The Review of scientific instruments·2024
Same author

Metastate analysis of the ground states of two-dimensional Ising spin glasses.

Physical review. E·2023
Same author

Cutting-plane algorithms and solution whitening for the vertex-cover problem.

Physical review. E·2022
Same journal

Erratum: Bacterial Turbulence at Compressible Fluid Interfaces [Phys. Rev. Lett. 136, 138301 (2026)].

Physical review letters·2026
Same journal

Unveiling Light-Quark Yukawa Flavor Structure via Dihadron Fragmentation at Lepton Colliders.

Physical review letters·2026
Same journal

Adaptable Route to Fast Coherent State Transport via Bang-Bang-Bang Protocols.

Physical review letters·2026
Same journal

Topological Transition and Emergence of Elasticity of Dislocation in Skyrmion Lattice: Beyond Kittel's Magnetic-Polar Analogy.

Physical review letters·2026
Same journal

Pound-Drever-Hall Method for Superconducting-Qubit Readout.

Physical review letters·2026
Same journal

Coupling a ^{73}Ge Nuclear Spin to an Electrostatically Defined Quantum Dot in Silicon.

Physical review letters·2026
See all related articles

We analytically describe backtracking algorithm solution times for the vertex-cover problem on random graphs. Two transitions were found: one from linear to exponential time, and another at the solvability threshold.

Area of Science:

  • Computational complexity theory
  • Graph algorithms
  • Statistical physics

Background:

  • The vertex-cover problem is a classic NP-complete problem.
  • Random graphs provide a framework for studying complex systems.
  • Understanding algorithm performance on random graphs is crucial for theoretical computer science.

Purpose of the Study:

  • To analytically describe the solution time of backtracking algorithms for the vertex-cover problem on finite-connectivity random graphs.
  • To identify and characterize phase transitions in the algorithm's performance.
  • To relate algorithm-dependent transitions to algorithm-independent phase transitions in problem solvability.

Main Methods:

  • Analytical description of solution time.
  • Identification of two distinct transitions.

Related Experiment Videos

  • Characterization of computational complexity at the solvability threshold.
  • Corroboration through numerical simulations.

    • Main Results:

    • A dynamical transition from linear to exponential solution times, dependent on the algorithm.
    • An algorithm-independent phase transition in solvability at a critical threshold.
    • The maximum computational complexity is precisely at this solvability threshold.

    Conclusions:

    • The study provides a detailed analytical understanding of backtracking algorithm performance on random graphs for the vertex-cover problem.
    • Two critical transitions govern the computational complexity and solvability.
    • The findings bridge algorithm-specific behavior with fundamental properties of the problem instances.