1
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Have you tried showing equivalence to Set Cover? $\endgroup$
    – Chandra Chekuri
    Jun 22, 2022 at 2:07
  • $\begingroup$ Ah. Thanks for the pointer :) It is equivalent to Set Cover. $\endgroup$
    – Karagounis Z
    Jun 22, 2022 at 5:26

0

Reset to default

Your Answer

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