Temporal Valued Constraint Satisfaction Problems

VCSPs on infinite domains have been studied in [39, 37, 40]. However, the valued structures considered in these articles typically do not have an oligomorphic automorphism group, a property that is essential for applying our techniques for classifying the complexity of VCSPs. The foundations of the theory for VCSPs of valued structures with an oligomorphic automorphism group were laid in [13] with the motivation to study resilience problems from database theory. Concrete subclasses of temporal VCSPs have been studied in the context of min-CSPs from the parameterized complexity perspective: the complexity of equality min-CSPs has been classified in [35] and parameterized complexity of min-CSPs over the Point Algebra has been classified in [33]. The authors mention a classification of first-order generalizations of the Point Algebra as a natural continuation of their research [33, Section 5]. The present paper contains a classification of VCSPs over all temporal structures and thus provides the foundations for classifying the parameterized complexity of min-CSPs for such structures, including algebraic techniques that we expect to be useful in this context as well.

The article is organized as follows. Section 2 contains preliminaries on VCSPs in general, with some notation and properties specific to temporal VCSPs. Section 3 contains several new facts about VCSPs that have been used in the classification. Section 4 contains the classification of equality VCSPs, that is, VCSPs of valued structures with an automorphism group equal to the full symmetric group; on the one hand, this serves as a warm-up, on the other hand it is a building block for the general case. Section 5 contains the full classification of temporal VCSPs, which is the main contribution of the paper.

Let $A$ be a set and let $k\in \mathbb{N}$. A valued relation of arity $k$ over $A$ is a function $R:A^k\to \mathbb{Q}\cup \{\mathrm{\infty }\}$. We write ${ℛ}_A^{(k)}$ for the set of all valued relations over $A$ of arity $k$, and define

A valued relation is called finite-valued if it takes values only in $\mathbb{Q}$.

Usual relations $R\subseteq A^k$ will also be called crisp relations. A valued relation $R\in {ℛ}_A^{(k)}$ that only takes values from $\{0,\mathrm{\infty }\}$ will be identified with the crisp relation $\{t\in A^k\mid R(t)=0\}.$ A valued relation $R\in {ℛ}_A^{(k)}$ is called essentially crisp if there exists $a\in \mathbb{Q}$ such that $R(t)\in \{a,\mathrm{\infty }\}$ for every $t\in A^k$. For $R\in {ℛ}_A^{(k)}$ the feasibility relation of $R$ is defined as For $S\subseteq A^k$ and $a,b\in \mathbb{Q}\cup \{\mathrm{\infty }\}$, we denote by $S_a^b$ the valued relation such that $S_a^b(t)=a$ if $t\in S$, and $S_a^b(t)=b$ otherwise. We write $S_0^{\mathrm{\infty }}$ to stress that $S$ is a crisp relation viewed as a valued relation. The unary empty relation on $A$, where every element of $A$ evaluates to $\mathrm{\infty }$, is denoted by $\perp$.

A (relational) signature $\tau$ is a set of relation symbols, each of them equipped with an arity from $\mathbb{N}$. A valued $\tau$-structure $𝔄$ consists of a set $A$, which is also called the domain of $𝔄$, and a valued relation $R^{𝔄}\in {ℛ}_A^{(k)}$ for each relation symbol $R\in \tau$ of arity $k$. All valued structures in this article have countable domains. We often write $R$ instead of $R^{𝔄}$ if the valued structure is clear from the context. When not specified, we assume that the domains of valued structures $𝔄,𝔅,ℭ,\mathrm{\dots }$ are denoted $A,B,C,\mathrm{\dots }$, respectively. If $ℛ$ is a set of valued relations over a common domain $A$, we write $(A;ℛ)$ for a valued structure $𝔄$ whose relations are precisely the relations from $ℛ$; we only use this notation if the precise choice of the signature does not matter. A valued $\tau$-structure where all valued relations only take values from $\{0,\mathrm{\infty }\}$ may then be viewed as a relational or crisp $\tau$-structure in the classical sense. A valued structure is called essentially crisp if all of its valued relations are essentially crisp. If $𝔄$ is a valued $\tau$-structure on the domain $A$, then $\mathrm{Feas}(𝔄)$ denotes the relational $\tau$-structure ${𝔄}^{\prime }$ on the domain $A$ where $R^{{𝔄}^{\prime }}=\mathrm{Feas}(R^{𝔄})$ for every $R\in \tau$. If $\sigma \subseteq \tau$ and ${𝔄}^{\prime }$ is a valued $\sigma$-structure such that $R^{{𝔄}^{\prime }}=R^{𝔄}$ for every $R\in \sigma$, then we call ${𝔄}^{\prime }$ a reduct of $𝔄$.

