Extending subcubic-time recognition and localized characterizations of Pfaffian bipartite graphs beyond the near-biwheel class $\mathcal{G}_{u,w}$

Pfaffian orientations of bipartite graphs convert the #P-complete task of counting perfect matchings (evaluating a matrix permanent) into a single determinant computation, so the complexity of recognizing Pfaffian bipartite graphs is a central algorithmic question in matching theory. The structure theorem of Robertson, Seymour and Thomas for Pfaffian braces yields an $O(n^3)$ recognition-and-construction algorithm, independently matched by McCuaig, and no improvement to this cubic bound has been published since. Feng, Zhang and Zhang identified the class $\mathcal{G}_{u,w}$ of matching-covered bipartite graphs having a vertex adjacent to all but one vertex of the opposite side, where Pfaffian-ness is characterized by local parity conditions on an explicit finite family of central 4-cycles and 6-cycles, giving $O(|E|^2)$ recognition with orientation construction. The open problem asks how far this paradigm reaches beyond $\mathcal{G}_{u,w}$: whether localized cycle-family characterizations exist for all braces, equivalently for all bipartite graphs, and whether recognition-and-construction for the full class can be made subcubic. No subcubic recognition algorithm for general bipartite graphs, and no extension of the localized $\mathcal{G}_{u,w}$ criteria beyond that class, has been published.

Background

A graph with an even number of vertices admits a perfect matching: a set of edges covering every vertex exactly once. Counting perfect matchings is a fundamental problem — for bipartite graphs it equals evaluating the permanent of the 0-1 biadjacency matrix, and in general it is #P-complete (the counting analogue of NP-completeness). A graph $G$ is called Pfaffian if it admits a Pfaffian orientation: an orientation of the edges such that every central even cycle is oddly oriented, where a cycle $C$ is central (also called nice) if $G-V(C)$ has a perfect matching, and an even cycle is oddly oriented in a given orientation if, for either direction of traversal, an odd number of its edges point along the traversal. Given a Pfaffian orientation, the number of perfect matchings can be computed in polynomial time by evaluating a single Pfaffian (a determinant-type quantity), which is why Pfaffian-ness marks the tractable regime of matching-count problems; every planar graph is Pfaffian, but non-Pfaffian graphs exist already among sparse bipartite graphs.

For bipartite graphs the structural theory is essentially complete. Little's theorem states that a bipartite graph is non-Pfaffian if and only if an even subdivision of $K_{3,3}$ (each edge replaced by an internally disjoint path containing an even number of vertices) occurs in it as a central subgraph, central meaning that deleting the subgraph's vertices leaves a graph with a perfect matching. Robertson, Seymour and Thomas proved the corresponding structure theorem for braces — a brace is a bipartite graph in which every matching of size at most two extends to a perfect matching; braces are the indecomposable building blocks obtained from bipartite matching-covered graphs (graphs in which every edge lies in some perfect matching) by repeatedly splitting along tight cuts, i.e. cuts met by every perfect matching in exactly one edge. Their theorem says a brace is Pfaffian if and only if it is isomorphic to the Heawood graph (the 14-vertex bipartite incidence graph of the Fano plane, the unique sporadic Pfaffian brace) or can be assembled from planar braces by repeated 4-sum operations glued along central 4-cycles. From this they derived an $O(n^3)$-time algorithm (Algorithm 9.7 of their paper) that, given an $n$-vertex bipartite graph, decides whether it is Pfaffian and constructs a Pfaffian orientation if so, after an $O(nm)$ decomposition into braces; McCuaig independently obtained a polynomial algorithm. This simultaneously settled Pólya's permanent problem (which 0-1 matrices admit a signing whose determinant equals the permanent), the recognition of sign-nonsingular sign patterns (sign patterns forcing every real matrix with those signs to be nonsingular), and the even directed circuit problem (deciding whether a digraph contains a directed cycle of even length), all of which are equivalent to bipartite Pfaffian recognition. Remarkably, this $O(n^3)$ bound has never been improved: papers as recent as 2023–2026 still cite the Robertson–Seymour–Thomas and McCuaig algorithms as the state of the art for the general problem, while recognizing Pfaffian-ness of nonbipartite graphs is not even known to be polynomial.

Against this background, a line of work has pursued restricted classes where recognition is both faster and more local. Lin, Zhang and Lu studied 1-extendable bipartite graphs (1-extendable meaning that every edge lies in a perfect matching) having a vertex of maximum possible degree $\Delta(G)=|V(G)|/2$; Feng, Zhang and Zhang then handled the class $\mathcal{G}_{u,w}$ of matching-covered bipartite graphs $G=(U,W)$ having a vertex $u\in U$ with $d(u)=|V(G)|/2-1$ and $uw\notin E(G)$, that is, $u$ is adjacent to every vertex of the opposite side except one distinguished vertex $w$. Such graphs are organized around biwheels: an even cycle $C$ together with two extra vertices $u$ and $w$, where $u$ is adjacent to every vertex of one color class of $C$ and $w$ to every vertex of the other class. Their two structural theorems show that (i) the global condition 'every central even cycle is oddly oriented' needs only be checked on an explicit finite family $C_u^4(G)\cup C_{u,w}^6(G)$ consisting of central 4-cycles through $u$ and central 6-cycles through $u$ and $w$, and (ii) Pfaffian-ness of a graph in $\mathcal{G}_{u,w}$ is equivalent to local parity conditions on a canonical orientation (an orientation built by an ear decomposition, i.e. growing the graph one odd-length path at a time, orienting each added path in a prescribed way), expressible as partitions of common neighbors by the parity of short oriented paths together with centrality tests on specific 4-cycles. Their Algorithm IPf then recognizes Pfaffian-ness and constructs a Pfaffian orientation for any member of $\mathcal{G}_{u,w}$ in $O(|E(G)|^2)$ time, replacing the global cycle-space machinery by local criteria. What that paper leaves untouched — and what forms the open problem — is everything outside $\mathcal{G}_{u,w}$.

