Title: 
Steiner Problems on Directed Acyclic Graphs

Tsan-sheng Hsu, Kuo-Hui Tsai, Da-Wei Wang
Institute of Information Science,
Academia Sinica, 
Nankang 11529, 
Taipei, Taiwan, ROC
e-mail: tshsu,tsaikh,wdw@iis.sinica.edu.tw

and

D. T. Lee*
Department of Electrical and Computer Engineering 
Northwestern University 
Evanston, IL 60208 
e-mail: dtlee@ece.nwu.edu

*  Supported in part by the National Science Foundation under the 
   Grants CCR-9309743 and INT-9207212, and by the Office of Naval 
   Research under the Grant No. N00014-93-1-0272.

Abstract

In this paper, we consider two variations of the minimum-cost Steiner 
problem on a directed acyclic graph $G(V,E)$ with a non-negative weight 
on each edge of $E$.  The <i>minimum directed Steiner network</i> 
problem is defined as follows.
Given a set of starting vertices $S \subset V$ and a set of terminating 
vertices $T \subset V$, find a subgraph with the minimum total edge 
weight such that for each starting vertex $s$ there exists a path from 
$s$ to a terminating vertex, and for each terminating vertex $t$, there 
exists a path from a starting vertex to $t$.
The <i>minimum union path</i> problem is similar to the minimum directed 
Steiner network problem except that we are given a set of hitting 
vertices $H \subset V$, in addition to the sets of starting and 
terminating vertices and that we want to find a subgraph with the minimum 
total edge weight such that the subgraph satisfies not only the conditions 
above, but also that every hitting vertex is on a path from a starting 
vertex to a terminating vertex.

We present algorithms for finding <i>optimal</i> solutions to these two 
problems in time, respectively, $O(n\cdot m + 2^{|S| + |T|} \cdot \alpha^{3}
\cdot (n^{\alpha - 2} + n^{\beta-1}))$ and 
$O(k! \cdot (8 \cdot k)^k \cdot k^3 \cdot n^{k-1} + n \cdot m)$,
where $n$ and $m$ denote the number of vertices and edges of the graph, 
$\alpha = \max\{|S|, |T|\}$, $\beta = \min\{|S|, |T|\}$, and 
$k = |S| + |T| + |H|$.  The algorithms can also enumerate all possible 
optimal solutions for both problems.

We also give linear time algorithms for some special cases.


Algorithmica, to appear.