Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR21-107 | 20th July 2021 14:02

Classification of OBDD size for monotone 2-CNFs


Authors: igor razgon
Publication: 23rd July 2021 09:08
Downloads: 291


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 $\varphi$,
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 new parameter is closely related to two existing parameters:
linear maximum induced matching width (\textsc{lmim width}) and linear symmetric induced matching width
(\textsc{lsim width}). We prove that \textsc{lu-mim width} lies strictly in between these two
parameters, being dominated by \textsc{lsim width} and dominating \textsc{lmim width}.
We conclude that neither of the two existing parameters can be used instead of \textsc{lu-mim width}
to characterize the size of \textsc{obdd}s for monotone $2$-\textsc{cnf}s and this justifies introduction
of the new parameter.

ISSN 1433-8092 | Imprint