Constraint Satisfaction with Bounded Treewidth RevisitedJournal of Computer and System Sciences, vol. 76, no. 2, pp. 103-114, 2010. Preliminary version of the paper appeared in the Proceedings of CP 2006 , Twelfth International Conference on Principles and Practice of Constraint Programming, September 24-29, 2006, Nantes, France. Lecture Notes in Computer Science, vol. 4204, pp. 499—513, 2006. There are significant differences between the journal version and the conference version. Abstract:We consider the constraint satisfaction problem (CSP) parameterized by the treewidth of primal, dual, and incidence graphs, combined with several other basic parameters such as domain size and arity. We determine all combinations of the considered parameters that admit fixed-parameter tractability.Download: [full paper pdf] |