期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 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+ 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.
