  We introduce a new structural graph parameter called \emph{partial matching
width}. For each (sufficiently large) integer $k \geq 1$, we introduce a class
$\mathcal{G}_k$ of graphs of treewidth at most $k$ and max-degree $7$ such that
for each $G \in \mathcal{G}_k$ and each (sufficiently large) $V \subseteq
V(G)$, the partial matching width of $V$ is $\Omega(k \log |V|)$.
  We use the above lower bound to establish a lower bound on the size of
non-deterministic read-once branching programs (NROBPs). In particular, for
each sufficiently large ineteger $k$, we introduce a class ${\bf \Phi}_k$ of
CNFs of (primal graph) treewidth at most $k$ such that for any $\varphi \in
{\bf \Phi}_k$ and any Boolean function $F \subseteq \varphi$ and such that
$|\varphi|/|F| \leq 2^{\sqrt{n}}$ (here the functions are regarded as sets of
assignments on which they are true), a NROBP implementing $F$ is of size
$n^{\Omega(k)}$. This result significantly generalises an earlier result of the
author showing a non-FPT lower bound for NROBPs representing CNFs of bounded
treewidth. Intuitively, we show that not only those CNFs but also their
arbitrary one side approximations with an exponential ratio still attain that
lower bound.
  The non-trivial aspect of this approximation is that due to a small number of
satisfying assignments for $F$, it seems difficult to establish a large
bottleneck: the whole function can `sneak' through a single rectangle
corresponding to just \emph{one} vertex of the purported bottleneck. We
overcome this problem by simultaneously exploring $\sqrt{n}$ bottlenecks and
showing that at least one of them must be large. This approach might be useful
for establishing other lower bounds for branching programs.
