We give a polynomial-time algorithm for the following problem of Polya. Given an n×n 0-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 Pfaffian orientations of bipartite graphs and to the even circuit problem for directed graphs. The algorithm is based on a structural characterization of bipartite graphs that admit a Pfaffian orientation.
|Original language||English (US)|
|Number of pages||4|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - Jan 1 1997|
|Event||Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA|
Duration: May 4 1997 → May 6 1997
All Science Journal Classification (ASJC) codes