Advertisement
Published in:
2014 | OriginalPaper | Chapter
The Maximum Labeled Path Problem
Authors : Basile Couëtoux, Elie Nakache, Yann Vaxès
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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. Our main results are a \(\sqrt{OPT}\)-approximation algorithm for this problem 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 a constant ratio unless \(P=NP\).