The Pfaffian recognition problem beyond planar, bipartite, and near-bipartite graphs (Problem 42 of Kothari–de Carvalho–Lucchesi–Little)

A matching covered graph is Pfaffian if it admits an orientation in which every conformal cycle is oddly oriented; for such graphs the number of perfect matchings is computable in polynomial time by a determinant (the Fisher–Kasteleyn–Temperley method). Kasteleyn proved all planar graphs Pfaffian in 1963, and the bipartite (Little; Robertson–Seymour–Thomas; McCuaig) and near-bipartite (Fischer–Little; Miranda–Lucchesi) cases are characterized with polynomial-time recognition. This problem records Problem 42 of Kothari, de Carvalho, Lucchesi and Little (Electron. J. Combin. 2020): characterize Pfaffian nonplanar matching covered graphs, and determine whether deciding Pfaffianness is in NP or in P.

Background

A perfect matching of a graph is a set of edges covering every vertex exactly once. A connected graph is matching covered if every edge lies in some perfect matching. Lovász proved that every matching covered graph decomposes uniquely along tight cuts — a cut is tight if every perfect matching has exactly one edge in it — into indecomposable pieces: braces (the bipartite pieces) and bricks (the nonbipartite pieces, which are 3-connected and bicritical, i.e., deleting any two vertices leaves a graph with a perfect matching). This tight cut decomposition is computable in polynomial time.

A cycle $C$ of a matching covered graph $G$ is conformal if $G - V(C)$ has a perfect matching; a subgraph is conformal if its vertex-deletion leaves a matchable graph. Bisubdividing an edge means subdividing it by an even number of vertices; a conformal minor of $G$ is a cubic matching covered graph $J$ such that $G$ has a conformal subgraph that is a bisubdivision of $J$ ($G$ is then called $J$-based; otherwise $J$-free). An orientation of $G$ is Pfaffian if every conformal cycle is oddly oriented, i.e., has an odd number of edges oriented in each direction of traversal. A graph is Pfaffian if it admits a Pfaffian orientation; Kasteleyn (1963) proved every planar graph is Pfaffian, and the determinant of the oriented (skew-symmetric) adjacency matrix of a Pfaffian orientation equals, up to sign, the square of the number of perfect matchings, yielding polynomial-time counting — the Fisher–Kasteleyn–Temperley (FKT) method. This makes characterizing the Pfaffian graphs one of the central open problems of matching theory, going back to Kasteleyn's program and Pólya's permanent problem.

