Bounded Tree-Width and CSP-Related Problems

DOI10.1007/978-3-540-77120-3_55MaRDI QIDQ5387797zbMATH OpenOpenAlexFDO

Authors Tommy Färnqvist, Peter Jonsson

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

constraint satisfactionhomomorphisminapproximabilityrelational structureComputational complexity

Mathematics Subject Classification ID

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

Recommendations

• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of counting homomorphisms seen from the other side
• Can you beat treewidth?
• scientific article; zbMATH DE number 7228418
• Constraint satisfaction with bounded treewidth revisited

Cites work

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

Cited in

(16)

• On the expressive power of CNF formulas of bounded tree- and clique-width
• Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
• Constraint satisfaction with bounded treewidth revisited
• Counting and Enumeration Problems with Bounded Treewidth
• Balancing Bounded Treewidth Circuits
• Can you beat treewidth?
• The smallest hard trees
• Answer set solving with bounded treewidth revisited
• Lower Bounds for QBFs of Bounded Treewidth
• Counting truth assignments of formulas of bounded tree-width or clique-width
• Balancing bounded treewidth circuits
• The parameterised complexity of list problems on graphs of bounded treewidth
• On planar valued CSPs
• The challenges of unbounded treewidth in parameterised subgraph counting problems
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
• Obstructions to partitions of chordal graphs

This page was built for publication: Bounded Tree-Width and CSP-Related Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387797)