In this talk, we will address two variants of the Graph Search Problem (GSP). Here, we are given a graph with a randomly hidden target. The probability distribution of the location of the target is known by the seeker and his goal is to minimize the expected length of the walk until finding the target.

In the Canadian Traveler Problem, we want to walk from s to t in a graph. However, edges are blocked randomly and we only know whether an edge is present if we visit one of its adjacent vertices. The optimal policy minimizes the expected length of the walk to t. The Canadian Traveler Problem can be considered as a generalization of GSP with multiple targets and failing edges. We study the complexity and approximability of this problem.

We also discuss the Lost Cow Problem, which is a generalization of GSP on the line. Here, the probability distribution can also be non-discrete. For this problem, we will give an overview of interesting results by others and discuss our contribution.