Reducibility concepts are fundamental in complexity theory.
Usually, they are defined as follows: A problem P is reducible
to a problem S if P can be computed using a program or device
for S as a subroutine. However, in the case of such restricted
models as ... more >>>

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 ... more >>>