A combinatorial constraint satisfaction problem dichotomy classification conjecture

AbstractWe further generalise a construction–the fibre construction–that was developed in an earlier paper of the first two authors. The extension in this paper gives a polynomial-time reduction of CSP(H) for any relational system H to CSP(P) for any relational system P that meets a certain technical partition condition, that of being K3-partitionable.Moreover, we define an equivalent condition on P, that of being block projective, and using this show that our construction proves NP-completeness for exactly those CSPs that are conjectured to be NP-complete by the CSP dichotomy classification conjecture made by Bulatov, Jeavons and Krohkin, and by Larose and Zádori. We thus provide two new combinatorial versions of the CSP dichotomy classification conjecture.As with our previous version of the fibre construction, we are able to address restricted versions of the dichotomy conjecture. In particular, we reduce the Feder–Hell–Huang conjecture to the CSP dichotomy classification conjecture, and we prove the Kostochka–Nešetřil–Smolíková conjecture. Although these results were proved independently by Jonsson et al. and Kun respectively, we give different, shorter, proofs