Under Construction

(GSF) Generalized Steiner Forest

Instance: A graph G=(V,E), a weight W(e)>=0 for each e in E.
          A collection of terminal sets T={T1,T2,...,Tt},
          each a subset of V. A subset C of the edges E
Solution: A generalized steiner forest (GSF) i.e.
          for each T_i, and for every pair of terminals x,y in T_i, 
          there exists a path in C connecting x and y
Measure : W(C) (i.e. Sum {W(e): e in C}).

+-----------------------------------------------------------------+
|   The "Local-Ratio Theorem" (oriented for GSF)                  |
+-----------------------------------------------------------------+
|   If   C is 2-approximation GSF w.r.t the weight function W1    |
|   and  C is 2-approximation GSF w.r.t the weight function W2    |
|   then C is 2-approximation GSF w.r.t the weight function W1+W2 |
+-----------------------------------------------------------------+

Our objective is to find a MINIMAL-GSF C, i.e.
C is an GSF, but for each e in C: C-{e} is not GSF.

Observations1: If Ti intersects Tj than we can replace them
              by there union.
Observations2: If W({x,y})=0 We can shrink x and y, use Observation1
               if needed and proceed recursively, after recursion
               in back, "UN-shrink" xy and add it to the forest
               if does not disturb minimality.
Local Ratio Step:
Define W1 to be epsilon HOMOGENEOUS, i.e.
   for all e in E: W1(e) = epsilon*terminal_degree(e) 
   
Where: terminal degree e is the number of e's terminal endpoints.
   
Q1: Every MINIMAL-GSF is 2-approximations w.r.t W1. Why?

   Solve recursively for W2=W-W1 and get 2-approximate GSF, modify
   it to be minimal w.r.t the edges e s.t. W(e)>0 to get MINIMAL-GSF C.

   C is 2-approx w.r.t. W1             (see Q1)
   C is 2-approx w.r.t. W2             (By induction Hyp.)
therefore by the Local-Ratio Theorem:
   C is 2-approx w.r.t. W              (=W1+(W-W1))

p.s. Sanjeev Khanna suggests the following simpler weight
     function: W1(e) = epsilon iff e adjacent to any terminal.
     Now: t<=W1(C)<=2*t is trivial.