Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.12780 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915805499752448 |
|---|---|
| author | Gervens, Timo Grohe, Martin Härtel, Louis Fonseca, Philipp da Silva |
| author_facet | Gervens, Timo Grohe, Martin Härtel, Louis Fonseca, Philipp da Silva |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_12780 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Complexity of Homomorphism Reconstruction Revisited Gervens, Timo Grohe, Martin Härtel, Louis Fonseca, Philipp da Silva Discrete Mathematics Data Structures and Algorithms Combinatorics 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. |
| title | The Complexity of Homomorphism Reconstruction Revisited |
| topic | Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2602.12780 |