<div class="csl-bib-body">
<div class="csl-entry">Semanisinova, Z. (2025, December 18). <i>Temporal Valued Constraint Satisfaction Problems</i> [Conference Presentation]. MFO Workshop 2551 Homogeneous Structures: Model Theory meets Universal Algebra, Oberwolfach, Germany. http://hdl.handle.net/20.500.12708/223918</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/223918
-
dc.description.abstract
We study the computational complexity of the valued constraint satisfaction problem (VCSP) for all valued structures over the domain Q preserved by all order-preserving bijections. Such VCSPs will be called temporal, in analogy to temporal constraint satisfaction problems. Many optimization problems that have been studied intensively in the literature can be phrased as a temporal VCSP, for example, the min correlation clustering problem or the minimum feedback arc set problem. We present a P vs. NP-complete dichotomy for temporal VCSPs, based on the concepts of fractional polymorphisms and expressibility in valued structures. This is the first dichotomy result for VCSPs over infinite domains which is complete in the sense that it treats all valued structures that contain a given automorphism group. This is joint work with Manuel Bodirsky and Édouard Bonnet.
en
dc.description.sponsorship
FWF - Österr. Wissenschaftsfonds
-
dc.language.iso
en
-
dc.subject
Constraint Satisfaction Problems
en
dc.subject
valued CSPs
en
dc.subject
temporal CSPs
en
dc.subject
fractional polymorphisms
en
dc.subject
complexity dichotomy
en
dc.subject
min CSPs
en
dc.title
Temporal Valued Constraint Satisfaction Problems
en
dc.type
Presentation
en
dc.type
Vortrag
de
dc.relation.grantno
ESP6949724
-
dc.type.category
Conference Presentation
-
tuw.project.title
Komplexität von Optimierung: VCSPs auf unendlichen Mengen
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.id
A3
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.name
Fundamental Mathematics Research
-
tuw.researchTopic.value
90
-
tuw.researchTopic.value
10
-
tuw.publication.orgunit
E104-01 - Forschungsbereich Algebra
-
tuw.author.orcid
0000-0001-8111-0671
-
tuw.event.name
MFO Workshop 2551 Homogeneous Structures: Model Theory meets Universal Algebra
en
dc.description.sponsorshipexternal
European Research Council
-
dc.description.sponsorshipexternal
Deutsche Forschungsgemeinschaft
-
dc.relation.grantnoexternal
ERC Synergy Grant 101071674
-
dc.relation.grantnoexternal
467967530
-
tuw.event.startdate
14-12-2025
-
tuw.event.enddate
19-12-2025
-
tuw.event.online
Hybrid
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Oberwolfach
-
tuw.event.country
DE
-
tuw.event.institution
Mathematisches Forschungsinstitut Oberwolfach
-
tuw.event.presenter
Semanisinova, Zaneta
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
25
-
wb.sciencebranch.value
75
-
item.openairetype
conference paper not in proceedings
-
item.openairecristype
http://purl.org/coar/resource_type/c_18cp
-
item.cerifentitytype
Publications
-
item.languageiso639-1
en
-
item.grantfulltext
restricted
-
item.fulltext
no Fulltext
-
crisitem.author.dept
E104-01 - Forschungsbereich Algebra
-
crisitem.author.orcid
0000-0001-8111-0671
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie
