Cutting Barnette graphs perfectly is hard

A perfect matching cut is a perfect matching that is also a cutset, or equivalently, a perfect matching containing an even number of edges on every cycle. The corresponding algorithmic problem, Perfect Matching Cut, is known to be NP-complete in subcubic bipartite graphs Le & Telle, TCS '22, but its complexity was open in planar graphs and cubic graphs. We settle both questions simultaneously by showing that Perfect Matching Cut is NP-complete in 3-connected cubic bipartite planar graphs or Barnette graphs. Prior to our work, among problems whose input is solely an undirected graph, only Distance-2 4-Coloring was known to be NP-complete in Barnette graphs. Notably, Hamiltonian Cycle would only join this private club if Barnette's conjecture were refuted. Funding This work was supported by the ANR projects TWIN-WIDTH (ANR-21-CE48-0014) and Digraphs (ANR-19-CE48-0013). Acknowledgements We are much indebted to Carl Feghali for introducing us to the topic of (perfect) matching cuts, and for presenting open problems to us that led to the current paper. We also wish to thank him and Kristóf Huszár for helpful discussions at an early stage of the project.