License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2021.25
URN: urn:nbn:de:0030-drops-154081
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15408/
Go to the corresponding LIPIcs Volume Portal

Razgon, Igor

Classification of OBDD Size for Monotone 2-CNFs

pdf-format:
LIPIcs-IPEC-2021-25.pdf (0.7 MB)

Abstract

We introduce a new graph parameter called linear upper maximum induced matching width lu-mim width, denoted for a graph G by lu(G). We prove that the smallest size of the obdd for φ, the monotone 2-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 new parameter is closely related to two existing parameters: linear maximum induced matching width (lmim width) and linear special induced matching width (lsim width). We prove that lu-mim width lies strictly in between these two parameters, being dominated by lsim width and dominating lmim width. We conclude that neither of the two existing parameters can be used instead of lu-mim width to characterize the size of obdds for monotone 2-cnfs and this justifies introduction of the new parameter.

BibTeX - Entry

@InProceedings{razgon:LIPIcs.IPEC.2021.25,
  author =	{Razgon, Igor},
  title =	{{Classification of OBDD Size for Monotone 2-CNFs}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{25:1--25:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15408},
  URN =		{urn:nbn:de:0030-drops-154081},
  doi =		{10.4230/LIPIcs.IPEC.2021.25},
  annote =	{Keywords: Ordered Binary Decision Diagrams, Monotone 2-CNFs, Width parameters of graphs, upper and lower bounds}
}

Keywords: Ordered Binary Decision Diagrams, Monotone 2-CNFs, Width parameters of graphs, upper and lower bounds
Collection: 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Issue Date: 2021
Date of publication: 22.11.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI