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.