# Approximability of the Tree Augmentation Problem

(suggested by Zeev Nutov)

# Problem Statement

The Tree Augmentation Problem (TAP) is: given a graph with edge costs and a tree (laminar family) on node set , find a min-cost augmenting edge set such that is 2-edge connected. TAP is a particular case of the Min-Cost 2-Edge-Connected Subgraph problem, when the input graph contains a spanning tree of cost zero.

# What is known?

1. The problem admits several 2-approximation algorithms.

2. The integrality gap of a standard cut-LP is in the range [1.5,2].

3. For unit/uniform costs ratio 1.5 is known, but it is not related to the cut-LP.

4. For unit/uniform costs there are several extensions of the cut-LP with integrality gap better than 2.

5. The Relative Greedy heuristic gives ratio in time roughly , where is the diameter of .

# Open questions

Does TAP with arbitrary costs admit ratio better than 2?

Does the cut-LP have integrality gap better than 2 in the case of unit costs?