Minimum-Cost 2-Edge-Connected Augmentation of Tree with Constant Radius

• INSTANCE: Graph $G=(V,E)$ , edge costs $c: E \rightarrow \mathbb{R}^+$ , a tree $F$ on $V$ disjoint to $E$ .
• SOLUTION: A tree $T=(V_{T}, E_{T})$ in G such that $V_{T} \subseteq V$ , $E_{T} \subseteq E$ , and $T \cup F$ is 2-edge-connected.
• COST FUNCTION: $\sum_{e \in E_{T}}c(e)$
• OBJECTIVE: Minimize.
• Approx.: Approximable within $1 + ln(2)$ [38].

• Hardness: NP-hard to approximate for trees with radius $\geq 2$ [50].