Let $\tau$ be a relational signature. An atomic $\tau$-expression is an expression of the form $R(x_1,\mathrm{\dots },x_k)$ for $R\in \tau$, ${(=)}_0^{\mathrm{\infty }}(x_1,x_2)$, or $\perp (x_1)$ where $x_1,\mathrm{\dots },x_k$ are (not necessarily distinct) variable symbols. A $\tau$-expression is an expression $\varphi$ of the form ${\sum }_{i\le m}{\varphi }_i$ where $m\in \mathbb{N}$ and ${\varphi }_i$ for $i\in \{1,\mathrm{\dots },m\}$ is an atomic $\tau$-expression. Note that the same atomic $\tau$-expression might appear several times in the sum. We write $\varphi (x_1,\mathrm{\dots },x_n)$ for a $\tau$-expression where all the variables are from the set $\{x_1,\mathrm{\dots },x_n\}$. If $𝔄$ is a valued $\tau$-structure, then a $\tau$-expression $\varphi (x_1,\mathrm{\dots },x_n)$ defines over $𝔄$ a member of ${ℛ}_A^{(n)}$ in the usual way, which we denote by ${\varphi }^{𝔄}$ (for example, if $\varphi (x,y)=R(x)+S(y)$ and $𝔄$ is an $\{R,S\}$-structure, then ${\varphi }^{𝔄}(x,y)=R^{𝔄}(x)+S^{𝔄}(y)$ for all $x,y\in A$). If $\varphi$ is the empty sum, then ${\varphi }^{𝔄}$ is constant $0$.

Let $𝔄$ be a valued structure over a finite signature $\tau$. The valued constraint satisfaction problem for $𝔄$, denoted by $\mathrm{VCSP}(𝔄)$, is the computational problem to decide for a given $\tau$-expression $\varphi (x_1,\mathrm{\dots },x_n)$ and a given $u\in \mathbb{Q}$ whether there exists $t\in A^n$ such that ${\varphi }^{𝔄}(t)\le u$. We refer to $\varphi$ as an instance of $\mathrm{VCSP}(𝔄)$, and to $u$ as the threshold. We also refer to the pair $(\varphi ,u)$ as a (positive or negative) instance of $\mathrm{VCSP}(𝔄)$. A tuple $t\in A^n$ such that ${\varphi }^{𝔄}(t)\le u$ is called a solution for $(\varphi ,u)$. The cost of $\varphi$ (with respect to $𝔄$) is defined to be ${inf}_{t\in A^n}{\varphi }^{𝔄}(t).$ In some contexts, it will be beneficial to consider only a given $\tau$-expression $\varphi$ to be the input of $\mathrm{VCSP}(𝔄)$ (rather than $\varphi$ and the threshold $u$) and a tuple $t\in A^n$ will then be called a solution for $\varphi$ if the cost of $\varphi$ equals ${\varphi }^{𝔄}(t)$. In general, there might not be any solution. If there exists $t\in A^n$ such that then $\varphi$ is called satisfiable. To give an example of a VCSP, note that is the minimum feedback arc set problem for directed multigraphs.

