Name: Classification of OBDD size for monotone 2-CNFs
Creator: Razgon, Igor
Keywords: FOS: Computer and information sciences, Ordered Binary Decision Diagrams, upper and lower bounds, 0211 other engineering and technologies, 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), Monotone 2-CNFs, 01 natural sciences, 004

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object 01 Jan 2021Embargo end date: 01 Jan 2021Publisher:arXiv

Authors: Razgon, Igor;

doi: 10.48550/arxiv.2103.09115

arXiv: http://arxiv.org/abs/2103.09115

Classification of OBDD size for monotone 2-CNFs

- Summary
- Subjects
- Related research
  (6)
- Metrics

Abstract

We introduce a new graph parameter called linear upper maximum induced matching width \textsc{lu-mim width}, denoted for a graph $G$ by $lu(G)$. We prove that the smallest size of the \textsc{obdd} for $��$, the monotone 2-\textsc{cnf} corresponding to $G$, is sandwiched between $2^{lu(G)}$ and $n^{O(lu(G))}$. The upper bound is based on a combinatorial statement that might be of an independent interest. We show that the bounds in terms of this parameter are best possible.

The presentation has been significantly improved. New material has been added: full proofs instead of sketches, examples with illustrations

Related Organizations

Leibniz Association
Germany
Birkbeck, University of London
United Kingdom
Schloss Dagstuhl – Leibniz Center for Informatics
Germany

Keywords

FOS: Computer and information sciences, Ordered Binary Decision Diagrams, upper and lower bounds, Computational Complexity (cs.CC), Monotone 2-CNFs, 004, Computer Science - Computational Complexity, Width parameters of graphs, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), ddc: ddc:004

6 Research products, page 1 of 1

On the Approximability of Splitting-SAT in 2-CNF Horn Formulas
2013IsAmongTopNSimilarDocuments
Rewriting (Dependency-)Quantified 2-CNF with Arbitrary Free Literals into Existential 2-HORN
2010IsAmongTopNSimilarDocuments
A simple parallel algorithm for finding a satisfying truth assignment to a 2-cnf formula
1988IsAmongTopNSimilarDocuments
The complete set of minimal simple graphs that support unsatisfiable 2-CNFs
2020IsAmongTopNSimilarDocuments
Compression with wildcards: All models of a Boolean 2-CNF
2012IsAmongTopNSimilarDocuments
Greedy Algorithms, Ordering of Variables, and d-degenerate Instances
2012IsAmongTopNSimilarDocuments

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