Hypergraph acyclicity and propositional model counting

DOI10.1007/978-3-319-09284-3_29MaRDI QIDQ3192085zbMATH OpenOpenAlexFDO

Authors Florent Capelli, Arnaud Durand, Stefan Mengel

Publication date 26 September 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.6307

Hypergraphs (05C65) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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.

Recommendations

Cited in

(7)

This page was built for publication: Hypergraph acyclicity and propositional model counting

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