{"ID":2878021,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.18857","arxiv_id":"2508.18857","title":"Recognizing Distance-Count Matrices is Difficult","abstract":"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.","short_abstract":"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 specif...","url_abs":"https://arxiv.org/abs/2508.18857","url_pdf":"https://arxiv.org/pdf/2508.18857v2","authors":"[\"Paolo Boldi\",\"Flavio Furia\",\"Chiara Prezioso\",\"Ian Stewart\"]","published":"2025-08-26T09:37:22Z","proceeding":"cs.SI","tasks":"[\"cs.SI\"]","methods":"[]","has_code":false}