---
_id: '10864'
abstract:
- lang: eng
  text: We prove that every congruence distributive variety has directed Jónsson terms,
    and every congruence modular variety has directed Gumm terms. The directed terms
    we construct witness every case of absorption witnessed by the original Jónsson
    or Gumm terms. This result is equivalent to a pair of claims about absorption
    for admissible preorders in congruence distributive and congruence modular varieties,
    respectively. For finite algebras, these absorption theorems have already seen
    significant applications, but until now, it was not clear if the theorems hold
    for general algebras as well. Our method also yields a novel proof of a result
    by P. Lipparini about the existence of a chain of terms (which we call Pixley
    terms) in varieties that are at the same time congruence distributive and k-permutable
    for some k.
acknowledgement: The second author was supported by National Science Center grant
  DEC-2011-/01/B/ST6/01006.
article_processing_charge: No
arxiv: 1
author:
- first_name: Alexandr
  full_name: Kazda, Alexandr
  id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87
  last_name: Kazda
- first_name: Marcin
  full_name: Kozik, Marcin
  last_name: Kozik
- first_name: Ralph
  full_name: McKenzie, Ralph
  last_name: McKenzie
- first_name: Matthew
  full_name: Moore, Matthew
  last_name: Moore
citation:
  ama: 'Kazda A, Kozik M, McKenzie R, Moore M. Absorption and directed Jónsson terms.
    In: Czelakowski J, ed. <i>Don Pigozzi on Abstract Algebraic Logic, Universal Algebra,
    and Computer Science</i>. Vol 16. OCTR. Cham: Springer Nature; 2018:203-220. doi:<a
    href="https://doi.org/10.1007/978-3-319-74772-9_7">10.1007/978-3-319-74772-9_7</a>'
  apa: 'Kazda, A., Kozik, M., McKenzie, R., &#38; Moore, M. (2018). Absorption and
    directed Jónsson terms. In J. Czelakowski (Ed.), <i>Don Pigozzi on Abstract Algebraic
    Logic, Universal Algebra, and Computer Science</i> (Vol. 16, pp. 203–220). Cham:
    Springer Nature. <a href="https://doi.org/10.1007/978-3-319-74772-9_7">https://doi.org/10.1007/978-3-319-74772-9_7</a>'
  chicago: 'Kazda, Alexandr, Marcin Kozik, Ralph McKenzie, and Matthew Moore. “Absorption
    and Directed Jónsson Terms.” In <i>Don Pigozzi on Abstract Algebraic Logic, Universal
    Algebra, and Computer Science</i>, edited by J Czelakowski, 16:203–20. OCTR. Cham:
    Springer Nature, 2018. <a href="https://doi.org/10.1007/978-3-319-74772-9_7">https://doi.org/10.1007/978-3-319-74772-9_7</a>.'
  ieee: 'A. Kazda, M. Kozik, R. McKenzie, and M. Moore, “Absorption and directed Jónsson
    terms,” in <i>Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and
    Computer Science</i>, vol. 16, J. Czelakowski, Ed. Cham: Springer Nature, 2018,
    pp. 203–220.'
  ista: 'Kazda A, Kozik M, McKenzie R, Moore M. 2018.Absorption and directed Jónsson
    terms. In: Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer
    Science. vol. 16, 203–220.'
  mla: Kazda, Alexandr, et al. “Absorption and Directed Jónsson Terms.” <i>Don Pigozzi
    on Abstract Algebraic Logic, Universal Algebra, and Computer Science</i>, edited
    by J Czelakowski, vol. 16, Springer Nature, 2018, pp. 203–20, doi:<a href="https://doi.org/10.1007/978-3-319-74772-9_7">10.1007/978-3-319-74772-9_7</a>.
  short: A. Kazda, M. Kozik, R. McKenzie, M. Moore, in:, J. Czelakowski (Ed.), Don
    Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science,
    Springer Nature, Cham, 2018, pp. 203–220.
date_created: 2022-03-18T10:30:32Z
date_published: 2018-03-21T00:00:00Z
date_updated: 2023-09-05T15:37:18Z
day: '21'
department:
- _id: VlKo
doi: 10.1007/978-3-319-74772-9_7
editor:
- first_name: J
  full_name: Czelakowski, J
  last_name: Czelakowski
external_id:
  arxiv:
  - '1502.01072'
intvolume: '        16'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1502.01072
month: '03'
oa: 1
oa_version: Preprint
page: 203-220
place: Cham
publication: Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer
  Science
publication_identifier:
  eisbn:
  - '9783319747729'
  eissn:
  - 2211-2766
  isbn:
  - '9783319747712'
  issn:
  - 2211-2758
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: OCTR
status: public
title: Absorption and directed Jónsson terms
type: book_chapter
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 16
year: '2018'
...
---
_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: 2023-09-20T11:20:26Z
day: '01'
department:
- _id: VlKo
doi: 10.1145/3230649
ec_funded: 1
external_id:
  arxiv:
  - '1602.03124'
  isi:
  - '000468036500007'
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'
...
---
_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'
...
---
_id: '1612'
abstract:
- lang: eng
  text: We prove that whenever A is a 3-conservative relational structure with only
    binary and unary relations,then the algebra of polymorphisms of A either has no
    Taylor operation (i.e.,CSP(A)is NP-complete),or it generates an SD(∧) variety
    (i.e.,CSP(A)has bounded width).
