From: Saurabh Sethia <saurabh@ams.sunysb.edu>

                Steiner tree problem with minimum number of
                  Steiner points and bounded edge-length


This problem has been studied by Guo-Hui Lin and Guoliang Xue in their
paper in a recent issue of Info. processing letters.

The problem asks for a tree interconnecting a given set of n terminal points
and a minimum number of Steiner points such that the Euclidean length of each
edge is no more than a given positive constant.  This problem has applications
in VLSI design, WDM optimal networks and wireless communications.

They prove that the problem is NP-complete and present a polynomial time
approximation algorithm whose worst-case performance ratio is 5.

Their approximation algorithm is pretty simple and it seems that there is lot
of scope to be clever.  So let's find out if we can be clever and bring down
the performance ratio.

The paper is just four pages and some of you may even look at
it before coming. It's in IPL v.69, Jan 1999 pp.53-57 and is available in
CS library.

-------------------- Notes by Estie Arkin -----------------------------------

We describe a graph version of the problem:

Instance: Graph $G=(V,E)$, a subset $R\subset V$, and an integer $k$.

Question: Is there a subtree of $G$ that includes all vertices of $R$
and such that at most $B$ vertices of $V\setminus R$ are used?

Comment: We know the problem is NP-complete, since the geometric
version is NP-complete. Note that I am assuming that only the edges
``short enough'' actually exist in the graph.

We show that this problem is as hard to approximate as set cover,
which also gives an alternative proof of the NP-completeness of this
version. This means that the problem can be approximated to within a
log factor, but no better, unless $P=NP$ (or something like that?)

The set cover problem is:

Instance: Collection $C$ of subsets of a finite set $S$, positive integer $k$.

Question: Does $C$ contain a cover for $S$ of size $k$ or less, i.e.,
a subset $C'\subseteq C$ such that every element of $S$ belongs to at
least one member of $C'$?

We reduce set cover to our problem: Create a graph with a node in $R$
for each element of $S$, and a node in $V\setminus R$ for each set in
$C$. Every set node is connected by an edge to the element nodes that
belong to it. Also, every pair of set nodes is connected by an edge. A
set cover $C'$ corresponds to a tree containg all nodes of $R$ and
those set nodes of $V\setminus R$ which are in the set cover. Thus, a
set cover of size $k$ exists if and only if a subtree with at most $k$
Steiner nodes (nodes in $V\setminus R$) exists.