# Find a vertex that is equidistant to a set of vertices?

I need help with the following problem:

Input: An undirected, unweighted graph $G = (V,E)$ and a set of vertices $F \subseteq V$.

Question: Find a vertex $v$ of $V$ such that the distance from each vertex of $F$ to $v$ is the same and all the distances are minimized? Return None if there is no such $v$.

The runtime should be $O(|V| + |E|)$.

My thoughts were to do a breadth-first search for each vertex in $F$, so for each vertex in $F$, you store all vertices with their distances, then find the intersection of all these.

Is there a better way?

• What have you tried? Since there is no runtime restriction, this task should be trivial. – Raphael Mar 26 '13 at 11:15

Assume $n = |V|, m = |E|, k = |F|$. Solve the SSSP for all $v \in F$ and annotate nodes with the respective distances (time $\Theta(k(n + m))$). Iterate over all nodes and find one all annotations of which are the same and minimal among all candidates (time $\Theta(nk)$).

This can be sped up by using depth-first search to solve the SSSP and executing all $k$ runs in parallel and in phases (by distance), observing the following rules.

• In any given phase, if we find a node in some runs but not in others, remove them from consideration.
• In any given phase, if a node is found in all runs (simultaneously), return it and stop.

Now the runtime depends on the minimal distance to be found and the density of the graph.

• Shouldn't the first $\Theta$ be $\Theta(k(n+m))$? – frafl Mar 26 '13 at 11:56
• @frafl Absolutely. I assumed $k$ to be constant for some reason. – Raphael Mar 26 '13 at 11:57

Starting with $i=0$ and going up, for every $f \in F$ consider a subset of $V$ containing points at the exact distance of $i$ from $f$. Look at intersection of all of those subsets. If you're lucky, as $i$ grows, you'll find this intersection non empty - those will be the solutions.

For the actual implementation, I'd suggest removing vertices closer than $i$ to any of $f$ at every iteration. To find intersection you could simply increment a counter on a vertex, whenever it is included in one of the subsets. When for some vertex v.count = |F|, you are done.

One way to implement it could be as follows

For each v in V, v.count = 0.

For each f in F,
f.subset = {f},
f.count = f.count + 1
if f.count = |F|, return f.

While V is not empty,
For each f in F,
old_subset = f.subset,
f.subset = the set of neighbors of vertices in old_subset,
(consider only vertices in V and not in old_subset)

For each v in old_subset,
if v.count == 1, remove v from V,
else v.count = v.count - 1

For each s in f.subset,
s.count = s.count + 1
if s.count = |F|, return s.

return "no such vertex"


While the running time of the above algorithm depends a lot on chosen graph representation, it can be as good as $O(|V| + |E|)$ assuming that you can find the neighbors of a vertex $v$ and remove it from the graph in $O(\deg(v))$ time. In that case, because $\sum_{v \in V} \deg(v) = 2 |E|$, most of the cost of the algorithm is covered by the $|E|$ term.

• Regarding runtime: consider the complete bipartite graph $K_{k,n}$ and select as $F$ the $k$ nodes on one side. In this case, we clearly have $\Theta(kn)$ effort in the first (and only) iteration. Of course, $|E|=kn$ in this case; if we add all edges among the $n$ nodes, we are in $o(|E|)$, but I think $O(|E|)$ is an upper bound in any case. Convinced! @frafl I think we have given the same answer in multiple forms. ;) – Raphael Mar 28 '13 at 10:03
• Suppose there are many equidistant nodes, how does this get the shortest one? (i.e. the distance from that node to any node in F is minimized) – omega Mar 29 '13 at 17:58
• @omega, the algorithm considers sets $V_{f, i}$ of all vertices at distance $i$ from $f$. First $\cap_{f \in F}V_{f, 0}$ is checked. If there is no solution at distance $0$, then $\cap_{f \in F}V_{f, 1}$ is checked and etc. No vertices are ever skipped, none are ever removed before checking them. There is nothing that could make a farther solution pop up before a nearer one does. – Karolis Juodelė Mar 29 '13 at 19:04
• No more comments, add this to the and several stuff to the answer! – frafl Mar 29 '13 at 19:30
• @omega, Raphael, I now see that my implementation in indeed not $O(|V| + |E|)$. Consider a tree as this, but with a longer path between $4$ and $5$. It is counterexample with $F = {1, 2, 3, 6}$. Because node $4$ belongs in the subsets of each of nodes $1$, $2$, $3$, it, along with half of the nodes between $4$ and $5$, will be processed $3$ times. This should be solvable. I'll think about it... – Karolis Juodelė Mar 30 '13 at 7:49

One easy but most likely not most efficient approach is this:

1. Reorder the vertices such that all vertices in $F$ come first.
2. Use the Floyd-Warshall algorithm to compute the Matrix $M$ of all distances.
3. Look at all columns where the first $|F|$ entries contain the same value $k$ and choose the one with the minimal $k$.

The worst case runtime is in $\mathcal{O}(|V|^3)$, since it's dominated by the Floyd-Warschall algorithm.

Another algorithm:

1. Let $M$ be the adjacency matrix of $G$ (again with the vertices in $F$ first)
2. If $F=\{v\}$ return $v$, if $F=\emptyset$ return an arbitrary $v \in V$, now $|F|>1$, so we know $v \notin F$.
3. Compute $M^i=MM^{i-1}$ and flag every $v \in V\setminus F$ s.t. some but not all of the first $F$ rows are nonzero (i.e. there is a path of length $i$). Such a vertex can't be $v$ since at least 2 distances differ.
4. Stop if you found a non flagged vertex $v$ that has all entries in the first $|F|$ rows nonzero and return $v$ or if all vertices in $V\setminus F$ are flagged and return "no such $v$ exists".

Note that we don't need the actual $M^i$ so we can speed up the expensive matrix multiplication to some extent.