Back to Search
Start Over
Temporal Valued Constraint Satisfaction Problems
- Publication Year :
- 2024
-
Abstract
- 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.
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2409.07285
- Document Type :
- Working Paper