Bounded Tree-Width and CSP-Related Problems

DOI10.1007/978-3-540-77120-3_55zbMath1193.68130OpenAlexW1872146596MaRDI QIDQ5387797

Peter Jonsson, Tommy Färnqvist

Publication date: 27 May 2008

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77120-3_55

zbMATH Keywords

homomorphismrelational structureconstraint satisfactionComputational complexityinapproximability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

On planar valued CSPs ⋮ Obstructions to partitions of chordal graphs ⋮ The challenges of unbounded treewidth in parameterised subgraph counting problems ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• The complexity of counting homomorphisms seen from the other side
• List homomorphisms of graphs with bounded degrees
• List homomorphisms to reflexive graphs
• On the algebraic structure of combinatorial problems
• Quickly excluding a planar graph
• Conjunctive-query containment and constraint satisfaction
• List homomorphisms and circular arc graphs
• Level of repair analysis and minimum cost homomorphisms of graphs
• The Approximability of Constraint Satisfaction Problems
• Complexity of conservative constraint satisfaction problems
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Parameterized Complexity of Counting Problems
• Bi‐arc graphs and the complexity of list homomorphisms
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Full Constraint Satisfaction Problems
• Generalised Integer Programming Based on Logically Defined Relations