Steiner Forest with Distances One and Two

• INSTANCE: Graph $G=(V,E)$ , and a collection ${\mathcal R}$ of subsets $R\subseteq V$ called required sets, where ${\bigcup}_{R \in {\mathcal R}} R$ is the set of $terminals$ .

• SOLUTION: A set of unordered node pairs $F$ such that each $R\in {\mathcal R}$ is contained in a connected component of $(V, F)$ .
• COST FUNCTION: $\vert F \cap E\vert+2\vert F-E\vert$ .
• OBJECTIVE: Minimize.

• Approx.: Approximable within $3/2$ [12].
• Hardness: APX- hard.[87],[13]
• Comment: $G$ defines a $\{1,2\}$ -Metric on $V$ where $E$ is the set of node pairs which are at distance one from each other, and all other node pairs are at distance $2$