Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-071 | 4th May 2011 13:27

The Parameterized Complexity of Local Consistency

Revision #1
Authors: Serge Gaspers, Stefan Szeider
Accepted on: 4th May 2011 13:27
Keywords:

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

Paper:

TR11-071 | 27th April 2011 14:06

The Parameterized Complexity of Local Consistency

TR11-071
Authors: Serge Gaspers, Stefan Szeider
Publication: 4th May 2011 00:02
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.