Document Open Access Logo

Classification of OBDD Size for Monotone 2-CNFs

Author Igor Razgon

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.25.pdf
  • Filesize: 0.65 MB
  • 15 pages

Document Identifiers

Author Details

Igor Razgon
  • Department of Computer Science and Information Systems, Birkbeck University of London, UK

Acknowledgements

I would like to thank the anonymous reviewers for their detailed and insightful comments that helped me to significantly improve the quality of the paper.

Cite As Get BibTex

Igor Razgon. Classification of OBDD Size for Monotone 2-CNFs. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.IPEC.2021.25

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph theory
  • Theory of computation → Circuit complexity
Keywords
  • Ordered Binary Decision Diagrams
  • Monotone 2-CNFs
  • Width parameters of graphs
  • upper and lower bounds

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Antoine Amarilli, Florent Capelli, Mikaël Monet, and Pierre Senellart. Connecting knowledge compilation classes and width parameters. Theory Comput. Syst., 64(5):861-914, 2020. Google Scholar
  2. Adnan Darwiche. Decomposable negation normal form. J. ACM, 48(4):608-647, 2001. Google Scholar
  3. Andrea Ferrara, Guoqiang Pan, and Moshe Y. Vardi. Treewidth in verification: Local vs. global. In Logic for Programming, Artificial Intelligence, and Reasoning, 12th International Conference (LPAR), pages 489-503, 2005. Google Scholar
  4. Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. Mim-width III. graph powers and generalized distance domination problems. Theor. Comput. Sci., 796:216-236, 2019. Google Scholar
  5. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Mim-width i. induced path problems. Discret. Appl. Math., 278:153-168, 2020. Google Scholar
  6. Lars Jaffke, O-joung Kwon, and Jan Arne Telle. Mim-width II. the feedback vertex set problem. Algorithmica, 82(1):118-145, 2020. Google Scholar
  7. Stasys Jukna. Extremal Combinatorics: With Applications in Computer Science. Springer, 2011. Google Scholar
  8. Dong Yeap Kang, O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle. A width parameter useful for chordal and co-comparability graphs. Theor. Comput. Sci., 704:1-17, 2017. Google Scholar
  9. Stefan Mengel. Lower bounds on the mim-width of some graph classes. Discret. Appl. Math., 248:28-32, 2018. Google Scholar
  10. Igor Razgon. On the read-once property of branching programs and cnfs of bounded treewidth. Algorithmica, 75(2):277-294, 2016. Google Scholar
  11. Igor Razgon. On oblivious branching programs with bounded repetition that cannot efficiently compute cnfs of bounded treewidth. Theory Comput. Syst., 61(3):755-776, 2017. Google Scholar
  12. Sigve Hortemo Sæther, Jan Arne Telle, and Martin Vatshelle. Solving #SAT and MAXSAT by dynamic programming. J. Artif. Intell. Res., 54:59-82, 2015. Google Scholar
  13. Martin Vatshelle. New width parameters of graphs. PhD thesis, Department of Informatics, University of Bergen, 2012. Google Scholar
  14. Ingo Wegener. Branching Programs and Binary Decision Diagrams. SIAM Monographs on Discrete Mathematics and applications, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact