I am interested in the following problem: given two relational structures $\mathbf{A},\mathbf{B}$, is there a unique homomorphism from $\mathbf{A}$ to $\mathbf{B}$ up to automorphisms of $\mathbf{B}$, meaning that: there is at least one homomorphism from $\mathbf{A}$ to $\mathbf{B}$ and, for every homomorphisms $f,g\colon \mathbf{A} \to \mathbf{B}$, there exists an automorphism $\psi$ of $\mathbf{B}$ such that $f = \psi \circ g$. If this helps, the signature can be assumed to be part of the input of the problem. The problem clearly belongs to $\Pi_2^P$.
Question: What is the computational complexity of this problem?
Here is what I know: it is in $\textsf{NP} \land \textsf{coNP}^{\textsf{GI}}$ and is $\textsf{US}$-hard under polynomial-time reductions.
Upper-bound
Fact 1: Given two homomorphisms $f,g\colon \mathbf{A} \to \mathbf{B}$, deciding if there are equivalent up to $\mathbf{B}$-automorphisms is in $\textsf{GI}$, the class of all problems that are reducible in polynomial-time to the graph isomorphism problem. (In fact it is even $\textsf{GI}$-complete.)
Proof: Given $f,g\colon \mathbf{A} \to \mathbf{B}$, where $\mathbf{A},\mathbf{B}$ are $\sigma$-structure, let $\sigma_{\mathbf{A}}$ be the signature obtained from $\sigma$ by adding a unary predicate symbol $a$ for each $a \in \mathbf{A}$. Define $\mathbf{B}_f$ as the $\sigma_{\mathbf{A}}$-structure obtained from $\mathbf{B}$ by making the predicate $a$ true only on the vertex $f(a)$. Then $\mathbf{B}_f$ and $\mathbf{B}_f$ are isomorphic if and only if $f$ and $g$ are equivalent up to $\mathbf{B}$-automorphisms.
Coro 2: The problem belongs to $\textsf{NP} \land \textsf{coNP}^{\textsf{GI}}$, i.e. it can be written as the intersection of a problem in $\textsf{NP}$ and a problem solvable in $\textsf{coNP}$ with $\textsf{GI}$-oracle.
Moreover, assuming $\textsf{AM} = \textsf{NP}$, then $\textsf{coNP}^{\textsf{GI}} = \textsf{coNP}$ (see this answer), and hence the problem belongs to $\textsf{NP} \land \textsf{coNP} =$ $\textsf{DP}$. Could we show this upper-bound without assuming that $\textsf{AM} = \textsf{NP}$ ?
Lower-bound
Fix $\sigma$ to contain a single binary symbol, and let $\mathbf{K}_3$ be the $\sigma$-structure with three elements with all possible edges except self-loops. There is a unique homomorphism $\mathbf{A} \to \mathbf{K}_3$ up to $\mathbf{K}_3$-automorphisms if and only if there is a unique 3-coloring of $\mathbf{A}$ up to renaming the colors. This problem was shown to be $\mathsf{US}$-complete by Barbanchon (Proposition 5), where $\mathsf{US}$ is the class of problems of the form $\{x \in \Sigma^* \mid \text{there exists a unique $y \in \Sigma^*$ such that $R(x,y)$ holds} \}$ for some polynomial-time computable relation $R$. Hence:
Fact 3: The problem is $\mathsf{US}$-hard under polynomial-time reductions.
In fact, it is not hard to see that for by fixing any structure $\mathbf{B}$, the problem becomes $\mathsf{US}$: the number of $\mathbf{B}$-automorphisms is constant.
Remarks
- The classes I mentioned are ordered in the following way: $\mathsf{coNP} \subseteq \mathsf{US} \subseteq \mathsf{DP} \subseteq \textsf{NP} \land \textsf{coNP}^{\textsf{GI}} \subseteq \Pi_2^P$.
- Barbanchon's paper refers to results showing that Unique-SAT (which is $\textsf{US}$-complete under polynomial-time reductions) is $\textsf{DP}$-complete under randomized polynomial-time reductions. This result does not imply that $\textsf{US} = \textsf{DP}$. On page 415 of Papadimitriou's Computational Complexity, it is mentioned that Unique-SAT is believed not to be $\textsf{DP}$-complete (under polynomial-time reductions).
- I am also interested in the symmetric problem (unique homomorphism from $\mathbf{A}$ up to $\mathbf{B}$ up to $\mathbf{A}$-automorphisms).
