Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2508.18857 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912725827846144 |
|---|---|
| author | Boldi, Paolo Furia, Flavio Prezioso, Chiara Stewart, Ian |
| author_facet | Boldi, Paolo Furia, Flavio Prezioso, Chiara Stewart, Ian |
| contents | Axiomatization of centrality measures often involves proving that something cannot hold by providing a counterexample (i.e., a graph for which that specific centrality index fails to have a given property). In the context of geometric centralities, building such counterexamples requires constructing a graph with specific distance counts between nodes, as expressed by its distance-count matrix. We prove that deciding whether a matrix is the distance-count matrix of a graph is strongly NP-complete. This negative result implies that a brute-force approach to building this kind of counterexample is out of question, and cleverer approaches are required. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18857 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Recognizing Distance-Count Matrices is Difficult Boldi, Paolo Furia, Flavio Prezioso, Chiara Stewart, Ian Social and Information Networks Axiomatization of centrality measures often involves proving that something cannot hold by providing a counterexample (i.e., a graph for which that specific centrality index fails to have a given property). In the context of geometric centralities, building such counterexamples requires constructing a graph with specific distance counts between nodes, as expressed by its distance-count matrix. We prove that deciding whether a matrix is the distance-count matrix of a graph is strongly NP-complete. This negative result implies that a brute-force approach to building this kind of counterexample is out of question, and cleverer approaches are required. |
| title | Recognizing Distance-Count Matrices is Difficult |
| topic | Social and Information Networks |
| url | https://arxiv.org/abs/2508.18857 |