The Parameterized Complexity of Local Consistency
Proceedings of CP 2011, Principles and Practice of Constraint Programming, 17th International Conference, Perugia, Italy, September 12-16, 2011. pp 302-316, Lecture Notes in Computer Science vol. 6876, Springer, 2011.
Abstract:We investigate the parameterized complexity of deciding whether a constraint network is k-consistent. We show that, parameterized by k, the problem is complete for the complexity class co-W. As secondary parameters we consider the maximum domain size d and the maximum number l of constraints in which a variable occurs. We show that parameterized by k+d, the problem drops down one complexity level and becomes co-W-complete. Parameterized by k+d+l the problem drops down one more level and becomes fixed-parameter tractable. We further show that the same complexity classification applies to strong k-consistency, directional k-consistency, and strong directional k-consistency.
Our results establish a super-polynomial separation between input size and time complexity. Thus we strengthen the known lower bounds on time complexity of k-consistency that are based on input size.
Preprint available from Electronic Colloquium on Computational Complexity (ECCC), Technical Report TR11-071, 2011. [PDF]