Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ arXiv.org e-Print Ar...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
https://dx.doi.org/10.48550/ar...
Article . 2025
License: arXiv Non-Exclusive Distribution
Data sources: Datacite
versions View all 2 versions
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

On complexity of restricted fragments of Decision DNNF

Authors: Calí, Andrea; Razgon, Igor;

On complexity of restricted fragments of Decision DNNF

Abstract

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).

Keywords

FOS: Computer and information sciences, Computer Science - Computational Complexity, Computational Complexity (cs.CC)

  • BIP!
    Impact byBIP!
    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
Powered by OpenAIRE graph
Found an issue? Give us feedback
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).
BIP!Citations provided by BIP!
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.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Green