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.
|Title of host publication||Algorithm theory — SWAT 2002 |
|Subtitle of host publication||8th Scandinavian workshop on algorithm theory Turku, Finland, July 3–5, 2002 proceedings|
|Editors||Martti Penttonen , Erik Meineche Schmidt|
|Place of Publication||Berlin|
|Publication status||Published - 2002|
|Name||Lecture Notes in Computer Science|