Johanna Brunar

dblp:398/4752 · DBLP profile ↗
← Back
2ranked-venue papers
2as first author
2since 2021 · last 2026
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 first-author · 2 since 2021
YearPublicationVenuePosition
2026 When Darwin Met Ianus: Dichotomies of Expressivity
Johanna Brunar, Michael Pinsker, Moritz Schöbi
MFCS1
2025 The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
abstract
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.
Johanna Brunar, Marcin Kozik, Tomás Nagy 0001, Michael Pinsker
LICS1