Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs
Vazirani, Vijay V.; Yannakakis, Mihali
The following issues in computational complexity remain imprecisely understood: the striking difference in the complexities of computing the permanent and determinant of a matrix despite their similar looking formulae, the complexity of checking if a directed graph contains an even length cycle, and the complexity of computing the number of perfect matchings in a graph using Pfaffian orientations. Via polynomial time equivalences, we show inter-relationships among these issues.
computer science; technical report
Previously Published As