- INSTANCE: Graph , cost function , set of terminal pairs .
- SOLUTION: A forest such that for all , vertices and are contained in the same connected component of
- COST FUNCTION: .
- OBJECTIVE: Minimize.
*Approx.:*Approximable within [3].*Hardness:*NP-hard to approximate within 96/95 [36].*Comment:*When is a planar graph [9] obtained a PTAS.

2015-04-27 Revision: 288 PDF version