The periodic structure of local consistency
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929569974452224 |
|---|---|
| author | Ciardo, Lorenzo Živný, Stanislav |
| author_facet | Ciardo, Lorenzo Živný, Stanislav |
| contents | We connect the mixing behaviour of random walks over a graph to the power of the local-consistency algorithm for the solution of the corresponding constraint satisfaction problem (CSP). We extend this connection to arbitrary CSPs and their promise variant. In this way, we establish a linear-level (and, thus, optimal) lower bound against the local-consistency algorithm applied to the class of aperiodic promise CSPs. The proof is based on a combination of the probabilistic method for random Erdős-Rényi hypergraphs and a structural result on the number of fibers (i.e., long chains of hyperedges) in sparse hypergraphs of large girth. As a corollary, we completely classify the power of local consistency for the approximate graph homomorphism problem by establishing that, in the nontrivial cases, the problem has linear width. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_19685 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The periodic structure of local consistency Ciardo, Lorenzo Živný, Stanislav Computational Complexity Discrete Mathematics Data Structures and Algorithms We connect the mixing behaviour of random walks over a graph to the power of the local-consistency algorithm for the solution of the corresponding constraint satisfaction problem (CSP). We extend this connection to arbitrary CSPs and their promise variant. In this way, we establish a linear-level (and, thus, optimal) lower bound against the local-consistency algorithm applied to the class of aperiodic promise CSPs. The proof is based on a combination of the probabilistic method for random Erdős-Rényi hypergraphs and a structural result on the number of fibers (i.e., long chains of hyperedges) in sparse hypergraphs of large girth. As a corollary, we completely classify the power of local consistency for the approximate graph homomorphism problem by establishing that, in the nontrivial cases, the problem has linear width. |
| title | The periodic structure of local consistency |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2406.19685 |