Cliquewidth and knowledge compilation

DOI10.1007/978-3-642-39071-5_25zbMATH Open1390.68509arXiv1303.4081OpenAlexW1586392743MaRDI QIDQ5326474FDOQ5326474

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)

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.

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

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

Mathematics Subject Classification ID

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

Cited In (3)

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

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)