Hard Optimization Problems have Soft Edges
| Autor: | Marino, Raffaele, Kirkpatrick, Scott |
|---|---|
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | Sci Rep 13, 3671 (2023) |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1038/s41598-023-30391-8 |
| Popis: | Finding a Maximum Clique is a classic property test from graph theory; find any one of the largest complete subgraphs in an Erd\"os-R\'enyi G(N, p) random graph. We use Maximum Clique to explore the structure of the problem as a function of N, the graph size, and K, the clique size sought. It displays a complex phase boundary, a staircase of steps at each of which 2log2 N and Kmax, the maximum size of a clique that can be found, increases by 1. Each of its boundaries has a finite width, and these widths allow local algorithms to find cliques beyond the limits defined by the study of infinite systems. We explore the performance of a number of extensions of traditional fast local algorithms, and find that much of the "hard" space remains accessible at finite N. The "hidden clique" problem embeds a clique somewhat larger than those which occur naturally in a G(N, p) random graph. Since such a clique is unique, we find that local searches which stop early, once evidence for the hidden clique is found, may outperform the best message passing or spectral algorithms. Comment: arXiv admin note: text overlap with arXiv:1807.09091 |
| Databáze: | arXiv |
| Externí odkaz: |
|