ECCC-Report TR11-071https://eccc.weizmann.ac.il/report/2011/071Comments and Revisions published for TR11-071en-usWed, 04 May 2011 13:27:40 +0300
Revision 1
| The Parameterized Complexity of Local Consistency |
Serge Gaspers,
Stefan Szeider
https://eccc.weizmann.ac.il/report/2011/071#revision1We 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.Wed, 04 May 2011 13:27:40 +0300https://eccc.weizmann.ac.il/report/2011/071#revision1
Paper TR11-071
| The Parameterized Complexity of Local Consistency |
Serge Gaspers,
Stefan Szeider
https://eccc.weizmann.ac.il/report/2011/071We 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.Wed, 04 May 2011 00:02:10 +0300https://eccc.weizmann.ac.il/report/2011/071