[comp.theory] Directed Steiner tree problem

STAMM@DBNINF5.BITNET (Hermann Stamm) (10/04/90)

I am interested in the following problem
  ( which this time is truely NP-complete ! ) :

------------------------------------------------------------------------------

MINIMUM-DIRECTED-STEINER-TREE (MDStT)

Instance: Strongly connected digraph D=(V,A),
          vertex s \in V, T \subset V, K < |V|

Question: Does there exist a directed Steiner tree S=(V',A') from s into T
          with |A'| <  K ?
                                       *
          ( a subtree S of D, so that s--->t for all t \in T )

------------------------------------------------------------------------------

I have found only two references which handle the above problem, [NAST74] and
[WONG84]. In [WONG84] it is shown, that MDStT is NP-complete.

For the undirected Steiner tree problem there are approximation algorithms
with a worst-case-ratio of 2.

My question now is:

   Is there any approximation algorithm with constant ( or at least
   logarithmic ) worst-case-ratio bound, or, if not, at least in the
   case of a planar digraph D ?

   ( The idea of a Travelling-Salesman tour after the doubling of a minimum
     spanning tree in the proof of the undirected worst-case-ratio bound 2
     does not work in the directed case ! )


Thanks in advance,

Hermann Stamm
Universitaet Bonn
STAMM@DBNINF5.BITNET

------------------------------------------------------------------------------

[NAST74] Nastansky, L. , Selkow, S.M. , Stewart, N.F. ,
         Zeitschrift fuer Operations Research , 1974 , Vol. 18 , pp. 59-67 ,
         Cost-Minimal Trees in Directed Acyclic Graphs

[WONG84] Wong, R.T. ,
         Mathematical Programming , 1984 , Vol. 28 , pp. 271-287 ,
         A Dual Ascent Approach for Steiner Tree Problems on a Directed Graph

------------------------------------------------------------------------------