paper

The Complexity of Homomorphism Reconstruction Revisited

arXiv:2602.12780

Abstract

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_{1}, \dots, F_{k}$ and counts $m_{1}, \dots, m_{k}$ , decide if there is a graph $G$ such that the number of homomorphisms from $F_{i}$ to $G$ is $m_{i}$ , for all $i$ . We prove that the problem is NEXP-hard if the counts $m_{i}$ are specified in binary and $I^£_{2}^{p}$ -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.

Full version of a paper accepted at STACS 2026