@inproceedings{fdf57c54f70d4337a40df36f49e90ced,

title = "Approximation hardness of the Steiner Tree Problem on graphs",

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{\aa}stad{\textquoteright}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.",

author = "Miroslav Chlebik and Janka Chlebikova",

note = "The final publication is available at Springer via http://dx.doi.org/[10.1007/3-540-45471-3_18]”.",

year = "2002",

doi = "10.1007/3-540-45471-3_18",

language = "English",

isbn = "9783540438663",

volume = "2368",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "170--179",

editor = "{Penttonen }, Martti and {Meineche Schmidt}, Erik",

booktitle = "Algorithm theory — SWAT 2002",

}