Permanents, Pfaffian orientations, and even directed circuits

Given a 0-1 square matrix A, when can some of the 1's be changed to -1's in such a way that the permanent of A equals the determinant of the modified matrix? When does a real square matrix have the property that every real ma trix with the same sign pattern (that is, the corresponding entries either have the same sign or are both zero) is nonsingular? When is a hypergraph w ith n vertices and n hyperedges minimally nonbipartite? When does a biparti te graph have a "Pfaffian orientation"? Given a digraph, does it have no di rected circuit of even length? Given a digraph, does it have a subdivision with no even directed circuit? It is known that all of the above problems are equivalent. We prove a struc tural characterization of the feasible instances, which implies a polynomia l-time algorithm to solve all of the above problems. The structural charact erization says, roughly speaking, that a bipartite graph has a Pfaffian ori entation if and only if it can be obtained by piecing together (in a specif ied way) planar bipartite graphs and one sporadic nonplanar bipartite graph .