Papers for

computational complexity theorists

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Pfaffian graph recognition placed in randomized coRP complexity class

Pfaffian Recognition is in coRP

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}$.

Wed 21 OctComputational ComplexityDiscrete Mathematics

The gist

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.

Open → 2610.29817v1