If $𝔄$ is a relational $\tau$-structure, then $\mathrm{CSP}(𝔄)$ is the problem of deciding satisfiability of conjunctions of atomic $\tau$-formulas in $𝔄$. Therefore, if $𝔄$ is a relational structure then $\mathrm{VCSP}(𝔄)$ and $\mathrm{CSP}(𝔄)$ are essentially the same problem.

Let $k\in \mathbb{N}$, let $R\in {ℛ}_A^{(k)}$, and let $\alpha$ be a permutation of $A$. Then $\alpha$ preserves $R$ if for all $t\in A^k$ we have $R(\alpha (t))=R(t)$. If $𝔄$ is a valued structure with domain $A$, then an automorphism of $𝔄$ is a permutation of $A$ that preserves all valued relations of $R$. The set of all automorphisms of $𝔄$ is denoted by $\mathrm{Aut}(𝔄)$, and forms a group with respect to composition. If $𝔅$ is a valued structure and we write $\mathrm{Aut}(𝔅)\subseteq \mathrm{Aut}(𝔄)$ or $\mathrm{Aut}(𝔅)=\mathrm{Aut}(𝔄)$, we implicitly assume that $𝔄$ and $𝔅$ have the same domain.

Let $k\in \mathbb{N}$. An orbit of $k$-tuples of a permutation group $G$ on a set $A$ is a set of the form $\{\alpha (t)\mid \alpha \in G\}$ for some $t\in A^k$. A permutation group $G$ on a countable set is called oligomorphic if for every $k\in \mathbb{N}$ there are finitely many orbits of $k$-tuples in $G$ [17]. For example, and therefore every permutation group on $\mathbb{Q}$ that contains is oligomorphic. If $𝔄$ is a relational structure with an oligomorphic automorphism group and $R\subseteq A^k$, then $R$ is first-order definable over $𝔄$ if and only if $R$ is preserved by $\mathrm{Aut}(𝔄)$ (this theorem, including the definition of first-order logic, is treated, e.g., in [2] (Theorem 4.2.9)).

Let $𝔄$ be a valued $\tau$-structure and $𝔅$ a relational structure. Suppose that $\mathrm{Aut}(𝔅)$ is oligomorphic and $\mathrm{Aut}(𝔅)\subseteq \mathrm{Aut}(𝔄)$ (and hence $\mathrm{Aut}(𝔄)$ is oligomorphic). Let $R\in \tau$ be of arity $k$. Then $R^{𝔄}$ attains only finitely many values by the oligomorphicity of $\mathrm{Aut}(𝔄)$. Moreover, if for some $s,t\in A^k$ we have $R^{𝔄}(s)\ne R^{𝔄}(t)$, then $s$ and $t$ lie in a different orbit of $\mathrm{Aut}(𝔅)$. Therefore, for every value $a\in \mathbb{Q}\cup \{\mathrm{\infty }\}$, there is a union $U_a$ of orbits of $k$-tuples under the action of $\mathrm{Aut}(𝔅)$ such that $R^{𝔄}(t)=a$ if and only if $t\in U_a$. Since $U_a$ is preserved by $\mathrm{Aut}(𝔅)$, it is first-order definable over $𝔅$ by a formula ${\varphi }_a$. Hence, $R$ can be given by a list of values $a$ in the range of $R$ and first-order formulas ${\varphi }_a$ over $𝔅$. Such a collection $((R,a,{\varphi }_a)\mid R\in \tau ,\exists t\in A^k(R(t)=a))$ will be called a first-order definition of $𝔄$ in $𝔅$. Clearly, if a valued structure $𝔄$ has a first-order definition in a relational structure $𝔅$, then $\mathrm{Aut}(𝔅)\subseteq \mathrm{Aut}(𝔄)$. Note that for some structures $𝔅$ such as $(\mathbb{Q};=)$ and , the formulas ${\varphi }_a$ can be chosen to be quantifier-free, and hence as disjunctions of conjunctions of atomic formulas over $𝔅$ (in fact, this is the case for every homogeneous structure with a finite relational signature). We will use first-order definitions of valued structures to be able to give valued structures as an input to decision problems (see Proposition 41).

