How to find the "center" of a subset of vertices in a graph?

Question

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 in V 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 not overly efficient. It's probably feasible in this case, but it feels like there might be a better way.

Answer 1

Here's an approximation algorithm that should offer a decent time-quality trade-off curve. The first part is due to Teofilo F. Gonzalez (Clustering to minimize the maximum intercluster distance, 1985), but I can't find a citation for the second offhand, probably because it's too thin to be a main result.

Let k be the number of times you're willing to run Dijkstra's algorithm (truncated after it reaches all of S, as you suggest). Gonzalez's algorithm runs Dijkstra k − 1 times to partition the terminals S into k clusters so as to 2-approximately minimize the maximum cluster radius. Conveniently, it produces as a byproduct k well-separated centers C and shortest path trees for k − 1 of them. We run Dijkstra one more time and then choose the optimum 1-center with respect to C. This center satisfies

approximate objective ≤ optimal objective + maximum cluster radius.

It's a little tricky to quantify an approximation factor here in terms of k. The key is bounded doubling dimension, which I'll illustrate by assuming Euclidean distances for a moment. Suppose that we're trying to find the 1-center of a disk of radius 1. The optimum is the center of the disk. How many disjoint radius-r balls centered inside the disk can there be? Their area is contained inside a disk of radius (1+r), which has area π(1+r)², so at most (π(1+r)²)/πr² = (1/r + 1)². The maximum cluster radius will be 2r, or in terms of k, on the order of 4/√k times as large as the optimal objective, so k = 100 will give you a solution within about 20% of optimal. Doubling dimension basically uses this argument as a definition.

For reference, Gonzalez's algorithm is

1. Choose any point in S.

2. Repeat k − 1 times: run Dijkstra from the most recently chosen point, choose the next point in S to maximize the minimum distance to all previously chosen points.

Then we run Dijkstra from the most recently chosen point one more time and then select the optimal 1-center for the chosen points.