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_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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.12780
curl -X POST /api/v1/records/arxiv/2602.12780/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.12780/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'