Approximation hardness of the Steiner Tree Problem on graphs

Miroslav Chlebik, Janka Chlebikova

Research output: Chapter in Book/Report/Conference proceedingConference contribution

123 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationAlgorithm theory — SWAT 2002
Subtitle of host publication8th Scandinavian workshop on algorithm theory Turku, Finland, July 3–5, 2002 proceedings
EditorsMartti Penttonen , Erik Meineche Schmidt
Place of PublicationBerlin
PublisherSpringer
Pages170-179
Volume2368
ISBN (Electronic)9783540454717
ISBN (Print)9783540438663
DOIs
Publication statusPublished - 2002

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2368
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'Approximation hardness of the Steiner Tree Problem on graphs'. Together they form a unique fingerprint.

Cite this