Energy landscapes of some matching-problem ensembles

The maximum-weight matching problem and the behavior of its energy landscape is numerically investigated. We apply a perturbation method adapted from the analysis of spin glasses. This method provides insight into the complexity of the energy landscape of different ensembles. Erdős–Rényi graphs and...

Full description

Saved in:
Bibliographic Details
Published in:Journal of physic, complexity complexity, 2023-12, Vol.4 (4), p.45009
Main Authors: Kahlke, Till, Hartmann, Alexander K
Format: Article
Language:English
Subjects:
complexity
computer simulations
ground states
matching
perturbation techniques
random graphs
replica-symmetry breaking
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The maximum-weight matching problem and the behavior of its energy landscape is numerically investigated. We apply a perturbation method adapted from the analysis of spin glasses. This method provides insight into the complexity of the energy landscape of different ensembles. Erdős–Rényi graphs and ring graphs with randomly added edges are considered, and two types of distributions for the random edge weights are used. Fast and scalable algorithms exist for maximum weight matching, allowing us to study large graphs with more than 10 5 nodes. Our results show that the structure of the energy landscape for standard ensembles of matching is simple, comparable to the energy landscape of a ferromagnet. Nonetheless, for some of the ensembles presented here, our results allow for the presence of complex energy landscapes in the spirit of a replica-symmetry breaking scenario.
ISSN:2632-072X
2632-072X
DOI:10.1088/2632-072X/ad0d88