- INSTANCE:
Undirected multigraph
, set
of pairwise disjoint subsets
of
- SOLUTION:
A set
of pairwise edge-disjoint Steiner forests
for
in
- COST FUNCTION:
(the number of Steiner forests)
- OBJECTIVE:
Maximize.
*Approx.:*APX [81].*Hardness:*NP-hard.*Comment:*If each is -edge-connected in , then there are edge-disjoint -forests in . The best upper bound achieved on is 32. This yields the first polynomial time constant factor approximation algorithm for the Steiner Forest Packing problem. [81]

2015-04-27 Revision: 288 PDF version