Problem Statement

Decide how far the Feng–Zhang–Zhang recognition paradigm for the near-biwheel class $\mathcal{G}_{u,w}$ extends to the general bipartite setting, in both its structural and its algorithmic facet.

(1) Algorithmic facet. Does there exist an algorithm that, given an arbitrary bipartite graph $G$ with $n$ vertices and $m=|E(G)|$ edges — equivalently, after the standard $O(nm)$ decomposition into braces, an arbitrary brace — decides whether $G$ is Pfaffian and constructs a Pfaffian orientation when one exists, in $o(n^3)$ time, thereby improving the $O(n^3)$ algorithm of Robertson, Seymour and Thomas?

(2) Structural facet. Does every brace — equivalently, every matching-covered bipartite graph after decomposition — admit a localized Pfaffian characterization of the type established for $\mathcal{G}_{u,w}$: Pfaffian-ness decided by parity conditions on an explicit family of structurally restricted central cycles generalizing the families $C_u^4(G)$ and $C_{u,w}^6(G)$, where the family is specified by a fixed structural rule uniform over the class (as $C_u^4(G)$ and $C_{u,w}^6(G)$ are specified by local conditions around $u$ and $w$), has size polynomial in $n$, and can be enumerated, together with the parity tests on its members, in time polynomial in $n+m$?

The two facets share one scientific objective: certificate-style, subcubic-time recognition of Pfaffian bipartite graphs beyond the near-extremal class $\mathcal{G}_{u,w}$, analogous to the role structural localization plays in Algorithm IPf. The question concerns the full class of bipartite graphs (or braces); a localized characterization for a special family strictly between $\mathcal{G}_{u,w}$ and the general class would not resolve it.

References

1. C. H. C. Little (1975). A characterization of convertible (0,1)-matrices. Journal of Combinatorial Theory, Series B 18:187–208. DOI: 10.1016/0095-8956(75)90048-9. https://doi.org/10.1016/0095-8956(75)90048-9
2. Neil Robertson, P. D. Seymour, Robin Thomas (1999). Permanents, Pfaffian orientations, and even directed circuits. Annals of Mathematics 150:929–975. DOI: 10.2307/121059; arXiv: math/9911268. https://arxiv.org/abs/math/9911268
3. William McCuaig (2004). Pólya's Permanent Problem. The Electronic Journal of Combinatorics 11(1):#R79. DOI: 10.37236/1832. https://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r79
4. Fenggen Lin, Lianzhu Zhang, Fuliang Lu (2014). Pfaffian orientations for a type of bipartite graph. Theoretical Computer Science 527:97–101. DOI: 10.1016/j.tcs.2014.01.030. https://doi.org/10.1016/j.tcs.2014.01.030
5. Xing Feng, Lianzhu Zhang, Mingzu Zhang (2018). An $O(|E(G)|^2)$ algorithm for recognizing Pfaffian graphs of a type of bipartite graphs. Journal of Combinatorial Optimization 35(3):740–753. DOI: 10.1007/s10878-017-0207-0. https://doi.org/10.1007/s10878-017-0207-0
6. Archontia C. Giannopoulou, Meike Hatzel, Sebastian Wiederrecht (2019). Braces of Perfect Matching Width 2. arXiv: 1902.06307; journal version: The Electronic Journal of Combinatorics 32(1) (2025), DOI: 10.37236/10716. https://arxiv.org/abs/1902.06307
7. Maximilian Gorsky, Ken-ichi Kawarabayashi, Stephan Kreutzer, Sebastian Wiederrecht (2023). Packing even directed circuits quarter-integrally. arXiv: 2311.16816 (conference version STOC 2024, DOI: 10.1145/3618260.3649682). https://arxiv.org/abs/2311.16816
8. Andreas Björklund, Petteri Kaski, Jesper Nederlof (2023). Another Hamiltonian Cycle in Bipartite Pfaffian Graphs. arXiv: 2308.01574. https://arxiv.org/abs/2308.01574
9. Rohinee Joshi, Santhosh Raghul, Ajit A. Diwan, Nishad Kothari (2024). $\theta$-free matching covered graphs: characterization and consequences. arXiv: 2407.05264. https://arxiv.org/abs/2407.05264
10. Wei Li, Yao Wang, Alishba Arshad, Wuyang Sun (2025). A Characterization on Pfaffian Graphs of Cartesian Product $G\times C_{2n+1}$. Journal of Graph Theory 110(1):33–40. DOI: 10.1002/jgt.23247. https://doi.org/10.1002/jgt.23247
11. Maximilian Gorsky, Clemens Kuske (2026). On non-planar, cycle-conformal graphs. arXiv: 2602.07331. https://arxiv.org/abs/2602.07331
12. Tao Jiang, Minbo Gao, Shaowei Cai (2026). Polynomial-Time Singular Witnesses for Non-SNS Sign Patterns. arXiv: 2608.12075. https://arxiv.org/abs/2608.12075