The structure is known to be finitely bounded and homogeneous, which yields the following theorem as a special case of [13, Theorem 3.4].

We define generalizations of the concepts of primitive positive definitions and relational clones. The motivation is that relations with a primitive positive definition can be added to the structure without changing the complexity of the respective CSP.

Note that ${inf}_{t\in A^n}R(s,t)$ in item 1 might be irrational or $-\mathrm{\infty }$. If this is the case, then ${inf}_{t\in A^n}R(s,t)$ does not express a valued relation because valued relations must have weights from $\mathbb{Q}\cup \{\mathrm{\infty }\}$. However, if $R$ is preserved by all permutations of an oligomorphic automorphism group, then $R$ attains only finitely many values and therefore this is never the case.

If $S\subseteq {ℛ}_A$, then an atomic expression over $S$ is an atomic $\tau$-expression where $\tau =S$. We say that $S$ is closed under forming sums of atomic expressions if for every $n\in \mathbb{N}$, $R_1,\mathrm{\dots },R_n\in S$ of arity $k_1,\mathrm{\dots },k_n$, respectively, and $i_1^j,\mathrm{\dots },i_{k_j}^j\in [k_j]$ for $j\in \{1,\mathrm{\dots },n\}$, the set $S$ also contains the valued relation $R$ of arity $k$ defined by

Note that every relation which is primitively positively definable from a set $S\subseteq {ℛ}_A$ of crisp relations lies in $⟨S⟩$. Moreover, if $𝔄$ is a relational structure and $R\in ⟨𝔄⟩$, then $R$ is essentially crisp and $\mathrm{Feas}(R)$ is primitively positively definable from $𝔄$; this is easily verified by induction.

The following lemma is the main motivation for the concept of expressibility.

We now introduce notation that enables us to talk about the crisp relations expressible in a valued structure, which turn out to be essential to understanding temporal VCSPs.

In words, ${⟨𝔄⟩}_0^{\mathrm{\infty }}$ contains all crisp relations that can be expressed in $𝔄$. If $𝔄$ is essentially crisp, then $⟨𝔄⟩=⟨\mathrm{Feas}(𝔄)⟩$ and ${⟨𝔄⟩}_0^{\mathrm{\infty }}$ consists of precisely those relations that are primitively positively definable in $\mathrm{Feas}(𝔄)$. In this case we obtain a polynomial-time reduction from $\mathrm{VCSP}(𝔄)$ to $\mathrm{CSP}(\mathrm{Feas}(𝔄))$ and vice versa by Lemma 5.

Next, we introduce a concept of pp-constructions which give rise to polynomial-time reductions between VCSPs. The acronym “pp” stands for primitive positive, since the concept of pp-constructions for relational structures is a generalization of primitive positive definitions used for reductions between CSPs.

Let $A$ and $B$ be sets and $f:B\to A$. If $k\in \mathbb{N}$ and $s\in B^k$, then by $f(s)$ we mean the tuple $(f(s_1),\mathrm{\dots },f(s_k))\in A^k.$ We equip the space $A^B$ of functions from $B$ to $A$ with the topology of pointwise convergence, where $A$ is taken to be discrete. In this topology, a basis of open sets is given by

for $s\in B^k$ and $t\in A^k$ for some $k\in \mathbb{N}$. For any topological space $T$, we denote by $ℬ(T)$ the Borel $\sigma$-algebra on $T$, i.e., the smallest subset of the powerset $𝒫(T)$ which contains all open sets and is closed under countable intersection and complement. We write $[0,1]$ for the set $\{x\in ℝ\mid 0\le x\le 1\}$.

We often use $\omega$ for both the entire fractional map and for the map $\omega :ℬ(A^B)\to [0,1]$.

