zbMATH — the first resource for mathematics

Permanents, Pfaffian orientations, and even directed circuits. (English) Zbl 0947.05066
The paper deals with the following problem asked by Pólya in 1913: Given a 0-1 matrix \(A\), is there a matrix \(B\) obtained from \(A\) by changing signs of some \(1\)’s to \(-1\)’s so that the permanent of \(A\) equals the determinant of \(B\)? Such \(B\) is called a Pólya matrix for \(A\). The paper provides a structural characterization of matrices for which Pólya’s matrices exist. This characterization is used to construct a polynomial-time algorithm to decide whether a matrix has its Pólya matrix.

05C75 Structural characterization of families of graphs
15A15 Determinants, permanents, traces, other special matrix functions
05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
05C20 Directed graphs (digraphs), tournaments
Full Text: DOI Link EuDML arXiv