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!

  • 1
    $\begingroup$ Have you tried showing equivalence to Set Cover? $\endgroup$ Commented Jun 22, 2022 at 2:07
  • $\begingroup$ Ah. Thanks for the pointer :) It is equivalent to Set Cover. $\endgroup$ Commented Jun 22, 2022 at 5:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.