author:
- first_name: Alexandr
  full_name: Kazda, Alexandr
  id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87
  last_name: Kazda
citation:
  ama: Kazda A. CSP for binary conservative relational structures. <i>Algebra Universalis</i>.
    2016;75(1):75-84. doi:<a href="https://doi.org/10.1007/s00012-015-0358-8">10.1007/s00012-015-0358-8</a>
  apa: Kazda, A. (2016). CSP for binary conservative relational structures. <i>Algebra
    Universalis</i>. Springer. <a href="https://doi.org/10.1007/s00012-015-0358-8">https://doi.org/10.1007/s00012-015-0358-8</a>
  chicago: Kazda, Alexandr. “CSP for Binary Conservative Relational Structures.” <i>Algebra
    Universalis</i>. Springer, 2016. <a href="https://doi.org/10.1007/s00012-015-0358-8">https://doi.org/10.1007/s00012-015-0358-8</a>.
  ieee: A. Kazda, “CSP for binary conservative relational structures,” <i>Algebra
    Universalis</i>, vol. 75, no. 1. Springer, pp. 75–84, 2016.
  ista: Kazda A. 2016. CSP for binary conservative relational structures. Algebra
    Universalis. 75(1), 75–84.
  mla: Kazda, Alexandr. “CSP for Binary Conservative Relational Structures.” <i>Algebra
    Universalis</i>, vol. 75, no. 1, Springer, 2016, pp. 75–84, doi:<a href="https://doi.org/10.1007/s00012-015-0358-8">10.1007/s00012-015-0358-8</a>.
  short: A. Kazda, Algebra Universalis 75 (2016) 75–84.
date_created: 2018-12-11T11:53:01Z
date_published: 2016-02-01T00:00:00Z
date_updated: 2021-01-12T06:52:00Z
day: '01'
department:
- _id: VlKo
doi: 10.1007/s00012-015-0358-8
intvolume: '        75'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1112.1099
month: '02'
oa: 1
oa_version: Preprint
page: 75 - 84
publication: Algebra Universalis
publication_status: published
publisher: Springer
publist_id: '5554'
quality_controlled: '1'
scopus_import: 1
status: public
title: CSP for binary conservative relational structures
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 75
year: '2016'
...
---
_id: '1353'
abstract:
- lang: eng
  text: We characterize absorption in finite idempotent algebras by means of Jónsson
    absorption and cube term blockers. As an application we show that it is decidable
    whether a given subset is an absorbing subuniverse of an algebra given by the
    tables of its basic operations.
acknowledgement: 'Libor Barto and Alexandr Kazda were supported by the the Grant Agency
  of the Czech Republic, grant GACR 13-01832S. '
author:
- first_name: Libor
  full_name: Barto, Libor
  last_name: Barto
- first_name: Alexandr
  full_name: Kazda, Alexandr
  id: 3B32BAA8-F248-11E8-B48F-1D18A9856A87
  last_name: Kazda
citation:
  ama: Barto L, Kazda A. Deciding absorption. <i>International Journal of Algebra
    and Computation</i>. 2016;26(5):1033-1060. doi:<a href="https://doi.org/10.1142/S0218196716500430">10.1142/S0218196716500430</a>
  apa: Barto, L., &#38; Kazda, A. (2016). Deciding absorption. <i>International Journal
    of Algebra and Computation</i>. World Scientific Publishing. <a href="https://doi.org/10.1142/S0218196716500430">https://doi.org/10.1142/S0218196716500430</a>
  chicago: Barto, Libor, and Alexandr Kazda. “Deciding Absorption.” <i>International
    Journal of Algebra and Computation</i>. World Scientific Publishing, 2016. <a
    href="https://doi.org/10.1142/S0218196716500430">https://doi.org/10.1142/S0218196716500430</a>.
  ieee: L. Barto and A. Kazda, “Deciding absorption,” <i>International Journal of
    Algebra and Computation</i>, vol. 26, no. 5. World Scientific Publishing, pp.
    1033–1060, 2016.
  ista: Barto L, Kazda A. 2016. Deciding absorption. International Journal of Algebra
    and Computation. 26(5), 1033–1060.
  mla: Barto, Libor, and Alexandr Kazda. “Deciding Absorption.” <i>International Journal
    of Algebra and Computation</i>, vol. 26, no. 5, World Scientific Publishing, 2016,
    pp. 1033–60, doi:<a href="https://doi.org/10.1142/S0218196716500430">10.1142/S0218196716500430</a>.
  short: L. Barto, A. Kazda, International Journal of Algebra and Computation 26 (2016)
    1033–1060.
date_created: 2018-12-11T11:51:32Z
date_published: 2016-07-20T00:00:00Z
date_updated: 2021-01-12T06:50:06Z
day: '20'
department:
- _id: VlKo
doi: 10.1142/S0218196716500430
intvolume: '        26'
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1512.07009
month: '07'
oa: 1
oa_version: Preprint
page: 1033 - 1060
publication: International Journal of Algebra and Computation
publication_status: published
publisher: World Scientific Publishing
publist_id: '5893'
quality_controlled: '1'
scopus_import: 1
status: public
title: Deciding absorption
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 26
year: '2016'
...