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 , only vertices one and four have external connections. Writing for row and column deletions, its permanents satisfyandSurviving weighted routes therefore enter once and leave at the opposite port. Invalid patterns have total weight zero, even when individual covers exist.[ref]
The Complexity of Computing the Permanent by Leslie G. Valiant. junction identities (i)–(v), proof of Lemma 3.1
Articles by others on the same topic
There are currently no matching articles.