DC Field
Value
Language
dc.contributor.author
Semanišinová, Žaneta
-
dc.contributor.author
Bodirsky, Manuel
-
dc.contributor.author
Bonnet, Édouard
-
dc.date.accessioned
2026-07-29T12:06:27Z
-
dc.date.available
2026-01-09T14:48:20Z
-
dc.date.available
2026-07-29T12:06:27Z
-
dc.date.issued
2025-12-18
-
dc.identifier.citation
<div class="csl-bib-body"> <div class="csl-entry">Semanišinová, Ž., Bodirsky, M., &#38; Bonnet, É. (2025, December 18). <i>Temporal Valued Constraint Satisfaction Problems</i> [Conference Presentation]. Homogeneous Structures: Model Theory meets Universal Algebra (MFO Workshop 2551), Oberwolfach, Germany. https://doi.org/10.34726/12452</div> </div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/223918
-
dc.identifier.uri
https://doi.org/10.34726/12452
-
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.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
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.rights.license
Urheberrechtsschutz
de
dc.rights.license
In Copyright
en
dc.identifier.doi
10.34726/12452
-
dc.contributor.affiliation
Technische Universität Dresden, Germany
-
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.author.orcid
0000-0001-8228-3611
-
tuw.author.orcid
0000-0002-1653-5822
-
dc.rights.identifier
Urheberrechtsschutz
de
dc.rights.identifier
In Copyright
en
tuw.event.name
Homogeneous Structures: Model Theory meets Universal Algebra (MFO Workshop 2551)
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
Semanišinová, Žaneta
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
25
-
wb.sciencebranch.value
75
-
item.languageiso639-1
en
-
item.openairecristype
http://purl.org/coar/resource_type/c_18cp
-
item.openaccessfulltext
Open Access
-
item.mimetype
application/pdf
-
item.openairetype
conference paper not in proceedings
-
item.fulltext
with Fulltext
-
item.grantfulltext
open
-
item.cerifentitytype
Publications
-
crisitem.project.funder
FWF - Österr. Wissenschaftsfonds
-
crisitem.project.grantno
ESP6949724
-
crisitem.author.dept
E104-01 - Forschungsbereich Algebra
-
crisitem.author.dept
Technische Universität Dresden, Germany
-
crisitem.author.orcid
0000-0001-8111-0671
-
crisitem.author.orcid
0000-0001-8228-3611
-
crisitem.author.orcid
0000-0002-1653-5822
-
crisitem.author.parentorg
E104 - Institut für Diskrete Mathematik und Geometrie
-
Appears in Collections:
Presentation
Thumbnail
Fulltext (Version of Record (published version))
Adobe PDF
(364.17 kB)
Slides
Open Access In Copyright
Show simple item record
Version History
Version Item submitted by Date Summary
2 20.500.12708/223918 Achleitner, Michaela 2026-07-29 14:04:29.16 Generation of DOI
1 20.500.12708/223918.1 Genciova, Zaneta 2026-01-09 15:48:20.0
Selected version

Page view(s)

5
checked on Jul 29, 2026

Google ScholarTM

Check