algorithms – How to find the “center” of a subset of vertices in a graph?

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_i in 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.