On complexity of restricted fragments of Decision DNNF

Decision $\text{textsc}dnnf$ (a.k.a. ${\wedge }_d$-$\text{textsc}fbdd$) is an important special case of Decomposable Negation Normal Form ($\text{textsc}dnnf$), a landmark knowledge compilation model. Like other known $\text{textsc}dnnf$ restrictions, Decision $\text{textsc}dnnf$ admits $\text{textsc}fpt$ sized representation of $\text{textsc}cnf$s of bounded \emph{primal} treewidth. However, unlike other restrictions, the complexity of representation for $\text{textsc}cnf$s of bounded \emph{incidence} treewidth is wide open. In[arxiv:1708.07767], we resolved this question for two restricted classes of Decision $\text{textsc}dnnf$ that we name ${\wedge }_d$-$\text{textsc}obdd$ and Structured Decision $\text{textsc}dnnf$. In particular, we demonstrated that, while both these classes have $\text{textsc}fpt$-sized representations for $\text{textsc}cnf$s of bounded primal treewidth, they need $\text{textsc}xp$-size for representation of $\text{textsc}cnf$s of bounded incidence treewidth. In the main part of this paper we carry out an in-depth study of the ${\wedge }_d$-$\text{textsc}obdd$ model. We formulate a generic methodology for proving lower bounds for the model. Using this methodology, we reestablish the $\text{textsc}xp$ lower bound provided in [arxiv:1708.07767]. We also provide exponential separations between $\text{textsc}fbdd$ and ${\wedge }_d$-$\text{textsc}obdd$ and between ${\wedge }_d$-$\text{textsc}obdd$ and an ordinary $\text{textsc}obdd$. We study the complexity of Apply operation for ${\wedge }_d$-$\text{textsc}obdd$. While, in general, the Apply operation leads to exponential blow up of the resulting model, we identify a special restricted case where the Apply operation can be carried out efficiently. We introduce a relaxed version of Structured Decision $\text{textsc}dnnf$ that we name Structured ${\wedge }_d$-$\text{textsc}fbdd$ and demonstrate that this model is quite powerful for $\text{textsc}cnf$s of bounded incidence treewidth.