The Parameterized Complexity of Local ConsistencyProceedings 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[2]. 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[1]-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] |