Approximability of the Minimum Steiner Cycle Problem

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<>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 beta-relaxed triangle inequality is approximable with the ratio beta^2+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 3/2- and a 2/3 log_2 k-approximation algorithm for undirected and directed graphs G=(V,E), respectively. For the case with the beta-relaxed triangle inequality, we present a (beta^2+beta)-approximation algorithm.