A topological proof of the Hell-Nešetřil dichotomy
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913645590478848 |
|---|---|
| author | Meyer, Sebastian Opršal, Jakub |
| author_facet | Meyer, Sebastian Opršal, Jakub |
| contents | We provide a new proof of a theorem of Hell and Nešetřil [J. Comb. Theory B, 48(1):92-110, 1990] using tools from topological combinatorics based on ideas of Lovász [J. Comb. Theory, Ser. A, 25(3):319-324, 1978]. The Hell-Nešetřil Theorem provides a dichotomy of the graph homomorphism problem. It states that deciding whether there is a graph homomorphism from a given graph to a fixed graph $H$ is in P if $H$ is bipartite (or contains a self-loop), and is NP-complete otherwise. In our proof we combine topological combinatorics with the algebraic approach to constraint satisfaction problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_12627 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A topological proof of the Hell-Nešetřil dichotomy Meyer, Sebastian Opršal, Jakub Computational Complexity Algebraic Topology Combinatorics We provide a new proof of a theorem of Hell and Nešetřil [J. Comb. Theory B, 48(1):92-110, 1990] using tools from topological combinatorics based on ideas of Lovász [J. Comb. Theory, Ser. A, 25(3):319-324, 1978]. The Hell-Nešetřil Theorem provides a dichotomy of the graph homomorphism problem. It states that deciding whether there is a graph homomorphism from a given graph to a fixed graph $H$ is in P if $H$ is bipartite (or contains a self-loop), and is NP-complete otherwise. In our proof we combine topological combinatorics with the algebraic approach to constraint satisfaction problem. |
| title | A topological proof of the Hell-Nešetřil dichotomy |
| topic | Computational Complexity Algebraic Topology Combinatorics |
| url | https://arxiv.org/abs/2409.12627 |