One neat idea is instead of starting the search from one node, start from both and see when the two search spaces meet. If the distance between two nodes is k and the average branching factor in the network is p then we explore O(p^(k/2)) nodes instead of O(p^k) nodes.
h2. Additional problems

1. Friend of a friend(inteview question): Given two user names in a social network find an easy way to test if one is a friend of a friend of the other.
2. Equal partition: Given a set A of 40 real numbers, find out if there is any way to split A in two sets such that the sums of their elements are equal. (O(2^n))
3. Minimal vertex cover: Given a graph of n nodes (n <= 30), find out a set with the smallest number of vertices such that each edge in the  graph has at least one node inside the set. (O(3^n/2))