2026-10-08T14:24:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24131 2025-11-12T12:33:26Z ddc:004 open_access

Temporal Valued Constraint Satisfaction Problems Bodirsky, Manuel Bonnet, Édouard Semanišinová, Žaneta Constraint Satisfaction Problems valued CSPs temporal CSPs fractional polymorphisms complexity dichotomy min CSPs We study the computational complexity of the valued constraint satisfaction problem (VCSP) for every valued structure over ℚ that is preserved by all order-preserving bijections. Such VCSPs will be called temporal, in analogy to the (classical) constraint satisfaction problem: a relational structure is preserved by all order-preserving bijections if and only if all its relations have a first-order definition in (ℚ; <), and the CSPs for such structures are called temporal CSPs. Many optimization problems that have been studied intensively in the literature can be phrased as a temporal VCSP. We prove that a temporal VCSP is in P, or NP-complete. Our analysis uses the concept of fractional polymorphisms. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Édouard Bonnet and Žaneta Semanišinová 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.24 urn:nbn:de:0030-drops-241311 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.24 eng https://creativecommons.org/licenses/by/4.0/legalcode