# Complexity of #SAT for monotone DNF formulae whose hypergraph is a hypertree

A monotone DNF on variables $x_1, \ldots, x_n$ is a disjunction of clauses, each clause being a conjunction of some of the $x_1, \ldots, x_n$. The #SAT problem asks, given a monotone DNF $\Phi$, how many assignments (i.e., functions from the variables to $\{0, 1\}$) make $\Phi$ true. As this problem is #P-hard, I study it for restricted classes of DNF formulae.

The hypergraph of a DNF formula has as vertices the variables, and has one hyperedge per clause which contains precisely the variables of the clause. The requirement that I impose is that the hypergraph of the input DNF is a hypertree: in other words there is a tree $T$ on the variables such that each clause is a connected subtree of $T$.

Is anything known about the complexity of #SAT for monotone DNF formulae obeying this restriction? Is it still #P-hard, or does it become PTIME?

Depending on whether this is hard or not, I am also curious about other possible restrictions on the hypergraph, e.g., alpha-acyclicity, beta-acyclicity, or the strenghtening of the hypertree condition where each clause must be a connected path of the tree $T$ (I do not know a name for these hypergraphs).

Some remarks on the problem. I think it is the case that, if the size of the clauses is bounded by a constant, the problem can be solved in PTIME by writing an OBDD for the formula following $T$. However, if there is no bound on clause size, this approach doesn't seem to work, but on the other hand the constrained structure imposed by $T$ does not make it easy to encode arbitrary counting problems, so I don't know how to show hardness.

I am aware of works that study the complexity of #SAT under various constraints on the input formulae, such as this one for beta-acyclicity, but the definition here is for hypergraphs on an input CNF formula, and I didn't find anything relevant about DNF inputs.