Characterizing Pfaffian general graphs: minimal non-Pfaffian obstructions and the complexity of recognition

A graph is Pfaffian if it admits an orientation in which every relevant even cycle — equivalently, every $F$ -alternating cycle for a perfect matching $F$ — is oddly oriented; with such an orientation, the number of perfect matchings can be computed in polynomial time as a single Pfaffian. For bipartite graphs, the characterization problem (Pólya's permanent problem) was completely solved: Little's forbidden- $K_{3,3}$ theorem, turned into polynomial-time recognition by Robertson–Seymour–Thomas and McCuaig. For general, non-bipartite graphs the analogous problem is open. The task is to determine a complete characterization of Pfaffian general graphs at unrestricted generality: no structural characterization and no polynomial-time recognition algorithm for Pfaffian graphs is known, and whether a complete characterization can be made efficiently testable — in particular, the computational complexity of recognizing Pfaffian graphs — remains open.

Background

A perfect matching (or 1-factor) of a graph $G$ is a set of edges covering every vertex exactly once. Counting the perfect matchings of $G$ is equivalent to evaluating the permanent of an associated $(0,1)$ -matrix (the determinant-like sum with all signs taken positive) and is $\#P$ -hard in general. Kasteleyn identified a large class on which the count is nevertheless tractable. Fix a 1-factor $F$ of $G$ . A cycle is $F$ -alternating if its edges alternate between $F$ and $E(G)\setminus F$ . An orientation of $G$ is evenly (oddly) oriented on a cycle if, traversing the cycle, the number of edges directed along the traversal is even (odd). The orientation is a Pfaffian orientation if every $F$ -alternating cycle is oddly oriented; this is equivalent to the classical definition (every even cycle whose vertex deletion leaves a perfect matching is oddly oriented) and, when it exists, the perfect matchings correspond to the terms of a single Pfaffian of a signed adjacency matrix, computable in polynomial time. Every planar graph is Pfaffian; the smallest non-Pfaffian graph is $K_{3,3}$ , and the Petersen graph is another standard example.

For bipartite graphs the characterization problem goes back to Pólya (1913): when can the signs of a $(0,1)$ -matrix be switched so that its permanent becomes a determinant — exactly the question of which bipartite graphs are Pfaffian. Little (1975) characterized Pfaffian bipartite graphs by a forbidden subdivision of $K_{3,3}$ , equivalently by excluding $K_{3,3}$ as a matching minor — a containment notion under which $J$ is a matching minor of $G$ when $J$ can be obtained from a subgraph $H$ of $G$ with $G-V(H)$ having a perfect matching by repeatedly bicontracting pairs of adjacent edges that lie in a common perfect matching. A characterization in this literature counts as complete only when it yields an efficient recognition procedure; that step was achieved by Robertson, Seymour and Thomas (1999) and independently by McCuaig (2004), building on the connection between Pfaffianity and even directed circuits established by Vazirani and Yannakakis (1989) and on polynomial algorithms for the even directed circuit problem. The result is a polynomial-time algorithm for Pólya's problem on bipartite graphs.

For general graphs, Little (1973) had already given an exact linear-algebraic characterization, restated by Little and Rendl (1991) in terms of what they call intractable sets of alternating circuits. Abreu, Labbate, Romaniello and Sheehan (arXiv:1510.07553; Bulletin of the Institute of Combinatorics and its Applications 95 (2022) 70–83) give a purely graph-theoretic proof of the same equivalence. A zero-sum $F$ -set is a set $A$ of $F$ -alternating cycles such that every edge of $G$ lies in an even number of members of $A$ ; it is odd if $|A|$ is odd. The graph is simply bad if it has a 1-factor $F$ and an odd zero-sum $F$ -set $A$ all of whose members are evenly oriented in some orientation, and bad if it has a 1-factor $F$ , a zero-sum $F$ -set $A$ , and an orientation in which an odd number of members of $A$ are evenly oriented. The paper proves: non-Pfaffian $\Leftrightarrow$ bad $\Leftrightarrow$ simply bad. The equivalence is exact, but it supplies no evident efficient test — naively searching for the required set of alternating cycles and orientation takes exponential time — and the paper's introduction remarks only that the problem of characterizing Pfaffian general graphs seems much harder than the bipartite case.

Two structural frameworks organize what is known. First, matching theory decomposes a matching covered graph (a graph in which every edge lies in some perfect matching) along tight cuts (cuts whose every perfect matching uses exactly one edge of the cut) into bricks (non-bipartite indecomposable pieces) and braces (bipartite indecomposable pieces); $G$ is Pfaffian if and only if all of its bricks and braces are, so the problem lives on bricks and braces. Second, containment notions weaker than subgraph inclusion preserve Pfaffianity. A cut of a matching covered graph is separating if both of its contractions (the two subgraphs obtained by shrinking either shore of the cut to a single vertex) are matching covered; every tight cut is separating, and a matching covered graph is solid if all of its separating cuts are tight. In the framework of Lucchesi and Murty, a graph $J$ is an S-minor (separation-deletion minor) of a matching covered graph $G$ if $J$ can be obtained from $G$ by a sequence of operations, each of which either shrinks the shore of a separating cut or deletes a removable class of edges (a minimal nonempty set of edges whose deletion preserves matching coveredness); the S-minor relation preserves Pfaffianity, and every S-minimally non-Pfaffian graph is a brick or a brace. A graph is near bipartite if deleting two suitable edges leaves a bipartite matching covered graph, and Fischer and Little (2001) proved that a near-bipartite graph is non-Pfaffian if and only if it contains one of three small graphs as an S-minor: $K_{3,3}$ , the cubeplex $\Gamma_1$ , and the twinplex $\Gamma_2$ (the last two being small cubic non-Pfaffian near-bipartite graphs). Norine and Thomas (2008) showed that under the natural matching-minor relation the analogous statement fails in the strongest possible way: there are infinitely many non-Pfaffian graphs minimal with respect to matching minors, so no finite forbidden matching-minor characterization exists; they introduced a relaxed minor notion and conjectured that only finitely many minimal non-Pfaffian graphs exist under it. Subclass characterizations in this spirit are known for bipartite graphs (Little), near-bipartite graphs (Fischer–Little), solid matching covered graphs (Carvalho–Lucchesi–Murty), and, most recently, $\theta$ -free graphs — graphs with no conformal minor isomorphic to $\theta$ , the loopless cubic graph on two vertices (two vertices joined by three parallel edges); here a conformal minor is a graph $J$ such that some subgraph $H$ of $G$ with $G-V(H)$ having a perfect matching is a bisubdivision of $J$ (each edge of $J$ replaced by a path of odd length). Joshi, Raghul, Diwan and Kothari (2024) proved that a $\theta$ -free graph is Pfaffian if and only if it excludes $K_{3,3}$ and the Petersen graph as S-minors, placing recognition in polynomial time for that subclass.

Problem Statement

Characterize Pfaffian graphs at full generality. Concretely, determine a complete structural description of the non-Pfaffian graphs among all graphs with perfect matchings (equivalently, among matching covered graphs, since Pfaffianity is decided by the bricks and braces), together with the recognition procedure such a description induces. The scientific objective is a structural understanding of non-Pfaffianity at unrestricted generality: a complete structural characterization of the non-Pfaffian graphs at unrestricted generality together with the recognition procedure it induces. As in the bipartite case settled by Robertson–Seymour–Thomas and McCuaig, the characterization sought here must yield an efficient recognition procedure. Independently, determine the computational complexity of deciding whether an arbitrary given graph is Pfaffian — in particular, whether the exact bad/simply-bad criterion (the existence of a 1-factor $F$ , a zero-sum $F$ -set $A$ , and an orientation in which an odd number of members of $A$ are evenly $F$ -oriented) can be tested in polynomial time, or whether the recognition problem is co-NP-complete. Partial characterizations restricted to bipartite, near-bipartite, solid, or $\theta$ -free graphs do not answer the problem, and no reduction of generality — to bounded genus, bounded matching width, fixed connectivity, or any other subclass — is permitted.

References

M. Abreu, D. Labbate, F. Romaniello, J. Sheehan, Even orientations and Pfaffian graphs, Bulletin of the Institute of Combinatorics and its Applications 95 (2022) 70-83; preprint arXiv:1510.07553 (2015, revised 2021). https://arxiv.org/abs/1510.07553
C.H.C. Little, Kasteleyn's theorem and arbitrary graphs, Canadian Journal of Mathematics 25 (1973) 758-764, doi:10.4153/cjm-1973-077-1. https://doi.org/10.4153/cjm-1973-077-1
C.H.C. Little, A characterization of convertible (0,1)-matrices, Journal of Combinatorial Theory, Series B 18 (1975) 187-208, doi:10.1016/0095-8956(75)90048-9. https://doi.org/10.1016/0095-8956(75)90048-9
C.H.C. Little, F. Rendl, Operations preserving the pfaffian property of a graph, Journal of the Australian Mathematical Society (Series A) 50 (1991) 248-257, doi:10.1017/s1446788700032730. https://doi.org/10.1017/s1446788700032730
I. Fischer, C.H.C. Little, A characterisation of Pfaffian near bipartite graphs, Journal of Combinatorial Theory, Series B 82 (2001) 175-222, doi:10.1006/jctb.2000.2025. https://doi.org/10.1006/jctb.2000.2025
N. Robertson, P.D. Seymour, R. Thomas, Permanents, Pfaffian orientations, and even directed circuits, Annals of Mathematics (2) 150 (1999) 929-975, doi:10.2307/121059. https://doi.org/10.2307/121059
W. McCuaig, Pólya's permanent problem, The Electronic Journal of Combinatorics 11 (2004), Article R79, 83 pp., doi:10.37236/1832. https://doi.org/10.37236/1832
V.V. Vazirani, M. Yannakakis, Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs, Discrete Applied Mathematics 25 (1989) 179-190, doi:10.1016/0166-218x(89)90053-x. https://doi.org/10.1016/0166-218x(89)90053-x
S. Norine, R. Thomas, Minimally non-Pfaffian graphs, Journal of Combinatorial Theory, Series B 98 (2008) 1038-1055, doi:10.1016/j.jctb.2007.12.005. https://doi.org/10.1016/j.jctb.2007.12.005
A.C. Giannopoulou, D.M. Thilikos, S. Wiederrecht, Excluding single-crossing matching minors in bipartite graphs, arXiv:2212.09348 (2022); Proceedings of SODA 2023, doi:10.1137/1.9781611977554.ch81. https://arxiv.org/abs/2212.09348
R. Joshi, S. Raghul, A.A. Diwan, N. Kothari, $\theta$ -free matching covered graphs: characterization and consequences, arXiv:2407.05264 (2024). https://arxiv.org/abs/2407.05264
N. Kothari, O. Lee, C.L. Lucchesi, C.N. da Silva, Cubic graphs, $S$ -minors and conformal minors, arXiv:2606.04173 (2026). https://arxiv.org/abs/2606.04173
C.L. Lucchesi, U.S.R. Murty, Perfect Matchings: A Theory of Matching Covered Graphs, Algorithms and Computation in Mathematics, Springer (2024), doi:10.1007/978-3-031-47504-7. https://doi.org/10.1007/978-3-031-47504-7
M.H. de Carvalho, C.L. Lucchesi, U.S.R. Murty, A generalization of Little's theorem on Pfaffian orientations, Journal of Combinatorial Theory, Series B 102 (2012) 1241-1266, doi:10.1016/j.jctb.2012.07.004. https://doi.org/10.1016/j.jctb.2012.07.004