Temporal Valued Constraint Satisfaction Problems
<|reference_start|>Temporal Valued Constraint Satisfaction Problems: We study the complexity of the valued constraint satisfaction problem (VCSP) for every valued structure with the domain ${\mathbb Q}$ 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 $({\mathbb Q};<)$, 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 with a given automorphism group.<|reference_end|>
@article{bodirsky2024temporal,
    title={Temporal Valued Constraint Satisfaction Problems},
    author={Manuel Bodirsky, 'Edouard Bonnet, v{Z}aneta Semaniv{s}inov'a},
    journal={arXiv preprint arXiv:2409.07285},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.07285},
    primaryClass={math.LO cs.CC}
}