pdf icon
Volume 6 (2010) Article 5 pp. 85-112
Can You Beat Treewidth?
Received: September 3, 2008
Published: August 27, 2010
Download article from ToC site:
[PDF (386K)]    [PS (1369K)]    [PS.GZ (313K)]
[Source ZIP]
Keywords: constraint satisfaction, treewidth, homomorphism
ACM Classification: F.2.2, G.2.2
AMS Classification: 68Q17, 68R10

Abstract: [Plain Text Version]

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 $\mathbb{A}$ be an algorithm solving binary CSP (i.e., CSP where every constraint involves two variables). We prove that if there is a class $\mathcal G$ of graphs with unbounded treewidth such that the running time of algorithm $\mathbb{A}$ is $f(G)n^{o(k/\log k)}$ on instances whose primal graph $G$ is in $\mathcal 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.