optimal way to calculate all nodes at distance less than k from m given nodes

Question

A graph of size n is given and a subset of size m of it's nodes is given . Find all nodes which are at a distance <=k from ALL nodes of the subset .

eg . A->B->C->D->E is the graph , subset = {A,C} , k = 2.

Now , E is at distance <=2 from C , but not from A , so it should not be counted .

I thought of running Breadth First Search from each node in subset , and taking intersection of the respective answers .
Can it be further optimized ?

I went through many posts on SO , but they all direct to kd-trees which i don't understand , so is there any other way ?

Answer 1

I can think of two non-asymptotic (I believe) optimizations:

1. If you're done with BFS from one of the subset nodes, delete all nodes that have distance > k from it
2. Start with the two nodes in the subset whose distance is largest to get the smallest possible leftover graph

Of course this doesn't help if k is large (close to n), I have no idea in that case. I am positive however that k/d trees are not applicable to general graphs :)