PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
The problem is NP-hard since it captures the difficulty of determining if a directed graph has a hamiltonian path or not. It is known as the “Orienteering Problem” in research literature. If the underlying graph was undirected, then for any constant c > 2 it is possible to approximate the optimum solution within a factor c in polynomial time [1]. However, in directed graphs (as in this problem), the situation is much more difficult.
Say the optimum solution visits K distinct nodes. In directed graphs, there is a polynomial time approximation algorithm that finds a solution within an O(log^2 K)-factor of K. If one allows “quasi-polynomial” running time (e.g. n^{log n}… the quasi means that while the exponent is not a constant, it still grows fairly slowly), then it is possible to find a solution within an O(log K)-factor of K [2]. An important research problem is whether this approximation guarantee can be achieved in true polynomial time.
This problem is also very well studied from the operations research viewpoint. A number of heuristics have been presented for solving the problem. See, for example, [3] and related articles.
[1] Improved Algorithms for Orienteering and Related Problems, Chandra Chekuri, Nitish Korula, and Martin Pal, To Appear in Transactions on Algorithms. Preliminary version appeared in Symposium on Discrete Algorithms (SODA), 2008. [2] A Recursive Greedy Algorithm for Walks in Directed Graphs, Chandra Chekuri and Martin Pal, Appeared in Symposium on Theory of Computing (STOC), 2005. [3] Metaheuristics for the Orienteering Problem, Yun-Chia L., Kulturel-Konak, S., Smith, A.E., Appeared in Congress on Evolutionary Computation (CEC), 2002.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.