The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908935185760256 |
|---|---|
| author | Brunar, Johanna Kozik, Marcin Nagy, Tomáš Pinsker, Michael |
| author_facet | Brunar, Johanna Kozik, Marcin Nagy, Tomáš Pinsker, Michael |
| contents | Two major milestones on the road to the full complexity dichotomy for finite-domain constraint satisfaction problems were Bulatov's proof of the dichotomy for conservative templates, and the structural dichotomy for smooth digraphs of algebraic length 1 due to Barto, Kozik, and Niven. We lift the combined scenario to the infinite, and prove that any smooth digraph of algebraic length 1 pp-constructs, together with pairs of orbits of an oligomorphic subgroup of its automorphism group, every finite structure -- and hence its conservative graph-colouring problem is NP-hard -- unless the digraph has a pseudo-loop, i.e. an edge within an orbit. We thereby overcome, for the first time, previous obstacles to lifting structural results for digraphs in this context from finite to $ω$-categorical structures; the strongest lifting results hitherto not going beyond a generalisation of the Hell-Nešetřil theorem for undirected graphs. As a consequence, we obtain a new algebraic invariant of arbitrary $ω$-categorical structures enriched by pairs of orbits which fail to pp-construct some finite structure. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_17060 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems Brunar, Johanna Kozik, Marcin Nagy, Tomáš Pinsker, Michael Logic in Computer Science Two major milestones on the road to the full complexity dichotomy for finite-domain constraint satisfaction problems were Bulatov's proof of the dichotomy for conservative templates, and the structural dichotomy for smooth digraphs of algebraic length 1 due to Barto, Kozik, and Niven. We lift the combined scenario to the infinite, and prove that any smooth digraph of algebraic length 1 pp-constructs, together with pairs of orbits of an oligomorphic subgroup of its automorphism group, every finite structure -- and hence its conservative graph-colouring problem is NP-hard -- unless the digraph has a pseudo-loop, i.e. an edge within an orbit. We thereby overcome, for the first time, previous obstacles to lifting structural results for digraphs in this context from finite to $ω$-categorical structures; the strongest lifting results hitherto not going beyond a generalisation of the Hell-Nešetřil theorem for undirected graphs. As a consequence, we obtain a new algebraic invariant of arbitrary $ω$-categorical structures enriched by pairs of orbits which fail to pp-construct some finite structure. |
| title | The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2501.17060 |