Graph Homomorphisms and Universal Algebra
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914507319672832 |
|---|---|
| author | Bodirsky, Manuel |
| author_facet | Bodirsky, Manuel |
| contents | Constraint satisfaction problems are computational problems that naturally appear in many areas of theoretical computer science. One of the central themes is their computational complexity, and in particular the border between polynomial-time tractability and NP-hardness. In this course we introduce the universal-algebraic approach to study the computational complexity of finite-domain CSPs. The course covers in particular the cyclic terms and bounded width theorems. To keep the presentation accessible, we start the course in the tangible setting of directed graphs and graph homomorphism problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_14243 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Graph Homomorphisms and Universal Algebra Bodirsky, Manuel Computational Complexity Discrete Mathematics Logic Rings and Algebras Constraint satisfaction problems are computational problems that naturally appear in many areas of theoretical computer science. One of the central themes is their computational complexity, and in particular the border between polynomial-time tractability and NP-hardness. In this course we introduce the universal-algebraic approach to study the computational complexity of finite-domain CSPs. The course covers in particular the cyclic terms and bounded width theorems. To keep the presentation accessible, we start the course in the tangible setting of directed graphs and graph homomorphism problems. |
| title | Graph Homomorphisms and Universal Algebra |
| topic | Computational Complexity Discrete Mathematics Logic Rings and Algebras |
| url | https://arxiv.org/abs/2602.14243 |