= Exclusive-or gadget in Valiant's permanent reduction
{c}
The <Exclusive-or gadget in Valiant's permanent reduction> cancels invalid <cycle covers of a directed graph> using signed <edge weights>. In the original four-<vertex> junction <matrix> $X$, only <vertices> one and four have external connections. Writing $X(R;C)$ for row and column deletions, its <permanents> satisfy
$$
\operatorname{perm}X=\operatorname{perm}X(1;1)=\operatorname{perm}X(4;4)=\operatorname{perm}X(1,4;1,4)=0,
$$
and
$$
\operatorname{perm}X(1;4)=\operatorname{perm}X(4;1)=4.
$$
Surviving weighted routes therefore enter once and leave at the opposite port. Invalid patterns have total weight zero, even when individual covers exist.<The Complexity of Computing the Permanent by Leslie G. Valiant>[junction identities (i)–(v), proof of Lemma 3.1]{ref}
Back to article page
