= 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'$ and <edges> $v\to u_0$, $v\to u_1$, $u_0\to v'$, $u_1\to v'$. If $b=1$, also add $s\to v'$. Replace $v$ by $v'$. 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>.
Back to article page
