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.MFCS.2022.52

Graph Similarity Based on Matrix Norms

Authors: Timo Gervens and Martin Grohe

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract

Quantifying the similarity between two graphs is a fundamental algorithmic problem at the heart of many data analysis tasks for graph-based data. In this paper, we study the computational complexity of a family of similarity measures based on quantifying the mismatch between the two graphs, that is, the "symmetric difference" of the graphs under an optimal alignment of the vertices. An important example is similarity based on graph edit distance. While edit distance calculates the "global" mismatch, that is, the number of edges in the symmetric difference, our main focus is on "local" measures calculating the maximum mismatch per vertex. Mathematically, our similarity measures are best expressed in terms of the adjacency matrices: the mismatch between graphs is expressed as the difference of their adjacency matrices (under an optimal alignment), and we measure it by applying some matrix norm. Roughly speaking, global measures like graph edit distance correspond to entrywise matrix norms like the Frobenius norm and local measures correspond to operator norms like the spectral norm. We prove a number of strong NP-hardness and inapproximability results even for very restricted graph classes such as bounded-degree trees.

Cite as

Timo Gervens and Martin Grohe. Graph Similarity Based on Matrix Norms. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gervens_et_al:LIPIcs.MFCS.2022.52,
  author =	{Gervens, Timo and Grohe, Martin},
  title =	{{Graph Similarity Based on Matrix Norms}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.52},
  URN =		{urn:nbn:de:0030-drops-168509},
  doi =		{10.4230/LIPIcs.MFCS.2022.52},
  annote =	{Keywords: graph similarity, approximate graph isomorphism, graph matching}
}

Search Results

Documents authored by Gervens, Timo

The Complexity of Homomorphism Reconstruction Revisited

Abstract

Cite as

Graph Similarity Based on Matrix Norms

Abstract

Cite as

Thanks for your feedback!

Could not send message