Pfaffian graph recognition placed in randomized coRP complexity class
Pfaffian Recognition is in coRP
Computational ComplexityDiscrete Mathematics
Summary
Determining whether a graph has a special property called Pfaffian has been a tricky problem with uncertain complexity. The authors show that deciding if a graph has a Pfaffian orientation can be translated into a problem called polynomial identity testing, which can be solved quickly using randomization. This means there is now a randomized algorithm that can test the Pfaffian property in polynomial time for any graph. This advances our theoretical understanding of the problem’s complexity from only knowing it was in coNP.
What this means in practice
- •For graph algorithm developers: Use the new randomized polynomial-time algorithm to test Pfaffian properties in complex graph-based computations and algorithms.
- •For computational complexity theorists: Incorporate the placement of Pfaffian recognition in coRP to refine complexity classifications of related graph problems and guide future algorithm design.
A theory result. No direct application yet.
Authors
Priyanshu Pant, Ranveer Singh
Abstract
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}$.