Pfaffian Recognition is in $\mathsf{coRP}$
Priyanshu Pant, Ranveer Singh
An orientation of a graph is called Pfaffian if all perfect matchings occur with the same sign in its Pfaffian expansion. A graph is Pfaffian if it admits such an orientation. Given a Pfaffian orientation, the number of perfect matchings can be computed in polynomial time. In 1963, Kasteleyn showed that every planar graph is Pfaffian. In 1989, Vazirani and Yannakakis showed that deciding whether a graph is Pfaffian is polynomial time equivalent to testing whether a given orientation is Pfaffian. For bipartite graphs, polynomial time recognition algorithms were obtained by Robertson, Seymour, and Thomas in 1999, and independently by McCuaig in 2004. Whether a deterministic polynomial time algorithm exists for general graphs remains open. In this paper, we first construct a polynomial that is identically zero if and only if a given orientation is Pfaffian, and show that this polynomial can be evaluated in polynomial time. Combined with the reduction of Vazirani and Yannakakis, this gives a randomized polynomial time algorithm for deciding whether a general graph is Pfaffian, placing the problem in $\mathsf{coRP}$. We also prove that an orientation of a matching covered graph is non-Pfaffian if and only if reversing the edges of some cut makes it strongly connected. Although deciding whether such a cut exists is NP-complete for general digraphs, our characterization yields a randomized polynomial time algorithm for matching covered graphs and deterministic polynomial time algorithms for bipartite and planar matching covered graphs.
尚无 AI 解读，展示原文摘要