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?

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.

StackExchange Computer Science Q#10794, answer score: 5