On Queries Determined by a Constant Number of Homomorphism Counts
share
It is well known [Lovász, 1967] that up to isomorphism a graph G is determined by the homomorphism counts (F, G), i.e., the number of homomorphisms from F to G, where F ranges over all graphs. Moreover, it suffices that F ranges over the graphs with at most as many vertices as G. Thus in principle we can answer any query concerning G with only accessing the (·,G)'s instead of G itself. In this paper, we zoom in on those queries that can be answered using a constant number of (·,G) for every graph G. We observe that if a query φ is expressible as a Boolean combination of universal sentences in first-order logic, then whether a graph G satisfies φ can be determined by the vector hom_F_1, …, F_k(G):= (hom(F_1, G), …, hom(F_k, G)), where the graphs F_1,…,F_k only depend on φ. This leads to a query algorithm for φ that is non-adaptive in the sense that those F_i are independent of the input G. On the other hand, we prove that the existence of an isolated vertex, which is not definable by such a φ but in first-order logic, cannot be determined by any hom_F_1, …, F_k(·). These results provide a clear delineation of the power of non-adaptive query algorithms with access to a constant number of (·, G)'s. For adaptive query algorithms, i.e., algorithms that might access some (F_i+1, G) with F_i+1 depending on (F_1, G), …, (F_i, G), we show that three homomorphism counts (·,G) are both sufficient and in general necessary to determine the graph G. In particular, by three adaptive queries we can answer any question on G. Moreover, adaptively accessing two (·, G)'s is already enough to detect an isolated vertex.
READ FULL TEXT