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 $\ell$ 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+\ell$ 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.

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 $\ell$ 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+\ell$ 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.