title: How to find the "center" of a subset of vertices in a graph?
body: <p>I have an undirected, positive-weighted, connected graph with vertices <code>V</code> and edges <code>E</code>. I also have a subset <code>S</code> of vertices. Right now <code>V</code> contains about 22000 vertices and <code>E</code> about 23000 edges, but these are expected to go up to about a million for larger inputs. <code>S</code>, on the other hand, will usually contain fewer than 1000 vertices, and they are relatively close together in the graph.</p>
  <p>I want to find the &quot;center&quot; of <code>S</code>, meaning a vertex <code>c</code> in <code>V</code> from which the distance to the furthest vertex in <code>S</code> is as small as possible. It's like the <a href="https://en.wikipedia.org/wiki/Graph_center" rel="nofollow noreferrer">graph center</a> but only for a subset of vertices. [Edit:] It's also a <a href="https://en.wikipedia.org/wiki/1-center_problem" rel="nofollow noreferrer">1-center problem</a> on a graph; the more general <em>k</em>-center problem is NP-hard but this one is probably easier.</p>
  <p>Is there an algorithm to find this center efficiently? Ideally, the performance would only depend on <code>S</code> and its surroundings, and not on the entire graph.</p>
  <p>I've thought about starting a breadth-first search from all vertices <code>s_i</code> in <code>S</code> simultaneously, stopping when a vertex <code>v_i</code> has been encountered by all <code>s_i</code>, but this is not overly efficient. It's probably feasible in this case, but it feels like there might be a better way.</p>