### Abstract

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) |
---|---|

Pages (from-to) | 402-405 |

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

- Software

## Fingerprint Dive into the research topics of 'Permanents, Pfaffian orientations, and even directed circuits'. Together they form a unique fingerprint.

## Cite this

McCuaig, W., Robertson, N., Seymour, P. D., & Thomas, R. (1997). Permanents, Pfaffian orientations, and even directed circuits.

*Conference Proceedings of the Annual ACM Symposium on Theory of Computing*, 402-405.