Pfaffian Recognition is in coRP

Overview & Synopsis

A graph is called Pfaffian if it admits a Pfaffian orientation. The Pfaffian recognition problem asks whether a given graph is Pfaffian. In 1989, Vazirani and Yannakakis showed that this problem is polynomial time equivalent to testing whether a prescribed orientation is Pfaffian, and that the problem belongs to $\mathsf{coNP}$. The complexity of the problem for general graphs has remained open since then. For bipartite graphs, polynomial time recognition algorithms were obtained by Robertson, Seymour, and Thomas in 1999, and independently by McCuaig in 2004. We show that testing whether a given orientation is Pfaffian can be reduced to polynomial identity testing. This gives a randomized polynomial time algorithm for Pfaffian recognition on general graphs, placing the problem in $\mathsf{coRP}$.