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\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
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. Aust. 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. IPL 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: Brandstädt, A., Kratsch, D., Müller, H. (eds.) WG 2007. LNCS, vol. 4769, pp. 328–340. Springer, Heidelberg (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. IPL 66, 81–85 (1998)
Monnot, J.: The labeled perfect matching in bipartite graphs. IPL 96, 81–88 (2005)
Acknowledgment
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
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Couëtoux, B., Nakache, E., Vaxès, Y. (2014). The Maximum Labeled Path Problem. In: Kratsch, D., Todinca, I. (eds) Graph-Theoretic Concepts in Computer Science. WG 2014. Lecture Notes in Computer Science, vol 8747. Springer, Cham. https://doi.org/10.1007/978-3-319-12340-0_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-12340-0_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12339-4
Online ISBN: 978-3-319-12340-0
eBook Packages: Computer ScienceComputer Science (R0)