Optimal recognition of exact free-fermion solutions for spin models

Finding exact solutions to spin models is a fundamental problem of many-body physics. A workhorse technique for many such exact solution methods is mapping to an effective description by noninteracting particles. The paradigmatic example of this method is the exact solution for the one dimensional XY model by mapping to free-fermions via the Jordan-Wigner transformation. We connect the general problem of recognizing models which can be exactly solved in this way to the graph-theoretic problem of recognizing line graphs, which has been solved optimally. Our solution method captures an entire class of spin models which are as exactly solvable as the Kitaev honeycomb model. We give an example of a previously unsolved spin model and demonstrate its exact solution by our method. We close by showing how these techniques can be used to design new fermion-to-qubit mappings.