Abstract

In this paper, we consider variants of a new problem that we call minimum Steiner cycle problem (SCP). The problem is defined as follows. Given is a weighted complete graph and a set of terminal vertices. In the SCP problem, we are looking for a minimum-cost cycle that passes through every terminal exactly once and through every other vertex of the graph at most once. We show that, if P neq NP, there is no approximation algorithm for SCP on directed graphs with an approximation ratio polynomial in the input size. Moreover, this result holds even in the case when the number of terminals is 4. On the contrary, we show that SCP on undirected graphs with constant number of terminals and edge costs satisfying the relaxed triangle inequality is approximable with the ratio beta2+ beta. When the number of terminals k is a part of the input, the problem is obviously a generalization of TSP. For the metric case, we present a frac32- and a frac23łog 2 k-approximation algorithm for undirected and directed graphs G=(V,E), respectively. For the case with the relaxed triangle inequality, we present a ( beta2+ beta)-approximation algorithm.

Keywords

MSC

68Q25, 68W25, 68W40

Cite this article

@article{cai-11079,
  author  = {Monika Steinová},
  title   = {Approximability of the Minimum Steiner Cycle Problem},
  journal = {Computing and Informatics},
  volume  = {29},
  number  = {6+},
  pages   = {1349--1357},
  year    = {2010},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2010/6%2B/approximability-of-the-minimum-steiner-cycle-problem/}
}
Download .bib