A Better-Than-2 Approximation for the Directed Tree Augmentation Problem

We introduce and study a directed analogue of the weighted Tree Augmentation Problem (WTAP). In the weighted Directed Tree Augmentation Problem (WDTAP), we are given an oriented tree $T = (V,A)$ and a set of directed links $L \subseteq V \times V$ with positive costs. The goal is to select a minimum cost set of links which enters each fundamental dicut of $T$ (cuts with one leaving and no entering tree arc). WDTAP captures the problem of covering a cross-free set family with directed links. It can also be used to solve weighted multi 2-TAP, in which we must cover the edges of an undirected tree at least twice. WDTAP can be approximated to within a factor of 2 using standard techniques. We provide an improved ($1.75 + \varepsilon$)-approximation algorithm for WDTAP in the case where the links have bounded costs, a setting that has received significant attention forWTAP. To obtain this result, we discover a class of instances, called “willows”, for which the natural set covering LP is an integral formulation. We further introduce the notion of “visibly $k$-wide” instances which can be solved exactly using dynamic programming. Finally, we show how to leverage these tractable cases to obtain an improved approximation ratio via an elaborate structural analysis of the tree.