Recognizing distance-count matrices

Abstract

Axiomatizing centrality measures often requires proving that certain properties do not hold by exhibiting a counterexample (i.e., a graph for which a given centrality measure does not satisfy a specified property). In the context of geometric centralities, constructing such counterexamples requires building a graph with prescribed distance counts, as encoded in its distance-count matrix (DCM). We prove that deciding whether a matrix is the distance-count matrix of an undirected graph is strongly NP-complete. This negative result implies that a brute-force approach to constructing such counterexamples is out of the question. We complement this negative result with some positive findings: while recognizing DCM matrices is strongly NP-hard, the construction of DCM matrices is algorithmically well-behaved under some natural graph operations (which we call DCM-stable ): that is, for many important graph operations ⊗, the DCM of G ⊗ H can be computed efficiently from those of G and H , without having to reconstruct the graphs themselves. This observation shows that, although the inverse problem is intractable in general, distance-count matrices admit a rich and tractable compositional theory on structured graph classes generated by DCM-stable operations.