The Maximum Labeled Path Problem

In this paper, we study the approximability of the Maximum Labeled Path problem: given a vertex-labeled directed acyclic graph D, find a path in D that collects a maximum number of distinct labels. For any $$\epsilon >0$$ϵ>0, we provide a polynomial time approximation algorithm that computes a solution of value at least $$OPT^{1-\epsilon }$$OPT1-ϵ and a self-reduction showing that any constant ratio approximation algorithm for this problem can be converted into a PTAS. This last result, combined with the APX-hardness of the problem, shows that the problem cannot be approximated within any constant ratio unless $$P=NP$$P=NP.