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