2014/01/24 by Florent Capelli, Capelli, Florent, Arnaud Durand +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #cs.AI #cs.CC
paper · pdf · doi:10.48550/arxiv.1401.6307
arxiv created 2014/01/24 · openalex publication_date 2014/01/24 · arxiv updated 2014/01/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that the propositional model counting problem #SAT for CNF- formulas with hypergraphs that allow a disjoint branches decomposition can be solved in polynomial time. We show that this class of hypergraphs is incomparable to hypergraphs of bounded incidence cliquewidth which were the biggest class of hypergraphs for which #SAT was known to be solvable in polynomial time so far. Furthermore, we present a polynomial time algorithm that computes a disjoint branches decomposition of a given hypergraph if it exists and rejects otherwise. Finally, we show that some slight extensions of the class of hypergraphs with disjoint branches decompositions lead to intractable #SAT, leaving open how to generalize the counting result of this paper.