Counting truth assignments of formulas of bounded tree-width or clique-width

DOI10.1016/j.dam.2006.06.020zbMath1131.68093OpenAlexW2090518395MaRDI QIDQ2473047

Eldar Fischer, Elena V. Ravve, Johann A. Makowsky

Publication date: 26 February 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2006.06.020

zbMATH Keywords

clique-widthtree-widthcounting problemssatisfiability (SAT)fixed parameter tractable (FPT)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items

Backdoors to Satisfaction ⋮ A Most General Edge Elimination Polynomial ⋮ On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width ⋮ Model counting for CNF formulas of bounded modular treewidth ⋮ The rank-width of edge-coloured graphs ⋮ Sum-of-Products with Default Values: Algorithms and Complexity Results ⋮ Grammars and clique-width bounds from split decompositions ⋮ Satisfiability of acyclic and almost acyclic CNF formulas ⋮ Weighted positive binary decision diagrams for exact probabilistic inference ⋮ From tree-decompositions to clique-width terms ⋮ Tensor network contractions for \#SAT ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Algorithms for Propositional Model Counting ⋮ On the expressive power of CNF formulas of bounded tree- and clique-width ⋮ Graph classes with and without powers of bounded clique-width ⋮ Compact labelings for efficient first-order model-checking ⋮ Unnamed Item ⋮ The enumeration of vertex induced subgraphs with respect to the number of components ⋮ Latency-bounded target set selection in social networks ⋮ On efficiently solvable cases of quantum \(k\)-SAT ⋮ Solving \#SAT using vertex covers ⋮ An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents ⋮ Satisfiability of Acyclic and almost Acyclic CNF Formulas (II) ⋮ Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems ⋮ $\mathbb F$ -Rank-Width of (Edge-Colored) Graphs ⋮ The complexity landscape of decompositional parameters for ILP ⋮ An extended tree-width notion for directed graphs related to the computation of permanents ⋮ Algorithms for propositional model counting ⋮ Bounded treewidth as a key to tractability of knowledge representation and reasoning ⋮ Unnamed Item ⋮ Variable Influences in Conjunctive Normal Forms ⋮ An extension of the bivariate chromatic polynomial ⋮ Planar 3-SAT with a clause/variable cycle ⋮ Unnamed Item ⋮ Backdoors to q-Horn

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Satisfiability, branch-width and Tseitin tautologies
• Algorithmic uses of the Feferman-Vaught theorem
• Monadic second-order evaluations on tree-decomposable graphs
• Tutte polynomials computable in polynomial time
• The intractability of resolution
• On generating all maximal independent sets
• Tree clustering for constraint networks
• The monadic second-order logic of graphs. VII: Graphs as relational structures
• On the complexity of regular resolution and the Davis-Putnam procedure
• All structured programs have small tree width and good register allocation
• Splitting formulas for Tutte polynomials
• Logical description of context-free graph languages
• Farrell polynomials on graphs of bounded tree width
• Tree-width and the monadic quantifier hierarchy.
• Coloured Tutte polynomials and Kauffman brackets for graphs of bounded tree width
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• The complexity of first-order and monadic second-order logic revisited
• Complexity of generalized satisfiability counting problems
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Partition-based logical reasoning for first-order and propositional theories
• On the colored Tutte polynomial of a graph of bounded treewidth
• Approximating clique-width and branch-width
• Recognizability, hypergraph operations, and logical types
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Fusion in relational structures and the verification of monadic second-order properties
• Many hard examples for resolution
• Complexity of Finding Embeddings in a k-Tree
• Unification as a complexity measure for logic programming
• Polynomial Invariants of Graphs
• The Complexity of Enumeration and Reliability Problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• The complexity of satisfiability problems
• Graph-Theoretic Concepts in Computer Science
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic