Recognizing distance-count matrices

Paolo Boldi, Chiara Prezioso, Flavio Furia and Ian Stewart

PLOS ONE, 2026, vol. 21, issue 7, 1-27

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.

Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0352427 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 52427&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0352427

DOI: 10.1371/journal.pone.0352427

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().