Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

The Parameterized Complexity of Local Consistency

RSS-Feed




Revision #1
Authors: Serge Gaspers, Stefan Szeider
Accepted on: 4th May 2011 13:27
Downloads: 5548
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
Downloads: 3102
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.



ISSN 1433-8092 | Imprint