In this talk, we will address three variants of the Graph Search Problem (GSP). Here, we are given a graph with 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.

The Canadian Traveler Problem is a generalization of this problem with multiple targets and failing edges. We study the complexity and approximation of this problem. Another variant is the Lost Cow Problem, which can be considered as a continuous version of GSP on the line, i.e. there is a continuous probability density function for the location of the target. For this problem, we will give an overview of interesting results by others and discuss our contribution. Finally, the GSP with a uniform distribution over its edges is called the Chinese Repairman Problem, and will be discussed shortly.