On the bidirected cut relaxation for the metric Steiner tree problem

Abstract

We give the first algorithmic result using the bidirected cut relaxation for the metric Steiner tree problem: a 3/2+ε factor approximation algorithm, for any ε>0, for the special case of quasi-bipartite graphs; these are graphs that do not have edges connecting pairs of Steiner vertices. This relaxation is conjectured to have integrality gap close to 1; the worst example known has integrality gap of 8/7. Our result places an upper bound of 3/2 on the integrality gap, for the special class of quasi-bipartite graphs. Part of the difficulty of designing an algorithm using the bidirected cut relaxation arises from edges connecting pairs of Steiner vertices. Restricting to quasi-bipartite graphs enables us to finesse this difficulty and address the rest of the aspects of the problem. The progress reported in this paper is quite similar to that made on the matching problem by restricting to bipartite graphs, thereby finessing the difficulty created by odd cycles.