 Binary path-counting gadget

A binary path-counting gadget constructs a directed acyclic graph with exactly $w$ directed paths from entrance $s$ to exit $t$, using $O(\log (w+1))$ vertices for a nonnegative integer $w$.

For $w>0$, read its binary expansion after the leading one. Begin with one edge $s\to v$. For each following bit $b$, add fresh vertices $u_0,u_1,v^{\prime }$ and edges $v\to u_0$, $v\to u_1$, $u_0\to v^{\prime }$, $u_1\to v^{\prime }$. If $b=1$, also add $s\to v^{\prime }$. Replace $v$ by $v^{\prime }$. The path count changes from $q$ to $2q+b$. Finally add $v\to t$. For $w=5$, the bits $101$ give counts $1,2,5$. For $w=0$, leave $s,t$ disconnected.

To replace a weighted edge $x\to y$ inside a cycle cover of a directed graph, identify $s=x,t=y$ and give each fresh internal vertex a unit-weight self-loop. If the replacement is unused, all fresh vertices use their self-loops, in one way. If it is used, the selected internal edges form one $x$-to-$y$ path, giving $w$ possibilities; all unused vertices use their self-loops. The internal graph is acyclic apart from these self-loops, so there are no other internal directed cycles. Thus the substitution preserves the weighted permanent of a matrix.