*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.