7 papers
When Darwin met Ianus: dichotomies of expressivity
Johanna Brunar, Michael Pinsker, Moritz Schöbi
The classifications of temporal and phylogeny constraint languages stand among the most seminal complexity classifications within infinite-domain Constraint Satisfaction Problems (…
The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
Johanna Brunar, Marcin Kozik, Tomáš Nagy +1
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 template…
The Golden Path to Guarded Monotone Strict NP
Alexey Barsukov, Michael Pinsker, Jakub Rydval
Guarded Monotone Strict NP (GMSNP) extends Monotone Monadic Strict NP (MMSNP) by guarded existentially quantified predicates of arbitrary arities. We prove that the containment and…
Decidability of Interpretability
Roman Feller, Michael Pinsker
The Bodirsky-Pinsker conjecture asserts a P vs. NP-complete dichotomy for the computational complexity of Constraint Satisfaction Problems (CSPs) of first-order reducts of finitely…
An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
Roman Feller, Michael Pinsker
For a set F of finite tournaments, the F-free orientation problem is the problem of deciding if a given finite undirected graph can be oriented in such a way that the resulting ori…
The random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra
Michael Pinsker, Jakub Rydval, Moritz Schöbi +1
We prove that the random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra, hereby answering an open question of Bartošová and Scow.