Cross-post from StackOverflow.
I have an undirected, positive-weighted, connected graph with vertices
V and edges
E. I also have a subset
S of vertices. Right now
V contains about 22000 vertices and
E about 23000 edges, but these are expected to go up to about a million for larger inputs.
S, on the other hand, will usually contain fewer than 1000 vertices, and they are relatively close together in the graph.
I want to find the “center” of
S, meaning a vertex
c from which the distance to the furthest vertex in
S is as small as possible. It’s like the graph center but only for a subset of vertices. (Edit:) It’s also a 1-center problem on a graph; the more general k-center problem is NP-hard but this one is probably easier.
Is there an algorithm to find this center efficiently? Ideally, the performance would only depend on
S and its surroundings, and not on the entire graph.
I’ve thought about starting a breadth-first search from all vertices
S simultaneously, stopping when a vertex
v_i has been encountered by all
s_i, but this is more or less
O(|S|²) in both time and memory. It’s probably feasible in this case, but it feels like there might be a better way.