Even Delta-Matroids and the Complexity of Planar Boolean CSPs

SODA 2017, journal version in ACM Transactions on Algorithms, 2018

Authors: Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek

Matching on general graphs can be generalized in terms of matroids. This has connections to a planar version of constraint satisfaction problems. We developed a nontrivial generalization of the Blossom algorithm that solves a large class of such problems.