DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.45

The Complexity of Homomorphism Reconstruction Revisited

Authors: Timo Gervens, Martin Grohe, Louis Härtel, and Philipp da Silva Fonseca

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

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₁,…,F_k and counts m₁,…,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 Σ₂^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.

Cite as

Timo Gervens, Martin Grohe, Louis Härtel, and Philipp da Silva Fonseca. The Complexity of Homomorphism Reconstruction Revisited. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gervens_et_al:LIPIcs.STACS.2026.45,
  author =	{Gervens, Timo and Grohe, Martin and H\"{a}rtel, Louis and da Silva Fonseca, Philipp},
  title =	{{The Complexity of Homomorphism Reconstruction Revisited}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.45},
  URN =		{urn:nbn:de:0030-drops-255342},
  doi =		{10.4230/LIPIcs.STACS.2026.45},
  annote =	{Keywords: graph homomorphism, nexp-complete, counting complexity}
}

Document

DOI: 10.4230/LIPIcs.STACS.2024.19

The Complexity of Homomorphism Reconstructibility

Authors: Jan Böker, Louis Härtel, Nina Runde, Tim Seppelt, and Christoph Standke

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract

Representing graphs by their homomorphism counts has led to the beautiful theory of homomorphism indistinguishability in recent years. Moreover, homomorphism counts have promising applications in database theory and machine learning, where one would like to answer queries or classify graphs solely based on the representation of a graph G as a finite vector of homomorphism counts from some fixed finite set of graphs to G. We study the computational complexity of the arguably most fundamental computational problem associated to these representations, the homomorphism reconstructability problem: given a finite sequence of graphs and a corresponding vector of natural numbers, decide whether there exists a graph G that realises the given vector as the homomorphism counts from the given graphs. We show that this problem yields a natural example of an NP^#𝖯-hard problem, which still can be NP-hard when restricted to a fixed number of input graphs of bounded treewidth and a fixed input vector of natural numbers, or alternatively, when restricted to a finite input set of graphs. We further show that, when restricted to a finite input set of graphs and given an upper bound on the order of the graph G as additional input, the problem cannot be NP-hard unless 𝖯 = NP. For this regime, we obtain partial positive results. We also investigate the problem’s parameterised complexity and provide fpt-algorithms for the case that a single graph is given and that multiple graphs of the same order with subgraph instead of homomorphism counts are given.

Cite as

Jan Böker, Louis Härtel, Nina Runde, Tim Seppelt, and Christoph Standke. The Complexity of Homomorphism Reconstructibility. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 19:1-19:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{boker_et_al:LIPIcs.STACS.2024.19,
  author =	{B\"{o}ker, Jan and H\"{a}rtel, Louis and Runde, Nina and Seppelt, Tim and Standke, Christoph},
  title =	{{The Complexity of Homomorphism Reconstructibility}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{19:1--19:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.19},
  URN =		{urn:nbn:de:0030-drops-197298},
  doi =		{10.4230/LIPIcs.STACS.2024.19},
  annote =	{Keywords: graph homomorphism, counting complexity, parameterised complexity}
}

Search Results

Documents authored by Härtel, Louis

The Complexity of Homomorphism Reconstruction Revisited

Abstract

Cite as

The Complexity of Homomorphism Reconstructibility

Abstract

Cite as

Thanks for your feedback!

Could not send message