Even Delta-Matroids and the Complexity of Planar Boolean CSPs

Alexandr Kazda, Vladimir Kolmogorov and Michal Rolínek.

In Transactions on Algorithms (TALG), 15(2), December 2018. Preliminary version appeared in ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2017.


The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec.

Furthermore, we extend the tractability result to a larger class of Δ-matroids that we call stabilizable. Our method works by calling the algorithm for even Δ-matroids polynomially many times. We then show that stabilizable Δ-matroids cover classes that were known to be tractable before, namely co-independent, compact, local and binary.


doi arXiv version