@article{6032,
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.},
author = {Kazda, Alexandr and Kolmogorov, Vladimir and Rolinek, Michal},
journal = {ACM Transactions on Algorithms},
number = {2},
publisher = {ACM},
title = {{Even delta-matroids and the complexity of planar boolean CSPs}},
doi = {10.1145/3230649},
volume = {15},
year = {2018},
}
@inbook{10864,
abstract = {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.},
author = {Kazda, Alexandr and Kozik, Marcin and McKenzie, Ralph and Moore, Matthew},
booktitle = {Don Pigozzi on Abstract Algebraic Logic, Universal Algebra, and Computer Science},
editor = {Czelakowski, J},
isbn = {9783319747712},
issn = {2211-2758},
pages = {203--220},
publisher = {Springer Nature},
title = {{Absorption and directed Jónsson terms}},
doi = {10.1007/978-3-319-74772-9_7},
volume = {16},
year = {2018},
}
@inproceedings{1192,
abstract = {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.},
author = {Kazda, Alexandr and Kolmogorov, Vladimir and Rolinek, Michal},
isbn = {978-161197478-2},
location = {Barcelona, Spain},
pages = {307 -- 326},
publisher = {SIAM},
title = {{Even delta-matroids and the complexity of planar Boolean CSPs}},
doi = {10.1137/1.9781611974782.20},
year = {2017},
}
@article{1612,
abstract = {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 = {Kazda, Alexandr},
journal = {Algebra Universalis},
number = {1},
pages = {75 -- 84},
publisher = {Springer},
title = {{CSP for binary conservative relational structures}},
doi = {10.1007/s00012-015-0358-8},
volume = {75},
year = {2016},
}
@article{1353,
abstract = {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.},
author = {Barto, Libor and Kazda, Alexandr},
journal = {International Journal of Algebra and Computation},
number = {5},
pages = {1033 -- 1060},
publisher = {World Scientific Publishing},
title = {{Deciding absorption}},
doi = {10.1142/S0218196716500430},
volume = {26},
year = {2016},
}