---
_id: '1192'
abstract:
- lang: eng
  text: 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 (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. Knowing that edge CSP is tractable for even
    Δ-matroid constraints allows us to extend the tractability result to a larger
    class of Δ-matroids that includes many classes that were known to be tractable
    before, namely co-independent, compact, local and binary.
article_processing_charge: No
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. In: SIAM; 2017:307-326. doi:<a href="https://doi.org/10.1137/1.9781611974782.20">10.1137/1.9781611974782.20</a>'
  apa: 'Kazda, A., Kolmogorov, V., &#38; Rolinek, M. (2017). Even delta-matroids and
    the complexity of planar Boolean CSPs (pp. 307–326). Presented at the SODA: Symposium
    on Discrete Algorithms, Barcelona, Spain: SIAM. <a href="https://doi.org/10.1137/1.9781611974782.20">https://doi.org/10.1137/1.9781611974782.20</a>'
  chicago: Kazda, Alexandr, Vladimir Kolmogorov, and Michal Rolinek. “Even Delta-Matroids
    and the Complexity of Planar Boolean CSPs,” 307–26. SIAM, 2017. <a href="https://doi.org/10.1137/1.9781611974782.20">https://doi.org/10.1137/1.9781611974782.20</a>.
  ieee: 'A. Kazda, V. Kolmogorov, and M. Rolinek, “Even delta-matroids and the complexity
    of planar Boolean CSPs,” presented at the SODA: Symposium on Discrete Algorithms,
    Barcelona, Spain, 2017, pp. 307–326.'
  ista: 'Kazda A, Kolmogorov V, Rolinek M. 2017. Even delta-matroids and the complexity
    of planar Boolean CSPs. SODA: Symposium on Discrete Algorithms, 307–326.'
  mla: Kazda, Alexandr, et al. <i>Even Delta-Matroids and the Complexity of Planar
    Boolean CSPs</i>. SIAM, 2017, pp. 307–26, doi:<a href="https://doi.org/10.1137/1.9781611974782.20">10.1137/1.9781611974782.20</a>.
  short: A. Kazda, V. Kolmogorov, M. Rolinek, in:, SIAM, 2017, pp. 307–326.
conference:
  end_date: 2017-01019
  location: Barcelona, Spain
  name: 'SODA: Symposium on Discrete Algorithms'
  start_date: 2017-01-16
date_created: 2018-12-11T11:50:38Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-09-20T11:20:26Z
day: '01'
department:
- _id: VlKo
doi: 10.1137/1.9781611974782.20
ec_funded: 1
external_id:
  isi:
  - '000426965800020'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1602.03124
month: '01'
oa: 1
oa_version: Submitted Version
page: 307 - 326
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '616160'
  name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_identifier:
  isbn:
  - 978-161197478-2
publication_status: published
publisher: SIAM
publist_id: '6159'
quality_controlled: '1'
related_material:
  record:
  - id: '6032'
    relation: later_version
    status: public
status: public
title: Even delta-matroids and the complexity of planar Boolean CSPs
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...