The Complexity of Homomorphism Reconstructibility

ACM Transactions on Computation Theory, vol. 18, pp. 1–37

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 reconstructibility 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 \(\mathsf {NP}^{\#\mathsf {P}}\) -hard problem, which still can be \(\mathsf {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 \(\mathsf {NP}\) -hard unless \(\mathsf {P}= \mathsf {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.

Authors 5

1. Jan Böker Aachen Chair for Logic and Theory of Discrete Systems

   RWTH Aachen University

   Affiliation as printed

   Chair for Logic and Theory of Discrete Systems, RWTH Aachen University

2. Louis Härtel Aachen Chair for Logic and Theory of Discrete Systems

   RWTH Aachen University

   Affiliation as printed

   Chair for Logic and Theory of Discrete Systems, RWTH Aachen University

3. Nina Runde Aachen Chair for Logic and Theory of Discrete Systems

   RWTH Aachen University

   Affiliation as printed

   Chair for Logic and Theory of Discrete Systems, RWTH Aachen University

4. Tim Seppelt Aachen Chair for Logic and Theory of Discrete Systems

   IT University of Copenhagen · RWTH Aachen University

   Affiliation as printed

   Chair for Logic and Theory of Discrete Systems, RWTH Aachen University

   IT-Universitet i København

5. Christoph Standke Aachen Chair for Logic and Theory of Discrete Systems

   RWTH Aachen University

   Affiliation as printed

   Chair for Logic and Theory of Discrete Systems, RWTH Aachen University