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 minimum directed Steiner network 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 minimum union path 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 optimal 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.