How to find all nodes in a graph equidistant from a given set of nodes?

Question

If you have a simple undirected graph G(V,E) and F which is a subset of V. How can you find some node v such that the distance from every node in F to v is the same and the distances are minimized? And just return None if there is no v. I was told this can be done in O(|V|+|E|) complexity.

Assume all edges are of distance 1.

Can anyone explain how this can be done? A pseudo-code would also help.

Answer 1

The solution is similar to BFS, but with a little change:

1. Start with S = F with F nodes marked.

2. Find |S| sets with distance 1 from each element in S (all these sets should contain unmarked nodes). If the intersection of these sets is non-empty, the candidate is found.

3. Take the union of the |S| sets above in S' and mark these nodes. If S' is empty, return 'None'.

4. Return to step 2.

Suppose all the set operations take constant time, then the complexity of the algorithm is same as BFS which is O(|V| + |E|).

Now to reason about the complexity of set operations. My reasoning is that the set operations don't increase the complexity as the union and intersection operations in steps 2 and 3 can be combined to take time O(|S|), and since at every step S is different from S in previous iterations, the overall complexity of set operations would be O(|V|).

Answer 2

Here is one algorithm, in pseudo-code, trying to add comments to explain how it works.

declare explored // a table of all the vertices that can keep track of one number (distance, initialized to -1) and a list of vertex references (origins, initialized to null)
to_explore = S  // fifo queue of vertices to explore

while (to_explore not empty) {
    pop vertex v from to_explore
    current_distance = explored[v].distance
    current_origins = explored[v].origins
    for (vertex n, neighbor of v) {
        if (explored[n].origins contains v)
            continue // we just hit a loop and we're only interested in shortest distances
        if (explored[n].distance == -1) { // first time we come here
            explored[n].distance = current_distance+1
            explored[n].origins = current_origins
            push n to to_explore
            continue
        }
        if (explored[n].distance != current_distance+1) {
            continue // we are merging path from another node of S but different distance, cannot lead to any solution
        }
        // only case left is explored[n].distance == current_distance+1
        // so we've already come here from other place(s) in S with the same distance
        add / merge (without duplicates) origins to explored[n].origins
        if (explored[n].origins = S) // maybe compare the size is enough?
            return n // we found a solution
        // if not , we just continue our exploration, no need to add to the queue since we've already been through here before
    }
}

The idea is that with the FIFO queue, we will explore everything that's at distance 1 from the set S, if we cannot find any solution there, everything at distance 2...etc.. so we'll find the shortest distance first.

I am not completely sure about the complexity, but I believe that in the worst case, we only explore every vertex and every edge only once so that would give O(|E| + |V|). But in some case we visit the same vertex multiple times. Although that does not increase the paths to explore much, I am not sure if there should be a factor |S| somewhere (but if that is just considered like a constant, then it's ok...)

Hope I did not miss anything. Obviously I did not test any of this.... :)

EDIT (reply to comment)

Will your code work for a graph like this? E = ( a, b), (a, c), (a,d) , (b,e), (c,e), (d, e), and my F = { b, c , d}. Say, you start your bfs with a. I suspect, in the end the origins array will only have {a} and therefore the code will return None. – Guru Devanla

In this case, here is what happens:

to_explore is initialized to {b,c,d}
//while (to_explore not empty)
pop one from to_explore (b). to_explore becomes {c,d}
current_distance=0
current_origins={b}
//for (neighbors of b) {
handling 'a' as neighbor of b first
explored[a].distance=1
explored[a].origins={b}
to_explore becomes {c,d,a}
//for (neighbors of b)
handling 'e' as next neighbor of b
explored[e].distance=1
explored[e].origins={b}
to_explore becomes {c,d,a,e}
//while (to_explore not empty)
pop one from to_explore (c). to_explore becomes {d,a,e}
current_distance=0
current_origins={c}
//for (neighbors of c)
handling 'a' as neighbor of c first
explored[a].distance is already 1
explored[a].origins={b,c}
to_explore already contains a
//for (neighbors of c) {
handling 'e' as next neighbor of b
explored[e].distance is already 1
explored[e].origins={b,}
to_explore already contains e
//while (to_explore not empty)
pop one from to_explore (d)
current_distance=0
current_origins={d}
//for (neighbors of d)
handling 'a' as neighbor of d first
explored[a].distance is already 1
explored[a].origins={b,c,d}
that matches F, found a as a solution.