---
res:
  bibo_abstract:
  - 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 exactly two constraints (we call it edge CSP) 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. Using a reduction to even Δ-matroids, we then
    extend the tractability result to larger classes of Δ-matroids that we call efficiently
    coverable. It properly includes classes that were known to be tractable before,
    namely, co-independent, compact, local, linear, and binary, with the following
    caveat:We represent Δ-matroids by lists of tuples, while the last two use a representation
    by matrices. Since an n ×n matrix can represent exponentially many tuples, our
    tractability result is not strictly stronger than the known algorithm for linear
    and binary Δ-matroids.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Alexandr
      foaf_name: Kazda, Alexandr
      foaf_surname: Kazda
      foaf_workInfoHomepage: http://www.librecat.org/personId=3B32BAA8-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Vladimir
      foaf_name: Kolmogorov, Vladimir
      foaf_surname: Kolmogorov
      foaf_workInfoHomepage: http://www.librecat.org/personId=3D50B0BA-F248-11E8-B48F-1D18A9856A87
  - foaf_Person:
      foaf_givenName: Michal
      foaf_name: Rolinek, Michal
      foaf_surname: Rolinek
      foaf_workInfoHomepage: http://www.librecat.org/personId=3CB3BC06-F248-11E8-B48F-1D18A9856A87
  bibo_doi: 10.1145/3230649
  bibo_issue: '2'
  bibo_volume: 15
  dct_date: 2018^xs_gYear
  dct_identifier:
  - UT:000468036500007
  dct_language: eng
  dct_publisher: ACM@
  dct_title: Even delta-matroids and the complexity of planar boolean CSPs@
...