Three cases are settled. Little (1975) proved that a bipartite matching covered graph is Pfaffian if and only if it is $K_{3,3}$-free (i.e., contains no conformal minor isomorphic to $K_{3,3}$); Robertson, Seymour and Thomas (1999) and, independently, McCuaig (2004) turned this into a structural decomposition of Pfaffian bipartite graphs (solving Pólya's permanent problem) and a polynomial-time recognition algorithm. Little and Rendl (1991) proved that a matching covered graph is Pfaffian if and only if each of its bricks and braces is Pfaffian, so the problem reduces to bricks and braces. A brick is near-bipartite if some pair of edges (a removable doubleton) can be deleted to leave a bipartite matching covered graph (e.g., $K_4$, the triangular prism $\overline{C_6}$, and the staircases); Fischer and Little (2001) characterized Pfaffian near-bipartite matching covered graphs by seven forbidden cubic conformal minors ($K_{3,3}$, Cubeplex, Twinplex, and four variants), and Miranda and Lucchesi (2008) gave a polynomial-time recognition algorithm for near-bipartite graphs.

What remains is the non-near-bipartite, nonplanar world. The smallest non-Pfaffian graph is $K_{3,3}$; the Petersen graph is a non-Pfaffian brick that is not near-bipartite, while the Heawood graph shows a nonplanar graph can be Pfaffian. On the complexity side, Vazirani and Yannakakis (1989) proved that deciding whether a given matching covered graph is Pfaffian — and deciding whether a given orientation is Pfaffian, an equivalent problem first established by them and re-established via ear decompositions by de Carvalho, Lucchesi and Murty (2005) — lies in co-NP; membership in NP and in P is not known. The source paper of this problem, a 2020 study of essentially 4-edge-connected cubic bricks (2-edge-connected cubic graphs whose only 3-edge-cuts are trivial; a 3-edge-cut is trivial when one of the two components left by removing it is a single vertex) and their $b$-invariant edges (removable edges — those whose deletion leaves a matching covered graph — whose deletion leaves exactly one brick in the tight cut decomposition), states the problem in this context as its Problem 42, reducing (as its Problem 45) to: characterize Pfaffian nonplanar non-near-bipartite bricks.

Problem Statement

As stated in Problem 42 of Kothari–de Carvalho–Lucchesi–Little (2020): characterize Pfaffian nonplanar matching covered graphs — i.e., give a structural description (for instance by a family of forbidden conformal minors, or of matching minors — the matching-preserving analogue of graph minors, built from conformal subgraphs and contractions of edges that lie in a perfect matching — or by an explicit decomposition) of those nonplanar matching covered graphs that admit a Pfaffian orientation — and determine the computational complexity of deciding whether a given graph is Pfaffian: is this decision problem in NP; is it in P? By Little–Rendl's theorem (a matching covered graph is Pfaffian if and only if each of its bricks and braces is Pfaffian) and the settled bipartite (Robertson–Seymour–Thomas; McCuaig) and near-bipartite (Fischer–Little; Miranda–Lucchesi) cases, the structural part is equivalent to Problem 45 of the same paper: characterize Pfaffian nonplanar non-near-bipartite bricks. The complexity part must be answered at full generality — for arbitrary matching covered graphs (equivalently, via the polynomial-time tight cut decomposition and the settled brace case, for arbitrary bricks), not merely for a subfamily; it is currently known only that the problem lies in co-NP (Vazirani–Yannakakis). A complete answer requires both parts: the structural part (a characterization of Pfaffian nonplanar non-near-bipartite bricks) and the complexity part (an explicit determination of the complexity class of the decision problem at full generality); the structural part answers the complexity part only when it is accompanied by a proof that it yields a polynomial-time recognition procedure.

References

1. Nishad Kothari, Marcelo H. de Carvalho, Cláudio L. Lucchesi, Charles H. C. Little, 'On Essentially 4-Edge-Connected Cubic Bricks', Electronic Journal of Combinatorics 27(1) (2020), DOI 10.37236/8594, https://doi.org/10.37236/8594 (arXiv:1803.08713, https://arxiv.org/abs/1803.08713)
2. P. W. Kasteleyn, 'Dimer Statistics and Phase Transitions', Journal of Mathematical Physics 4 (1963) 287–293, DOI 10.1063/1.1703953, https://doi.org/10.1063/1.1703953
3. 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
4. C. H. C. Little, F. Rendl, 'Operations preserving the pfaffian property of a graph', Journal of the Australian Mathematical Society (Series A) 50 (1991), DOI 10.1017/S1446788700032730, https://doi.org/10.1017/S1446788700032730
5. Neil Robertson, P. D. Seymour, Robin 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 (arXiv:math/9911268, https://arxiv.org/abs/math/9911268)
6. W. McCuaig, 'Pólya's Permanent Problem', The Electronic Journal of Combinatorics 11 (2004), DOI 10.37236/1832, https://doi.org/10.37236/1832
7. Ilse 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
8. A. A. A. Miranda, C. L. Lucchesi, 'A Polynomial Time Algorithm for Recognizing Near-Bipartite Pfaffian Graphs', Electronic Notes in Discrete Mathematics 30 (2008) 171–176, DOI 10.1016/j.endm.2008.01.030, https://doi.org/10.1016/j.endm.2008.01.030
9. 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
10. Serguei Norine, Robin 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
11. 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
12. N. Kothari, U. S. R. Murty, '$K_4$-free and $\overline{C_6}$-free planar matching covered graphs', Journal of Graph Theory 82(1) (2016) 5–32, DOI 10.1002/jgt.21882, https://doi.org/10.1002/jgt.21882
13. C. L. Lucchesi, M. de Carvalho, N. Kothari, U. S. R. Murty, 'On Two Unsolved Problems Concerning Matching Covered Graphs', SIAM Journal on Discrete Mathematics 32 (2018) 1478–1504, DOI 10.1137/17M1138704, https://doi.org/10.1137/17M1138704
14. Rohinee Joshi, Santhosh Raghul, Ajit A. Diwan, Nishad Kothari, '$\theta$-free matching covered graphs: characterization and consequences', arXiv:2407.05264 (2024), https://arxiv.org/abs/2407.05264
15. Nishad Kothari, Orlando Lee, Cláudio L. Lucchesi, Cândida Nunes da Silva, 'Cubic graphs, $S$-minors and conformal minors', arXiv:2606.04173 (2026), https://arxiv.org/abs/2606.04173
16. Cláudio 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://link.springer.com/book/10.1007/978-3-031-47504-7
17. Fuliang Lu, Xing Feng, Yan Wang, '$b$-Invariant Edges in Essentially 4-Edge-Connected Near-Bipartite Cubic Bricks', The Electronic Journal of Combinatorics 27(1) (2020), DOI 10.37236/8945, https://doi.org/10.37236/8945 (arXiv:1905.07301, https://arxiv.org/abs/1905.07301)
18. Yaxian Zhang, Fuliang Lu, Heping Zhang, 'b-Invariant Edges in Near-Bipartite Bricks', Journal of Graph Theory (2026), DOI 10.1002/jgt.70078, https://doi.org/10.1002/jgt.70078
19. Archontia C. Giannopoulou, Dimitrios M. Thilikos, Sebastian Wiederrecht, 'Excluding Single-Crossing Matching Minors in Bipartite Graphs', Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023), DOI 10.1137/1.9781611977554.ch81, https://doi.org/10.1137/1.9781611977554.ch81
20. Archontia C. Giannopoulou, Sebastian Wiederrecht, 'A Flat Wall Theorem for Matching Minors in Bipartite Graphs', Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), DOI 10.1145/3618260.3649774, https://doi.org/10.1145/3618260.3649774
21. Maximilian Gorsky, Clemens Kuske, 'On non-planar, cycle-conformal graphs', arXiv:2602.07331 (2026), https://arxiv.org/abs/2602.07331
22. M. H. de Carvalho, C. L. Lucchesi, U. S. R. Murty, 'On the number of dissimilar Pfaffian orientations of graphs', RAIRO – Theoretical Informatics and Applications 39 (2005) 93–113, DOI 10.1051/ita:2005005, https://doi.org/10.1051/ita:2005005