Even Delta-Matroids and the Complexity of Planar Boolean CSPs

The main result of this article is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in...