Permanents, Pfaffian orientations, and even directed circuits (extended abstract)

Abstract

We give a polynomial-time algorithm for the following problem of P61ya. Given an n x n O-1 matrix, either find a matrix obtained from it by changing some of the 1's to -1's in such a way that the determinant of the new matrix equals the permanent of the old one, or determine that no such matrix exists. This is equivalent to finding Pfafiian orientations of bipartite graphs and to the even circuit problem for directed graphs.