The Complexity of Homomorphism Reconstruction Revisited

We revisit the algorithmic problem of reconstructing a graph from homomorphism counts that has first been studied in (Böker et al. , STACS 2024): given graphs F₁, …, Fₖ and counts m₁, …, mₖ, decide if there is a graph G such that the number of homomorphisms from Fᵢ to G is mᵢ, for all i. We prove that the problem is NEXP-hard if the counts mᵢ are specified in binary and Σ₂ᵖ-complete if they are in unary. Furthermore, as a positive result, we show that the unary version can be solved in polynomial time if the constraint graphs are stars of bounded size.