# The tree augmentation problem, but with hyperlinks

In the (Weighted) Tree Augmentation Problem, we are given a tree $$T = (V,E)$$ and a set of additional edges $$L$$ called links with non-negative costs. Each link $$\ell = (u,v)$$ covers the tree edges along the unique path from $$u$$ to $$v$$ in $$T$$.

Has the following generalization been studied? I am still given a tree $$T = (V,E)$$, but now the links may join more than 2 vertices of $$T$$. Each link $$\ell = \{a_1,\ldots,a_k\}$$ covers the edges of each $$a_i$$-$$a_j$$ path in the tree, for all $$i,j \in [k]$$.

Another way to phrase this is: while the Tree Augmentation Problem involves covering the edges of the tree with paths, my generalization involves covering the edges of the tree with subtrees of the given tree.

Has this problem been studied? Are there upper or lower bounds on its approximability?

Thank you!

• Have you tried showing equivalence to Set Cover? Jun 22 at 2:07
• Ah. Thanks for the pointer :) It is equivalent to Set Cover. Jun 22 at 5:26