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

Computational complexityconstraint satisfactionhomomorphisminapproximabilityrelational structure

Mathematics Subject Classification ID

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

• 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
• 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?)
• 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 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
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Parameterized Complexity of Counting Problems

Cited in

(17)

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

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)