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

Question

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.

Answer 1

Observe that the negation of a (monotone) CNF-formula F is a (monotone) DNF G which has the same hypergraph. Moreover #G = 2^n-#F where n is the number of variables of F. Thus, every known (structural) easyness and hardness result for the exact counting on CNF generalizes to DNF.

In other words, counting the number of model of beta-acyclic DNF is easy (from the paper you cite). And it is hard for alpha-acyclic DNF (just add a big clause containing every variables in a CNF).

It is also hard for hypertrees: take a DNF F and construct F' by adding a fresh vertex x in every clause. #F = #F' and H(F') is a hypertree: take T rooted in x and attached to it every other variables as leaves. Observe that this reduction also shows that the problem #(k+1)-DNF restricted to hypertree is harder than #k-DNF so I doubt that you can compile them into OBDD. Moreover, taking k = 2 (already hard for counting), the transformation leads to a hypertree 3-DNF where every edge is a path in the tree so even this restriction is unlikely to yield easy cases.

DNF however differ from CNF as approximating the number of model is possible in the first case (see On the hardness of approximate reasoning Dan Roth - Artificial Intelligence, 1996 for the hardness of approximating and Monte-Carlo Approximation Algorithms for Enumeration Problems Richard Karp, Michael Luby, Neal Madras).