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. For any \(\epsilon >0\), we provide a polynomial time approximation algorithm that computes a solution of value at least \(OPT^{1-\epsilon }\) 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\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Batten, L.M.: Combinatorics of Finite Geometries. Cambridge University Press, New York (1997)
Broersma, H., Li, X.: Spanning trees with many or few colors in edge-colored graphs. Discuss. Math. Graph Theory 17, 259–269 (1997)
Broersma, H., Li, X., Woeginger, G.J., Zhang, S.: Paths and cycles in colored graphs. Australas. J. Comb. 31, 299–311 (2005)
Brüggemann, T., Monnot, J., Woeginger, G.J.: Local search for the minimum label spanning tree problem with bounded color classes. Oper. Res. Lett. 31, 195–201 (2003)
Chang, R.-S., Leu, S.-J.: The minimum labeling spanning trees. Inf. Process. Lett. 31, 195–201 (2003)
Couëtoux, B., Gourvès, L., Monnot, J., Telelis, O.: Labeled traveling salesman problems: complexity and approximation. Discrete Optim. 7, 74–85 (2010)
Hassin, R., Monnot, J., Segev, D.: Approximation algorithms and hardness results for labeled connectivity problems. J. Comb. Optim. 14, 437–453 (2007)
Hassin, R., Monnot, J., Segev, D.: The complexity of bottleneck labeled graph problems. In: International Workshop on Graph-Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science, vol. 4769. Springer, Berlin (2007)
Håstad, J.: Some optimal inapproximability results. J. ACM 48, 798–859 (2001)
Krumke, S.O., Wirth, H.-C.: Approximation algorithms and hardness results for labeled connectivity problems. Inf. Process. Lett. 66, 81–85 (1998)
Monnot, J.: The labeled perfect matching in bipartite graphs. Inf. Process. Lett. 96, 81–88 (2005)
Acknowledgments
We are grateful to Jérôme Monnot for suggesting the use of a self-reduction to prove the hardness result of Sect. 3.
Author information
Authors and Affiliations
Corresponding author
Additional information
An extended abstract of this paper appeared in the proceedings of the 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG’14.
Rights and permissions
About this article
Cite this article
Couëtoux, B., Nakache, E. & Vaxès, Y. The Maximum Labeled Path Problem. Algorithmica 78, 298–318 (2017). https://doi.org/10.1007/s00453-016-0155-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-016-0155-6