<p>In the (Weighted) Tree Augmentation Problem, we are given a tree <span class="math-container">$T = (V,E)$</span> and a set of additional edges <span class="math-container">$L$</span> called links with non-negative costs. Each link <span class="math-container">$\ell = (u,v)$</span> covers the tree edges along the unique path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span> in <span class="math-container">$T$</span>.</p>
<p>Has the following generalization been studied? I am still given a tree <span class="math-container">$T = (V,E)$</span>, but now the links may join more than 2 vertices of <span class="math-container">$T$</span>. Each link <span class="math-container">$\ell = \{a_1,\ldots,a_k\}$</span> covers the edges of each <span class="math-container">$a_i$</span>-<span class="math-container">$a_j$</span> path in the tree, for all <span class="math-container">$i,j \in [k]$</span>.</p>
<p>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.</p>
<p>Has this problem been studied? Are there upper or lower bounds on its approximability?</p>
<p>Thank you!</p>

CC BY-SA 4.0
2022-06-22T02:07:46.813Z
Have you tried showing equivalence to Set Cover?
Chandra Chekuri
CC BY-SA 4.0
2022-06-22T05:26:45.717Z
Ah. Thanks for the pointer :) It is equivalent to Set Cover.
Karagounis Z
<reference-request><graph-theory><co.combinatorics><approximation-algorithms><optimization>
The tree augmentation problem, but with hyperlinks
Karagounis Z
# The tree augmentation problem, but with hyperlinks

(Asked by: username_0 on 2022-06-21)

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!

**Tags:** reference-request, graph-theory, co.combinatorics, approximation-algorithms, optimization
> **Comments:**
> **username_1**: Have you tried showing equivalence to Set Cover?  
> **username_0**: Ah. Thanks for the pointer :) It is equivalent to Set Cover.  

---

## 0 answers

