Search for: All records

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. Differentcentralitymeasures have been proposed to capture the notion of node importance. For example, thecenterof a graph is a node that minimizes the maximum distance to any other node (the latter distance is theradiusof the graph). Themedianof a graph is a node that minimizes the sum of the distances to all other nodes. Informally, thebetweenness centralityof a nodewmeasures the fraction of shortest paths that havewas an intermediate node. Finally, thereach centralityof a nodewis the smallest distancersuch that anys-tshortest path passing throughwhas eithersortin the ball of radiusraroundw. 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 numbernof nodes in the input graph. It is open whether these problems admit truly subcubic algorithms, i.e., algorithms with running time Õ(n^3-δ) for some constant δ > 0.¹ 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 areequivalent under subcubic reductionsto 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. On the positive side, our reductions for Reach Centrality imply an improved Õ(Mn^ω)-time algorithm for this problem in case of non-negative integer weights upper bounded byM, where ω is a fast matrix multiplication exponent. 

In the Euclidean k-Means problem we are given a collection of n points D in an Euclidean space and a positive integer k. Our goal is to identify a collection of k points in the same space (centers) so as to minimize the sum of the squared Euclidean distances between each point in D and the closest center. This problem is known to be APX-hard and the current best approximation ratio is a primal-dual 6.357 approximation based on a standard LP for the problem [Ahmadian et al. FOCS'17, SICOMP'20]. In this note we show how a minor modification of Ahmadian et al.'s analysis leads to a slightly improved 6.12903 approximation. As a related result, we also show that the mentioned LP has integrality gap at least (16+Sqrt(5))/15 > 1.2157. .