EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Recognizing distance-count matrices

Paolo Boldi iD, Chiara Prezioso, Flavio Furia, Ian Stewart

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsModels, Theoretical

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}
}
Kostenlos starten →