Cliquewidth and knowledge compilation

DOI10.1007/978-3-642-39071-5_25MaRDI QIDQ5326474zbMATH OpenOpenAlexFDO

Authors Igor Razgon, J. Petke

Publication date 5 August 2013

Published in Theory and Applications of Satisfiability Testing – SAT 2013 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.4081

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: In this paper we study the role of cliquewidth in succinct representation of Boolean functions. Our main statement is the following: Let $Z$ be a Boolean circuit having cliquewidth $k$. Then there is another circuit $Z^{\ast }$ computing the same function as $Z$ having treewidth at most $18k+2$ and which has at most $4|Z|$ gates where $|Z|$ is the number of gates of $Z$. In this sense, cliquewidth is not more `powerful' than treewidth for the purpose of representation of Boolean functions. We believe this is quite a surprising fact because it contrasts the situation with graphs where an upper bound on the treewidth implies an upper bound on the cliquewidth but not vice versa. We demonstrate the usefulness of the new theorem for knowledge compilation. In particular, we show that a circuit $Z$ of cliquewidth $k$ can be compiled into a Decomposable Negation Normal Form ({sc dnnf}) of size $O(9^{18k}{k}^2|Z|)$ and the same runtime. To the best of our knowledge, this is the first result on efficient knowledge compilation parameterized by cliquewidth of a Boolean circuit.

Recommendations

• Connecting knowledge compilation classes and width parameters
• Connecting width and structure in knowledge compilation
• Parameterized compilation lower bounds for restricted CNF-formulas
• On the Relationship Between Clique-Width and Treewidth
• scientific article; zbMATH DE number 2044924

Cited in

(3)

• Connecting width and structure in knowledge compilation
• On compiling CNFs into structured deterministic DNNFs
• Connecting knowledge compilation classes and width parameters

This page was built for publication: Cliquewidth and knowledge compilation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5326474)