Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.02090 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917912265097216 |
|---|---|
| author | Nagy, Tomáš Pinsker, Michael Wrona, Michał |
| author_facet | Nagy, Tomáš Pinsker, Michael Wrona, Michał |
| contents | The path to the solution of Feder-Vardi dichotomy conjecture by Bulatov and Zhuk led through showing that more and more general algebraic conditions imply polynomial-time algorithms for the finite-domain Constraint Satisfaction Problems (CSPs) whose templates satisfy them. These investigations resulted in the discovery of the appropriate height 1 Maltsev conditions characterizing bounded strict width, bounded width, the applicability of the few-subpowers algorithm, and many others.
For problems in the range of the similar Bodirsky-Pinsker conjecture on infinite-domain CSPs, one can only find such a characterization for the notion of bounded strict width, with a proof essentially the same as in the finite case. In this paper, we provide the first non-trivial results showing that certain height 1 Maltsev conditions imply bounded width, and in consequence tractability, for a natural subclass of templates within the Bodirsky-Pinsker conjecture which includes many templates in the literature as well as templates for which no complexity classification is known. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02090 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality Nagy, Tomáš Pinsker, Michael Wrona, Michał Computational Complexity The path to the solution of Feder-Vardi dichotomy conjecture by Bulatov and Zhuk led through showing that more and more general algebraic conditions imply polynomial-time algorithms for the finite-domain Constraint Satisfaction Problems (CSPs) whose templates satisfy them. These investigations resulted in the discovery of the appropriate height 1 Maltsev conditions characterizing bounded strict width, bounded width, the applicability of the few-subpowers algorithm, and many others. For problems in the range of the similar Bodirsky-Pinsker conjecture on infinite-domain CSPs, one can only find such a characterization for the notion of bounded strict width, with a proof essentially the same as in the finite case. In this paper, we provide the first non-trivial results showing that certain height 1 Maltsev conditions imply bounded width, and in consequence tractability, for a natural subclass of templates within the Bodirsky-Pinsker conjecture which includes many templates in the literature as well as templates for which no complexity classification is known. |
| title | New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2502.02090 |