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
| CREATOR | Paolo Boldi, Chiara Prezioso, Flavio Furia, Ian Stewart |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59681 |
| LICENSE | CC_BY |
| RIGHTS | CC BY |
| SOURCE | PLOS |