Quantified Constraint Satisfaction and Bounded Treewidth

Keywords

Constraint satisfaction problem, Treewidth, Bounded function, Constraint satisfaction, Constraint (computer-aided design)

References

• Complexity of K-Tree Structured Constraint Satisfaction ProblemsEugene C. Freuder — 1990
• A Game-Theoretic Approach to Constraint SatisfactionPhokion G. Kolaitis, Moshe Y. Vardi — 2000
• Collapsibility and Consistency in Quantified Constraint SatisfactionHubie Chen — 2004
• Tree Clustering for Constraint NetworksRina Dechter, Judea Pearl — 1989
• A linear time algorithm for finding tree-decompositions of small treewidthHans L. Bodlaender — 1993
• Conjunctive-query containment and constraint satisfactionPhokion G. Kolaitis, Moshe Y. Vardi — 1998
• A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean FormulasBengt Aspvall, Michael F. Plass, Robert E. Tarjan — 1979
• The complexity of homomorphism and constraint satisfaction problems seen from the other sideMartin Grohe — 2003
• Constraint Satisfaction, Bounded Treewidth, and Finite-Variable LogicsVíctor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi — 2002
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small TreewidthHans L. Bodlaender — 1996
• Journal of Computer and System SciencesJessica A. Enright, Kitty Meeks, Fiona Skerman
• On the Computational Complexity of Quantified Horn ClausesMarek Karpinski, H. Buning, P. Schmitt — 1987
• Quantified Constraints: Algorithms and ComplexityF. Börner, A. Bulatov, P. Jeavons — 2003

Cited by

• The Complexity of Quantified Constraint Satisfaction Problems under Structural RestrictionsGeorg Gottlob, Gianluigi Greco, Francesco Scarcello — 2005
• New Width Parameters of GraphsMartin Vatshelle — 2012
• Modélisation et résolution de problèmes de décision et d'optimisation hiérarchiques en utilisant des contraintes quantifiées. (Decision and hierarchical optimisation problem modeling and solving by use of quantified contraints)Jérémie Vautard — 2010
• On the Complexity of Resolution-based Proof SystemsSergi Oliva Valls — 2013
• CSP Properties for Quantified Constraints: Definitions and ComplexityLucas Bordeaux, Marco Cadoli, Toni Mancini — 2005
• Evaluating and certifying QBFs: A comparison of state-of-the-art toolsMassimo Narizzano, Claudia Peschiera, Luca Pulina — 2009
• Tree decompositions and social graphsAaron Adcock, Blair D. Sullivan, Michael W. Mahoney — 2014
• Decomposing Quantified Conjunctive (or Disjunctive) FormulasHubie Chen, Víctor Dalmau — 2012
• Bounded-width QBF is PSPACE-completeAlbert Atserias, Sergi Oliva — 2014
• Generalizing consistency and other constraint properties to quantified constraintsLucas Bordeaux, Marco Cadoli, Toni Mancini — 2007
• Solving quantified constraint satisfaction problemsIan P. Gent, Peter Nightingale, Andrew Rowley — 2008
• Preprocessing Quantified Constraint Satisfaction Problems with Value Reordering and Directional Arc and Path ConsistencyKostas Stergiou — 2008
• SAT-Based Approaches to Treewidth Computation: An EvaluationJeremias Berg, Matti J„ärvisalo — 2014
• Abstract Branching for Quantified FormulasMarco Benedetti — 2006
• A solver for quantified Boolean and linear constraintsLucas Bordeaux, Lintao Zhang — 2007
• Does Treewidth Help in Modal Satisfiability?M. Praveen — 2010
• Tractable Reasoning in First-Order Knowledge Bases with Disjunctive InformationYongmei Liu, Hector J. Levesque — 2005
• Fixed-Parameter Hierarchies inside PSPACEGuoqiang Pan, Moshe Y. Vardi — 2006
• Parameterized complexity of some problems in concurrency and verification[HBNI Th 39]M. Praveen — 2011
• Practical Aspects of the Graph Parameter Boolean-widthSadia Sharmin — 2014

Related papers

• Fixed-Parameter Hierarchies inside PSPACEGuoqiang Pan, Moshe Y. Vardi — 2006
• The Complexity of Quantified Constraint Satisfaction Problems under Structural RestrictionsGeorg Gottlob, Gianluigi Greco, Francesco Scarcello — 2005
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small TreewidthHans L. Bodlaender — 1996
• Constraint Satisfaction, Bounded Treewidth, and Finite-Variable LogicsVíctor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi — 2002
• Parameterized Complexity TheoryJörg Flum, Martin Grohe — 2006
• Complexity of K-Tree Structured Constraint Satisfaction ProblemsEugene C. Freuder — 1990
• Graph Minors. II. Algorithmic Aspects of Tree-WidthNeil Robertson, Paul Seymour — 1986
• Resolution for Quantified Boolean FormulasHans Kleine Büning, Marek Karpiński, Andreas Flögel — 1995
• Collapsibility and Consistency in Quantified Constraint SatisfactionHubie Chen — 2004