The set $[0,1]$ carries the topology inherited from the standard topology on $ℝ$. We also view $ℝ\cup \{\mathrm{\infty }\}$ as a topological space with a basis of open sets given by all open intervals $(a,b)$ for $a,b\in ℝ$, and additionally all sets of the form $\{x\in ℝ\mid x>a\}\cup \{\mathrm{\infty }\}$ (thus, $ℝ\cup \{\mathrm{\infty }\}$ is equipped with its order topology when ordered in the natural way).

A (real-valued) random variable is a measurable function $X:T\to ℝ\cup \{\mathrm{\infty }\}$, i.e., pre-images of elements of $ℬ(ℝ\cup \{\mathrm{\infty }\})$ under $X$ are in $ℬ(T)$. If $X$ is a real-valued random variable, then the expected value of $X$ (with respect to a probability distribution $\omega$) is denoted by $E_{\omega }[X]$ and is defined via the Lebesgue integral

Let $A$ and $B$ be sets. In the rest of the paper, we will work exclusively on a topological space $A^B$ and the special case where $B=A^{\mathrm{\ell }}$ for some $\mathrm{\ell }\in \mathbb{N}$ and $A^B$ is the set of $\mathrm{\ell }$-ary operations on $A$, we denote this set by ${𝒪}_A^{(\mathrm{\ell })}$.

We refer to [13] for a detailed introduction to fractional homomorphisms in full generality. All concrete fractional homomorphisms $\omega$ that appear in this paper are of a very special form, namely, there is a single $f\in A^B$ such that $\omega (\{f\})=1$. In this case, we also write $f$ instead of $\omega$. If $\omega$ is of this form, then for every $R\in \tau$ of arity $k$ and $t\in B^k$, the expected value in Definition 9 always exists and is equal to $R^{𝔄}(f(t))$. If additionally $𝔄$ and $𝔅$ are crisp structures, then we call $f$ a homomorphism. It is easy to see that there are valued structures $𝔄$ and $𝔅$ with a fractional homomorphism from $𝔅$ to $𝔄$, but no fractional homomorphism from $𝔅$ to $𝔄$ of the form $f\in A^B$ (see, e.g. [41, Example 2.6 and 3.15]).

We say that two valued $\tau$-structures $𝔄$ and $𝔅$ are fractionally homomorphically equivalent if there exists a fractional homomorphisms from $𝔄$ to $𝔅$ and from $𝔅$ to $𝔄$. Since fractional homomorphisms compose [13], fractional homomorphic equivalence is indeed an equivalence relation on valued structures of the same signature.

The relation of pp-constructability is transitive: if $𝔄$, $𝔅$, and $ℭ$ are valued structures such that $𝔄$ pp-constructs $𝔅$ and $𝔅$ pp-constructs $ℭ$, then $𝔄$ pp-constructs $ℭ$ [13, Lemma 5.14].

By $K_3$ we denote the complete graph on $3$ vertices. The following is a direct consequence of [13, Corollary 5.13] and [2, Corollary 6.7.13].

It is well-known that $K_3$ pp-constructs all finite relational structures (see, e.g, [2, Corollary 6.4.4]). Hence, by the transitivity of pp-constructability, every valued structure that pp-constructs $K_3$ pp-constructs all finite relational structures.

Let $A$ be a set and $R\subseteq A^k$. An operation $f:A^{\mathrm{\ell }}\to A$ on the set $A$ preserves $R$ if $f(t^1,\mathrm{\dots },t^{\mathrm{\ell }})\in R$ for every $t^1,\mathrm{\dots },t^{\mathrm{\ell }}\in R$. If $𝔄$ is a relational structure and $f$ preserves all relations of $𝔄$, then $f$ is called a polymorphism of $𝔄$. The set of all polymorphisms of $𝔄$ is denoted by $\mathrm{Pol}(𝔄)$ and is closed under composition. We write ${\mathrm{Pol}}^{(\mathrm{\ell })}(𝔄)$ for the set $\mathrm{Pol}(𝔄)\cap {𝒪}_A^{(\mathrm{\ell })}$, $\mathrm{\ell }\in \mathbb{N}$. Unary polymorphisms are called endomorphisms and ${\mathrm{Pol}}^{(1)}(𝔄)$ is also denoted by $\mathrm{End}(𝔄)$.

