Approximation hardness of the Steiner Tree Problem on graphs

Miroslav Chlebik; Janka Chlebikova

doi:10.1007/3-540-45471-3_18

Approximation hardness of the Steiner Tree Problem on graphs

Miroslav Chlebik, Janka Chlebikova

School of Computing

University of Sussex

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

184 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 language	English
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
Publisher	Springer
Pages	170-179
Volume	2368
ISBN (Electronic)	9783540454717
ISBN (Print)	9783540438663
DOIs	https://doi.org/10.1007/3-540-45471-3_18
Publication status	Published - 2002

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2368
ISSN (Print)	0302-9743

Access to Document

10.1007/3-540-45471-3_18

Steiner Tree Problem post-print
The final publication is available at Springer via http://dx.doi.org/10.1007/3-540-45471-3_18.
Accepted author manuscript (Post-print), 191 KB

Cite this

Chlebik, M., & Chlebikova, J. (2002). Approximation hardness of the Steiner Tree Problem on graphs. In M. Penttonen , & E. Meineche Schmidt (Eds.), Algorithm theory — SWAT 2002 : 8th Scandinavian workshop on algorithm theory Turku, Finland, July 3–5, 2002 proceedings (Vol. 2368, pp. 170-179). (Lecture Notes in Computer Science; Vol. 2368). Springer. https://doi.org/10.1007/3-540-45471-3_18

@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",

}

Chlebik, M & Chlebikova, J 2002, Approximation hardness of the Steiner Tree Problem on graphs. in M Penttonen & E Meineche Schmidt (eds), Algorithm theory — SWAT 2002 : 8th Scandinavian workshop on algorithm theory Turku, Finland, July 3–5, 2002 proceedings. vol. 2368, Lecture Notes in Computer Science, vol. 2368, Springer, Berlin, pp. 170-179. https://doi.org/10.1007/3-540-45471-3_18

Approximation hardness of the Steiner Tree Problem on graphs. / Chlebik, Miroslav; Chlebikova, Janka.
Algorithm theory — SWAT 2002 : 8th Scandinavian workshop on algorithm theory Turku, Finland, July 3–5, 2002 proceedings. ed. / Martti Penttonen ; Erik Meineche Schmidt. Vol. 2368 Berlin: Springer, 2002. p. 170-179 (Lecture Notes in Computer Science; Vol. 2368).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Approximation hardness of the Steiner Tree Problem on graphs

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

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

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

U2 - 10.1007/3-540-45471-3_18

DO - 10.1007/3-540-45471-3_18

M3 - Conference contribution

SN - 9783540438663

VL - 2368

T3 - Lecture Notes in Computer Science

SP - 170

EP - 179

BT - Algorithm theory — SWAT 2002

A2 - Penttonen , Martti

A2 - Meineche Schmidt, Erik

PB - Springer

CY - Berlin

ER -

Chlebik M, Chlebikova J. Approximation hardness of the Steiner Tree Problem on graphs. In Penttonen M, Meineche Schmidt E, editors, Algorithm theory — SWAT 2002 : 8th Scandinavian workshop on algorithm theory Turku, Finland, July 3–5, 2002 proceedings. Vol. 2368. Berlin: Springer. 2002. p. 170-179. (Lecture Notes in Computer Science). doi: 10.1007/3-540-45471-3_18

Approximation hardness of the Steiner Tree Problem on graphs

Abstract

Publication series

Access to Document

Fingerprint

Cite this