{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:31Z","timestamp":1781077711128,"version":"3.54.1"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:00:00Z","timestamp":1675123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"SNSF Excellence","award":["200020B_182865\/1, and 200021_200731\/1"],"award-info":[{"award-number":["200020B_182865\/1, and 200021_200731\/1"]}]},{"name":"NSF CAREER","award":["CCF-1528078, and CCF-1514339"],"award-info":[{"award-number":["CCF-1528078, and CCF-1514339"]}]},{"name":"BSF","award":["2012338"],"award-info":[{"award-number":["2012338"]}]},{"name":"Sloan Research Fellowship and a Google"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>\n            Measuring the importance of a node in a network is a major goal in the analysis of social networks, biological systems, transportation networks, and so forth. Different\n            <jats:italic>centrality<\/jats:italic>\n            measures have been proposed to capture the notion of node importance. For example, the\n            <jats:italic>center<\/jats:italic>\n            of a graph is a node that minimizes the maximum distance to any other node (the latter distance is the\n            <jats:italic>radius<\/jats:italic>\n            of the graph). The\n            <jats:italic>median<\/jats:italic>\n            of a graph is a node that minimizes the sum of the distances to all other nodes. Informally, the\n            <jats:italic>betweenness centrality<\/jats:italic>\n            of a node\n            <jats:italic>w<\/jats:italic>\n            measures the fraction of shortest paths that have\n            <jats:italic>w<\/jats:italic>\n            as an intermediate node. Finally, the\n            <jats:italic>reach centrality<\/jats:italic>\n            of a node\n            <jats:italic>w<\/jats:italic>\n            is the smallest distance\n            <jats:italic>r<\/jats:italic>\n            such that any\n            <jats:italic>s<\/jats:italic>\n            -\n            <jats:italic>t<\/jats:italic>\n            shortest path passing through\n            <jats:italic>w<\/jats:italic>\n            has either\n            <jats:italic>s<\/jats:italic>\n            or\n            <jats:italic>t<\/jats:italic>\n            in the ball of radius\n            <jats:italic>r<\/jats:italic>\n            around\n            <jats:italic>w<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            The fastest known algorithms to compute the center and the median of a graph and to compute the betweenness or reach centrality even of a single node take roughly cubic time in the number\n            <jats:italic>n<\/jats:italic>\n            of nodes in the input graph. It is open whether these problems admit truly subcubic algorithms, i.e., algorithms with running time O\u0303(n\n            <jats:sup>3-\u03b4<\/jats:sup>\n            ) for some constant \u03b4 &gt; 0.\n            <jats:xref ref-type=\"fn\">\n              <jats:sup>1<\/jats:sup>\n            <\/jats:xref>\n          <\/jats:p>\n          <jats:p>\n            We relate the complexity of the mentioned centrality problems to two classical problems for which no truly subcubic algorithm is known, namely All Pairs Shortest Paths (APSP) and Diameter. We show that Radius, Median, and Betweenness Centrality are\n            <jats:italic>equivalent under subcubic reductions<\/jats:italic>\n            to APSP, i.e., that a truly subcubic algorithm for any of these problems implies a truly subcubic algorithm for all of them. We then show that Reach Centrality is equivalent to Diameter under subcubic reductions. The same holds for the problem of approximating Betweenness Centrality within any finite factor. Thus, the latter two centrality problems could potentially be solved in truly subcubic time, even if APSP required essentially cubic time.\n          <\/jats:p>\n          <jats:p>\n            On the positive side, our reductions for Reach Centrality imply an improved O\u0303(Mn\n            <jats:sup>\u03c9<\/jats:sup>\n            )-time algorithm for this problem in case of non-negative integer weights upper bounded by\n            <jats:italic>M<\/jats:italic>\n            , where \u03c9 is a fast matrix multiplication exponent.\n          <\/jats:p>","DOI":"10.1145\/3563393","type":"journal-article","created":{"date-parts":[[2022,9,16]],"date-time":"2022-09-16T13:27:29Z","timestamp":1663334849000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0502-4517","authenticated-orcid":false,"given":"Amir","family":"Abboud","sequence":"first","affiliation":[{"name":"IBM Almaden Research Center, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9676-4931","authenticated-orcid":false,"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"IDSIA, USI-SUPSI, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4844-2863","authenticated-orcid":false,"given":"Virginia","family":"Vassilevska Williams","sequence":"additional","affiliation":[{"name":"MIT, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,3,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_4"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796303421"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/18M1226737"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77004-6_10"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73951-7_47"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.2001.9990249"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218127407018403"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch27"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/08071990X"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.47"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.02.003"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.78"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/971617.971643"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80013-2"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.72"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00102"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0308210511001648"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti167"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00081"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/0205006"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00022-2"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.67"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972887.9"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972863.13"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72845-0_4"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/1387061.1387065"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3365835"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.17"},{"key":"e_1_3_2_36_2","first-page":"100","volume-title":"Proceedings of the 6th Workshop on Algorithm Engineering and Experiments and the 1st Workshop on Analytic Algorithmics and Combinatorics","author":"Gutman Ronald J.","year":"2004","unstructured":"Ronald J. Gutman. 2004. Reach-based routing: A new approach to shortest path algorithms optimized for road networks. In Proceedings of the 6th Workshop on Algorithm Engineering and Experiments and the 1st Workshop on Analytic Algorithmics and Combinatorics, Lars Arge, Giuseppe F. Italiano, and Robert Sedgewick (Eds.). SIAM, 100\u2013111."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(94)00248-9"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.3.450"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2016.09.001"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1998.0476"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301366"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1038\/35075138"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/321992.321993"},{"issue":"3","key":"e_1_3_2_45_2","first-page":"43","article-title":"Mapping networks of terrorist cells","volume":"24","author":"Krebs V.","year":"2002","unstructured":"V. Krebs. 2002. Mapping networks of terrorist cells. Connections 24, 3 (2002), 43\u201352.","journal-title":"Connections"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1038\/35082140"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00402-X"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702419650"},{"key":"e_1_3_2_52_2","first-page":"87","volume-title":"Interdisciplinary Statistics and Bioinformatics","author":"Pinney J. W.","year":"2006","unstructured":"J. W. Pinney and D. R. Westhead. 2006. Betweenness-based decomposition methods for social and biological networks. In Interdisciplinary Statistics and Bioinformatics. 87\u201390."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488673"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344423"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289527"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72845-0_6"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814635"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646088"},{"key":"e_1_3_2_59_2","article-title":"On some fine-grained questions in algorithms and complexity","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. Proc. of the ICM (2018).","journal-title":"Proc. of the ICM"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/2438645.2438646"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_2_62_2","doi-asserted-by":"crossref","unstructured":"Ryan Williams. 2018. Faster all-pairs shortest paths via circuit complexity. 47 5 (2018) 1965\u20131985.","DOI":"10.1137\/15M1024524"},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.102"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/3186893"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743464"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/567112.567114"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563393","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3563393","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:35Z","timestamp":1750182575000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3563393"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,31]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3563393"],"URL":"https:\/\/doi.org\/10.1145\/3563393","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,31]]},"assertion":[{"value":"2021-09-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}