A combinatorial constraint satisfaction problem dichotomy classification conjecture

作者：Nesetril Jaroslav^*; Siggers Mark H; Zadori Laszlo

来源：European Journal of Combinatorics, 2010, 31(1): 280-296.

DOI：10.1016/j.ejc.2009.02.007

We 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 K(3)-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 Zadori. 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-Nesetril-Smolikova conjecture. Although these results were proved independently by Jonsson et al. and Kun respectively, we give different, shorter, proofs.

• 出版日期2010-1