一句话：首次将代数长度为 1 的光滑有向图结构二分类提升到无限域，给出无限有向图着色的 NP 难判据。
本文研究无限域有向图着色问题的复杂度，旨在把有限域 CSP 的两个里程碑——Bulatov 的保守模板二分类和 Barto–Kozik–Niven 的代数长度为 1 光滑有向图结构二分类——推广到无限情形。作者证明：代数长度为 1 的光滑有向图连同其自同构群寡态子群的两条轨道可 pp-构造所有有限结构，因此除非图中存在伪环（轨道内的边），其保守图着色问题 NP 难。该工作首次克服将此类有向图结构结果从有限提升到 ω-范畴结构的障碍，此前最强结果仅推广了无向图的 Hell–Nešetřil 定理。作为推论，得到由无法 pp-构造某有限结构的轨道对丰富后的任意 ω-范畴结构的新代数不变量。
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 genera-lisation 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.
@inproceedings{paperbot8676,
title = {The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems},
author = {Johanna Brunar and Marcin Kozik and Tomáš Nagy and Michael Pinsker},
booktitle = {LICS},
year = {2025},
doi = {10.1109/lics65433.2025.00037}
}