Recognizing distance-count matrices

Paolo Boldi, Chiara Prezioso, Flavio Furia, Ian Stewart · 2026

Read Recognizing distance-count matrices by Paolo Boldi, Chiara Prezioso, Flavio Furia, Ian Stewart (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/plos-pone-0352427.txt.

Description

Paolo Boldi and three colleagues present this 2026 PLOS One mathematics paper about distance-count matrices, tables recording how many nodes in a network sit at each distance from a given node. Such tables underpin measures of how central a node is, and researchers sometimes need to know whether a made-up table could come from a real network when hunting for counterexamples.

The authors prove that deciding this question is strongly NP-complete, meaning no efficient general method is likely to exist. On the brighter side, they show that many common ways of combining networks preserve the ability to compute the combined table directly from the parts. The result closes one door for counterexample hunters while opening a compositional route for structured networks.

Catalog record

CREATORPaolo Boldi, Chiara Prezioso, Flavio Furia, Ian Stewart
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE59681
LICENSECC_BY
RIGHTSCC BY
SOURCEPLOS

Source: https://doi.org/10.1371/journal.pone.0352427

Browse the full library · About the Tower of Babel