Abstract
Steiner tree problem in weighted graphs seeks a minimum weight subtree containing a given subset of the vertices (terminals). We show that it is NP-hard to approximate the Steiner tree problem within 96/95. Our inapproximability results are stated in parametric way and can be further improved just providing gadgets and/or expanders with better parameters. The reduction is from Håstad’s inapproximability result for maximum satisfiability of linear equations modulo 2 with three unknowns per equation. This was first used for the Steiner tree problem by Thimm whose approach was the main starting point for our results.
The second author has been supported by the EU-Project ARACNE, Approximation and Randomized Algorithms in Communication Networks, HPRN-CT-199-00112.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification an hardness of approximation problems. Proceedings of the 33rd Annual Symposium on Fundations of Computer Science, 1992, 14–23.
Bern, M., Plassmann, P.: The Steiner Problem with edge lengths 1 and 2. Information Processing Letters 32 (1989) 171–176
Chun, F. R. K.: Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, American Mathematical Society, 1997, ISSN 0160-7642, ISBN 0-8218-0315-8.
Håstad, J.: Some optimal inapproximability results. Proceedings of the 28rd Annual Symposium on Theory of Computing, ACM, 1997.
Hougardy, S., Gröpl, C., Nierhoff, T., Prömel, H. J.: Approximation algorithms for the Steiner tree problem in graphs. In Steiner Trees in Industry, (X. Cheng and D.-Z. Du, eds.), Kluwer Academic Publishers, 2001, 235–279.
Karp, R. M.: Reducibility among combinatorial problems, In Complexity of Computer Computations, (Proc. Sympos. IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), New York: Plenum 1972, 85–103.
Papadimitriou, C. H., Vempala, S.: On the Approximability of the Traveling Salesman Problem. Proceedings of the 32nd ACM Symposium on the theory of computing, Portland, 2000.
Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms 2000, 770–779.
Thimm, M.: On the Approximability of the Steiner Tree Problem. Proceedings of the 26th International Symposium, MFCS 2001 Mariánske Lázne, Czech Republic, August 27–31, 2001, Springer, Lecture Notes in Computer Science 2136 (2001) 678–689.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chlebík, M., Chlebíková, J. (2002). Approximation Hardness of the Steiner Tree Problem on Graphs. In: Penttonen, M., Schmidt, E.M. (eds) Algorithm Theory — SWAT 2002. SWAT 2002. Lecture Notes in Computer Science, vol 2368. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45471-3_18
Download citation
DOI: https://doi.org/10.1007/3-540-45471-3_18
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43866-3
Online ISBN: 978-3-540-45471-7
eBook Packages: Springer Book Archive