### Abstract

Given a graph G=(V,E) with a cost function c:E→ℝ^{+} and a vertex subset R⊂V, an internal Steiner tree is a Steiner tree that contains all the vertices in R, and such that each vertex in R must be an internal vertex. The internal Steiner tree problem involves finding an internal Steiner tree T whose total cost ∑_{(u,v)∈E(T)}c(u,v) is the minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present a (2ρ+1)-approximation algorithm for solving the problem on complete graphs, where ρ is an approximation ratio for the Steiner tree problem. Currently, the best-known ρ is ln4+ε<1.39. Moreover, for the case where the cost of each edge is restricted to being either 1 or 2, we present a 9/7-approximation algorithm for the problem.

Original language | English |
---|---|

Pages (from-to) | 27-43 |

Number of pages | 17 |

Journal | Journal of Complexity |

Volume | 29 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2013 Feb |

### All Science Journal Classification (ASJC) codes

- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- Mathematics(all)
- Control and Optimization
- Applied Mathematics

## Fingerprint Dive into the research topics of 'The internal Steiner tree problem: Hardness and approximations'. Together they form a unique fingerprint.

## Cite this

*Journal of Complexity*,

*29*(1), 27-43. https://doi.org/10.1016/j.jco.2012.08.005