Feder–Vardi dichotomy conjecture for constraint satisfaction problems
A relational structure is a structure consisting of a domain together with relations of prescribed names and arities. For a fixed relational structure , is the decision problem whose instances are relational structures over the same vocabulary as , with question whether there is a homomorphism .
Feder–Vardi dichotomy conjecture. For any relational structure , is either NP-complete or polynomial-time solvable.
This is a major open problem in computational complexity. It is known for graph homomorphisms with one symmetric binary relation by the Hell–Nešetřil dichotomy theorem, and Feder and Vardi showed that a dichotomy for bipartite digraph homomorphism problems would imply the conjecture.
References
Primary source
Richard C. Brewster, Florent Foucaud, Pavol Hell and Reza Naserasr, “The complexity of signed graph and edge-coloured graph homomorphisms”, arXiv:1510.05502 (2016).
Additional references
3 papers in this index state this conjecture (2007–2015). The statement above is taken from the most recent of them; the others are arXiv:1201.0856, arXiv:0710.4477.
Progress summary
The standard finite-template version was proved by Bulatov and Zhuk, so the conjecture is resolved rather than open.
Feder and Vardi posed the finite-template dichotomy conjecture in the 1990s: every constraint-satisfaction problem should be either polynomial-time solvable or -complete.
Known results
- Schaefer, 1978: the dichotomy for Boolean-domain constraint problems.
- Hell and Nešetřil, 1990: the graph-homomorphism dichotomy.
- Feder and Vardi, 1993: reduction of finite-template CSPs to restricted digraph problems.
2017--2024 resolution and clarification
Bulatov and, independently, Zhuk proved the dichotomy for arbitrary finite domains; a 2024 paper supplied a simplified proof framework. An announced 2017 digraph proof by Rafiey, Kinne, and Feder was retracted after Willard found a counterexample, but this does not affect the independent theorem.
Current status (as of August 2026): the standard finite-template Feder--Vardi dichotomy is settled by the Bulatov--Zhuk theorem; the supplied sources do not establish the corresponding statement for unrestricted infinite relational structures.
Solutions 0
No solutions have been posted yet.