Recognizing distance-count matrices
PLOS One · 08.07.2026 · 21 (7) · e0352427
DOI: 10.1371/journal.pone.0352427 ↗Kurz gefasst
Fachartikel in der Zeitschrift PLOS One, online erschienen am 08.07.2026. Verfasst von Paolo Boldi und 3 weiteren Autor:innen. Beteiligte Einrichtung: Computer Science Department, Università degli Studi, Milano, Italy. Hauptthemen laut MEDLINE: Algorithms, Models, Theoretical. Die Arbeit nennt 33 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Ministero dell’Istruzione, dell’Università e della Ricerca.
Abstract (Originalsprache)
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.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Computer Science Department, Università degli Studi, Milano, Italy.
- Mathematics Institute, University of Warwick, Coventry, United Kingdom.
ORCID-Profile: Paolo Boldi
Förderung
- Ministero dell’Istruzione, dell’Università e della Ricerca
Zitieren
APA
Boldi, P., Prezioso, C., Furia, F., & Stewart, I. (2026). Recognizing distance-count matrices. PLOS One, 21(7), e0352427. https://doi.org/10.1371/journal.pone.0352427
Vancouver
Boldi P, Prezioso C, Furia F, Stewart I. Recognizing distance-count matrices. PLOS One. 2026;21(7):e0352427. doi:10.1371/journal.pone.0352427
BibTeX
@article{Boldi2026,
author = {Boldi, Paolo and Prezioso, Chiara and Furia, Flavio and Stewart, Ian},
title = {Recognizing distance-count matrices},
journal = {PLOS One},
year = {2026},
volume = {21},
number = {7},
pages = {e0352427},
doi = {10.1371/journal.pone.0352427}
}
EUVIMED