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.