
Decision DNNF (a.k.a. $\wedge_d$-FBDD) is an important special case of Decomposable Negation Normal Form (DNNF). Decision DNNF admits FPT sized representation of CNFs of bounded \emph{primal} treewidth. However, the complexity of representation for CNFs of bounded \emph{incidence} treewidth is wide open. In the main part of this paper we carry out an in-depth study of the $\wedge_d$-OBDD model. We formulate a generic methodology for proving lower bounds for the model. Using this methodology, we reestablish the XP lower bound provided in [arxiv:1708.07767]. We also provide exponential separations between FBDD and $\wedge_d$-OBDD and between $\wedge_d$-OBDD and an ordinary OBDD. The last separation is somewhat surprising since $\wedge_d$-FBDD can be quasipolynomially simulated by FBDD. In the remaining part of the paper, we introduce a relaxed version of Structured Decision DNNF that we name Structured $\wedge_d$-FBDD. We demonstrate that this model is quite powerful for CNFs of bounded incidence treewidth: it has an FPT representation for CNFs that can be turned into ones of bounded primal treewidth by removal of a constant number of clauses (while for both $\wedge_d$-OBDD and Structured Decision DNNF an XP lower bound is triggered by just two long clauses).
FOS: Computer and information sciences, Computer Science - Computational Complexity, Computational Complexity (cs.CC)
FOS: Computer and information sciences, Computer Science - Computational Complexity, Computational Complexity (cs.CC)
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
