---
_id: '6032'
abstract:
- lang: eng
  text: 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.
article_number: '22'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Alexandr
  full_name: Kazda, Alexandr
  id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87
  last_name: Kazda
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
- first_name: Michal
  full_name: Rolinek, Michal
  id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
  last_name: Rolinek
citation:
  ama: Kazda A, Kolmogorov V, Rolinek M. Even delta-matroids and the complexity of
    planar boolean CSPs. <i>ACM Transactions on Algorithms</i>. 2018;15(2). doi:<a
    href="https://doi.org/10.1145/3230649">10.1145/3230649</a>
  apa: Kazda, A., Kolmogorov, V., &#38; Rolinek, M. (2018). Even delta-matroids and
    the complexity of planar boolean CSPs. <i>ACM Transactions on Algorithms</i>.
    ACM. <a href="https://doi.org/10.1145/3230649">https://doi.org/10.1145/3230649</a>
  chicago: Kazda, Alexandr, Vladimir Kolmogorov, and Michal Rolinek. “Even Delta-Matroids
    and the Complexity of Planar Boolean CSPs.” <i>ACM Transactions on Algorithms</i>.
    ACM, 2018. <a href="https://doi.org/10.1145/3230649">https://doi.org/10.1145/3230649</a>.
  ieee: A. Kazda, V. Kolmogorov, and M. Rolinek, “Even delta-matroids and the complexity
    of planar boolean CSPs,” <i>ACM Transactions on Algorithms</i>, vol. 15, no. 2.
    ACM, 2018.
  ista: Kazda A, Kolmogorov V, Rolinek M. 2018. Even delta-matroids and the complexity
    of planar boolean CSPs. ACM Transactions on Algorithms. 15(2), 22.
  mla: Kazda, Alexandr, et al. “Even Delta-Matroids and the Complexity of Planar Boolean
    CSPs.” <i>ACM Transactions on Algorithms</i>, vol. 15, no. 2, 22, ACM, 2018, doi:<a
    href="https://doi.org/10.1145/3230649">10.1145/3230649</a>.
  short: A. Kazda, V. Kolmogorov, M. Rolinek, ACM Transactions on Algorithms 15 (2018).
date_created: 2019-02-17T22:59:25Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2025-06-04T08:46:58Z
day: '01'
department:
- _id: VlKo
doi: 10.1145/3230649
ec_funded: 1
external_id:
  arxiv:
  - '1602.03124'
  isi:
  - '000468036500007'
fulldoi: https://doi.org/10.1145/3230649
intvolume: '        15'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1602.03124
month: '12'
oa: 1
oa_version: Preprint
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication: ACM Transactions on Algorithms
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
  record:
  - id: '1192'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Even delta-matroids and the complexity of planar boolean CSPs
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 15
year: '2018'
...