Annual Symposium on Foundations of Computer Science · 2007 · 38 citations · 19 references
ComputingComputer ScienceAlgorithmsCombinatoricsTheory Of ComputationAlgorithmic ComplexityComputational ComplexityConstraint SatisfactionGraph AlgorithmsGraph TheoryTime ComplexityComplexity-theoretic ReductionsComputational Complexity Of Graph AlgorithmsCsp Solving
It is well-known that constraint satisfaction problems (CSP) can be solved in time n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(k)</sup> if the treewidth of the primal graph of the instance is at most k and n is the size of the input. We show that no algorithm can be significantly better than this treewidth-based algorithm, even if we restrict the problem to some special class of primal graphs. Formally, let g be an arbitrary class of graphs and assume that there is an algorithm A solving binary CSP for instances whose primal graph is in g. We prove that if the running lime of A is f(G)n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(k/logk)</sup> , where k is the treewidth of the primal graph G and f is an arbitrary function, then the Exponential Time Hypothesis fails. We prove the result also in the more general framework of the homomorphism problem for bounded-arity relational structures. For this problem, the treewidth of the core of the left-hand side structure plays the same role as the. treewidth of the primal graph above.
19
Michael R. Fellows · Electronic Notes in Theoretical Computer Science · 2002 · 2.9K citations · Full text
The complexity of satisfiability problems
Thomas J. Schaefer · 1978 · 1.8K citations · Full text
Noga Alon, Raphael Yuster, Uri Zwick · Journal of the ACM · 1995 · 1K citations · Full text