Theory of Computing ------------------- Title : Can You Beat Treewidth? Authors : Daniel Marx Volume : 6 Number : 5 Pages : 85-112 URL : https://theoryofcomputing.org/articles/v006a005 Abstract -------- It is well-known that constraint satisfaction problems (CSP) over an unbounded domain can be solved in time n^{O(k)} 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 do significantly better than this treewidth-based algorithm, even if we restrict the problem to some special class of primal graphs. Formally, let A be an algorithm solving binary CSP (i.e., CSP where every constraint involves two variables). We prove that if there is a class {\cal G} of graphs with unbounded treewidth such that the running time of algorithm A is f(G) n^{o(k/log k)} on instances whose primal graph G is in {\cal G}, where k is the treewidth of the primal graph G and f is an arbitrary function, then the Exponential Time Hypothesis (ETH) 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. Finally, we use the results to obtain corollaries on the complexity of (Colored/Partitioned) Subgraph Isomorphism.