{"id":"arxiv/2602.12780","url":"https://arxiv.org/abs/2602.12780","tags":["cs.DM","cs.DS","math.CO"],"score":0,"title":"The Complexity of Homomorphism Reconstruction Revisited","domain":"cs.DM","source":"arxiv","authors":["Timo Gervens","Martin Grohe","Louis Härtel","Philipp da Silva Fonseca"],"reviews":0,"subject":"cs.DM","summary":"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,\\ldots,F_k$ and counts $m_1,\\ldots,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 $Σ_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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-13","reactions":{}}