Exact Algorithms for Group Closeness Centrality
Luca Pascal Staus, Christian Komusiewicz, Nils Morawietz, Frank O. Sommer · Society for Industrial and Applied Mathematics eBooks · 2023
The Group Closeness Centrality problem asks, given a graph G and an integer k, for a vertex set S of size k such that the sum of distances from the vertices of V\S to S is minimal. Being a generalization of the NP-hard Dominating Set problem, Group Closeness Centrality is NP-hard as well and W[2]-hard with respect to k meaning that it presumably has no algorithm with running time f(k)·n