Theory of Computing
-------------------
Title : Can You Beat Treewidth?
Authors : Daniel Marx
Volume : 6
Number : 5
Pages : 85-112
URL : http://www.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.