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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2023-01-01
|
| Series: | Journal of Physics: Complexity |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/2632-072X/ad0d88 |
| _version_ | 1797447717026267136 |
|---|---|
| author | Till Kahlke Alexander K Hartmann |
| author_facet | Till Kahlke Alexander K Hartmann |
| author_sort | Till Kahlke |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T13:59:57Z |
| format | Article |
| id | doaj.art-6eabf6f15500432aa5b0ec96c06a800a |
| institution | Directory Open Access Journal |
| issn | 2632-072X |
| language | English |
| last_indexed | 2024-03-09T13:59:57Z |
| publishDate | 2023-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | Journal of Physics: Complexity |
| spelling | doaj.art-6eabf6f15500432aa5b0ec96c06a800a2023-11-30T08:56:17ZengIOP PublishingJournal of Physics: Complexity2632-072X2023-01-014404500910.1088/2632-072X/ad0d88Energy landscapes of some matching-problem ensemblesTill Kahlke0Alexander K Hartmann1https://orcid.org/0000-0001-6865-5474Institut für Physik, Carl von Ossietzky Universität Oldenburg , 26111 Oldenburg, GermanyInstitut für Physik, Carl von Ossietzky Universität Oldenburg , 26111 Oldenburg, GermanyThe 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.https://doi.org/10.1088/2632-072X/ad0d88matchingcomplexityperturbation techniquesrandom graphsground statesreplica-symmetry breaking |
| spellingShingle | Till Kahlke Alexander K Hartmann Energy landscapes of some matching-problem ensembles Journal of Physics: Complexity matching complexity perturbation techniques random graphs ground states replica-symmetry breaking |
| title | Energy landscapes of some matching-problem ensembles |
| title_full | Energy landscapes of some matching-problem ensembles |
| title_fullStr | Energy landscapes of some matching-problem ensembles |
| title_full_unstemmed | Energy landscapes of some matching-problem ensembles |
| title_short | Energy landscapes of some matching-problem ensembles |
| title_sort | energy landscapes of some matching problem ensembles |
| topic | matching complexity perturbation techniques random graphs ground states replica-symmetry breaking |
| url | https://doi.org/10.1088/2632-072X/ad0d88 |
| work_keys_str_mv | AT tillkahlke energylandscapesofsomematchingproblemensembles AT alexanderkhartmann energylandscapesofsomematchingproblemensembles |