A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs

A matching covered graph is a nontrivial connected graph in which every edge is in some perfect matching. A single ear of a connected graph G is a path P of odd length in G whose internal vertices, if any, have degree two in G. Let G – P denote the graph obtained from G by deleting the edges and internal vertices of G. A double ear of G is a pair ( R 1 , R 2 ) of vertex-disjoint single ears of G. A matching covered graph G is near-bipartite if it is non-bipartite and there is a double ear ( R 1 , R 2 ) such that G – R 1 – R 2 is matching covered and bipartite, but G – R i is not matching covered, for i = 1 , 2 . In 2000, C. Little and I. Fischer characterized Pfaffian near-bipartite graphs in terms of forbidden subgraphs [Little, C.H.C. and I. Fischer, A characterisation of Pfaffian near bipartite graphs, J. Combin. Theory Ser. B 82 (2001), pp. 175–222]. However, their characterization does not imply a polynomial time algorithm to determine whether a near-bipartite graph is Pfaffian. In this report, we give such an algorithm. Our algorithm is based in an Inclusion-Exclusion principle and uses as a subroutine an algorithm by McCuaig [McCuaig, W., Pólyaʹs permanent problem, The Electronic J. of Combin. 11 (2004)] and, independently, by Robertson, Seymour and Thomas [Robertson, N., P.D. Seymour and R. Thomas, Permanents, Pfaffian orientations and even directed circuits, Ann. of Math. (2) 150 (1999), pp. 929–975] that determines whether a bipartite graph is Pfaffian.