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.

Abstract Let $$D\,=\,(V,A)$$ D = ( V , A ) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected. We study the lattice theoretic properties of the integer points contained in a proper face F of P not contained in $$\{x:x_a=i\}$$ { x : x a = i } for any $$a\in A,i\in \{0,1\}$$ a ∈ A , i ∈ { 0 , 1 } . We prove under a mild necessary condition that $$F\cap \{0,1\}^A$$ F ∩ { 0 , 1 } A contains an integral basis B, i.e., B is linearly independent, and any integral vector in the linear hull of F is an integral linear combination of B. This result is surprising as the integer points in F do not necessarily form a Hilbert basis. In proving the result, we develop a theory similar to Matching Theory for degree-constrained dijoins in bipartite digraphs. Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say $$\tau $$ τ , is equal to the maximum number of disjoint dijoins. We prove a relaxation of this conjecture, by finding for any prime number $$p\,\ge \,2$$ p ≥ 2 , a p-adic packing of dijoins of value $$\tau $$ τ and of support size at most 2|A|. We also prove that the all-ones vector belongs to the lattice generated by $$F\cap \{0,1\}^A$$ F ∩ { 0 , 1 } A , where F is the face of P satisfying $$x(\delta ^+(U))=1$$ x ( δ + ( U ) ) = 1 for every minimum dicut $$\delta ^+(U)$$ δ + ( U ) .