Let $𝔄$ be a relational structure and $\mathrm{\ell }\in \mathbb{N}$. An operation $f\in {\mathrm{Pol}}^{(\mathrm{\ell })}(𝔄)$ is called a pseudo weak near unanimity (pwnu) polymorphism if there exist $e_1,\mathrm{\dots },e_{\mathrm{\ell }}\in \mathrm{End}(𝔄)$ such that for every $x,y\in A$, $e_{1}f(y,x,\mathrm{\dots },x)=e_{2}f(x,y,x,\mathrm{\dots },x)=\mathrm{\cdots }=e_{\mathrm{\ell }}f(x,\mathrm{\dots },x,y).$ We now introduce fractional polymorphisms of valued structures, which generalize polymorphisms of relational structures. Similarly to polymorphisms, fractional polymorphisms are an important tool for formulating tractability results and complexity classifications of VCSPs. For valued structures with a finite domain, our definition specialises to the established notion of a fractional polymorphism which has been used to study the complexity of VCSPs for valued structures over finite domains (see, e.g. [38]). Our definition is taken from [13] and allows arbitrary probability spaces in contrast to [39, 37, 40].

Note that (1) has the interpretation that the expected value of $R(f(t^1,\mathrm{\dots },t^{\mathrm{\ell }}))$ is at most the average of the values $R(t^1),\mathrm{\dots }$, $R(t^{\mathrm{\ell }})$.

As mentioned above, all concrete fractional polymorphisms $\omega$ that we need in this article are such that there exists an operation $f\in {𝒪}_A^{(\mathrm{\ell })}$ such that $\omega (\{f\})=1$.

We first define several important relations on $\mathbb{Q}$ that already played a role in the classification of temporal CSPs [7]; in this paper, we treat these relations in a black-box fashion.

To build on the results on temporal CSPs, we need the following operations on $\mathbb{Q}$; they will be used in a black-box fashion as well. By $\min$ and $\max$ we refer to the binary minimum and maximum operation on the set $\mathbb{Q}$, respectively.

The construction of endomorphisms that appear in Definitions 29 and 30 can be found for example in [2, Section 12.5]. The following was observed and used in [7].

Note that ${\min }^{\ast }=\max$ and the relation $-(>)$ is equal to . Statements about operations and relations on $\mathbb{Q}$ can be naturally dualised and we may refer to the dual version of a statement.

By combining results from [7] (Theorem 50, Corollary 51, Corollary 52, and the accompanying remarks), we obtain the following; also see Theorem 12.10.1 in [2].

We also need an alternative version of the classification theorem above.

The following proposition relates hardness of temporal CSPs to pp-constructing $K_3$; it is essentially proven in [2, Theorem 12.0.1].

In Lemma 38 below we present a polynomial-time algorithm for VCSPs of valued structures $𝔄$ improved by $\mathrm{lex}$ where a certain finite-signature reduct $\widehat{𝔄}$ of $(\mathbb{Q};{⟨𝔄⟩}_0^{\mathrm{\infty }})$ is preserved by $\mathrm{ll}$ or ${\mathrm{ll}}^{\ast }$; we define $\widehat{𝔄}$ below.

Note that $R_{\sigma }\in ⟨(A;R)⟩$ for every valued relation $R$ of arity $k$ and every $\sigma :[k]\to [\mathrm{\ell }]$.

In Algorithm 1 we provide a polynomial-time algorithm for the proof of Lemma 38. We can now state the complexity dichotomy for temporal VCSPs. We first phrase the classification with 4 cases, where we distinguish between the tractable cases that are based on different algorithms. As a next step, we formulate two corollaries each of which provides two concise mutually disjoint conditions that correspond to NP-completeness and polynomial-time tractability, respectively.