# Complexity of the unique homomorphism problem up to automorphisms

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).