Can you beat treewidth?

It is well-known that constraint satisfaction problems (CSP) 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 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 O(k/logk), 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.

Authors

• Dániel Marx

Keywords

• Tree graphs
• Polynomials
• Computer science
• Relational databases
• Input Size
• Homomorphism
• Constraint Satisfaction
• Framework For Problem
• Constraint Satisfaction Problem
• Class Of Graphs
• Vocabulary
• Sufficiently Large
• Class Structure
• Domain Size
• Theoretical Literature
• Line Graph
• Vertices
• Subset Of Variables
• Idea Of The Proof
• Complete Bipartite Graph
• Clique Of Size