<div class="csl-bib-body">
<div class="csl-entry">Genčiová, Ž., & Mottet, A. (2026, April 14). <i>A Preservation Theorem for Valued Structures</i> [Conference Presentation]. Durham Symposium 117 : Mathematics of Constraint Satisfaction, United Kingdom of Great Britain and Northern Ireland (the). https://doi.org/10.34726/12339</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/229098
-
dc.identifier.uri
https://doi.org/10.34726/12339
-
dc.description.abstract
The algebraic approach to constraint satisfaction problems (CSPs) has been very fruitful for classifying computational complexity. This approach is based on the interplay of polymorphisms of the template and of relations that are primitively positively definable in the template. A central result in the area is the so-called preservation theorem, due to Bodirsky and Nešetřil for templates with an oligomorphic automorphism group, which states that a relation is primitively positively definable in a relational structure A if and only if it is preserved by all polymorphisms of A.
Valued CSPs are a natural generalization of CSPs that allows to model optimization problems by replacing relations in the template by cost functions. For valued CSPs over finite-domain templates a preservation theorem was proved by Fulla and Živný, using the more general concepts of fractional polymorphisms and expressibility instead of polymorphisms and primitive positive definability. The focus of this talk is an ongoing project towards a common generalization of the result of Bodirsky and Nešetřil and of Fulla and Živný for valued CSPs over infinite-domain templates. We conjecture that given a valued structure Gamma with an oligomorphic automorphism group, a valued relation R is expressible in Gamma if and only if R is improved by all fractional polymorphisms of Gamma. If true, this result would have far-reaching consequences related to the complexity of valued CSPs and to the algebraic structure of templates for valued CSPs, e.g., existence of cores.
This is joint work with Antoine Mottet.
en
dc.description.sponsorship
FWF - Österr. Wissenschaftsfonds
-
dc.description.sponsorship
European Commission
-
dc.language.iso
en
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
valued CSPs
en
dc.subject
fractional polymorphisms
en
dc.subject
expressive power
en
dc.subject
preservation theorem
en
dc.title
A Preservation Theorem for Valued Structures
en
dc.type
Presentation
en
dc.type
Vortrag
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.identifier.doi
10.34726/12339
-
dc.contributor.affiliation
Hamburg University of Technology, Germany
-
dc.relation.grantno
ESP6949724
-
dc.relation.grantno
101071674
-
dc.type.category
Conference Presentation
-
tuw.project.title
Komplexität von Optimierung: VCSPs auf unendlichen Mengen
-
tuw.project.title
Berechnung in Polynomialzeit: Öffnen der Blackboxes für Bedingungserfüllungsprobleme
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.id
C4
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.name
Mathematical and Algorithmic Foundations
-
tuw.researchTopic.value
50
-
tuw.researchTopic.value
50
-
tuw.publication.orgunit
E104-01 - Forschungsbereich Algebra
-
tuw.author.orcid
0000-0001-8111-0671
-
dc.rights.identifier
CC BY 4.0
de
dc.rights.identifier
CC BY 4.0
en
tuw.event.name
Durham Symposium 117 : Mathematics of Constraint Satisfaction
en
dc.description.sponsorshipexternal
Deutsche Forschungsgemeinschaft
-
dc.relation.grantnoexternal
467967530
-
tuw.event.startdate
13-04-2026
-
tuw.event.enddate
17-04-2026
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.country
GB
-
tuw.event.presenter
Genčiová, Žaneta
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
5
-
wb.sciencebranch.value
95
-
item.mimetype
application/pdf
-
item.cerifentitytype
Publications
-
item.grantfulltext
open
-
item.fulltext
with Fulltext
-
item.openairetype
conference paper not in proceedings
-
item.openairecristype
http://purl.org/coar/resource_type/c_18cp
-
item.languageiso639-1
en
-
item.openaccessfulltext
Open Access
-
crisitem.author.dept
E104-01 - Forschungsbereich Algebra
-
crisitem.author.dept
Hamburg University of Technology, Germany
-
crisitem.author.orcid
0000-0001-8111-0671
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie
