Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP | Algorithmica Skip to main content
Springer Nature Link
Log in

Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

In Part I, we study a special case of the unweighted Tree Augmentation Problem (TAP) via the Lasserre (Sum of Squares) system. In the special case, we forbid so-called stems; these are a particular type of subtree configuration. For stemless TAP, we prove that the integrality ratio of an SDP relaxation (the Lasserre tightening of an LP relaxation) is \(\le \frac{3}{2}+\epsilon \), where \(\epsilon >0\) can be any small constant. We obtain this result by designing a polynomial-time algorithm for stemless TAP that achieves an approximation guarantee of \(\left( \frac{3}{2}+\epsilon \right) \) relative to the SDP relaxation. The algorithm is combinatorial and does not solve the SDP relaxation, but our analysis relies on the SDP relaxation. We generalize the combinatorial analysis of integral solutions from the previous literature to fractional solutions by identifying some properties of fractional solutions of the Lasserre system via the decomposition result of Karlin et al. (Integer programming and combinatoral optimization (IPCO), Lecture Notes in Computer Science, vol 6655. Springer, Berlin/Heidelberg, pp 301–314, 2011). Also, we present an example of stemless TAP such that the approximation guarantee of \(\frac{3}{2}\) is tight for the algorithm. In Part II of this paper, we extend the methods of Part I to prove the same results relative to the same SDP relaxation for TAP.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

Notes

  1. In other words, a link covers every tree-edge in the unique path of T between the ends of the link.

  2. A preliminary version of our paper with a weaker approximation guarantee for TAP relative to the same SDP relaxation was circulated widely in July 2014, see [1], and it led to subsequent publications by others, e.g., [15], but we prefer to avoid discussion on these matters and we leave it to the subsequent publications.

  3. Although we defined \(\textsc {Las}_t({ LP}_0)\) to be a set of vectors in \(\mathbb {R}^{2^{[|E|]}}\), in what follows, we abuse the notation and take \(\textsc {Las}_t({ LP}_0)\) to be the projection on the subspace indexed by the singleton sets; thus, we take \(\textsc {Las}_t({ LP}_0)\) to be a set of vectors in \(\mathbb {R}^{{|E|}}\).

  4. Recall that \(\mathcal {R}\) is the set of original non-leaf nodes of T; thus \(V(T'_v)\cap \mathcal {R}\) denotes the set of nodes of \(T'_v\) excluding all leaves and all compound nodes.

References

  1. Cheriyan, J., Gao, Z.: Approximating (unweighted) tree augmentation via lift-and-project (Part 0: \(1.8+{\epsilon }\) approximation for (unweighted) TAP). CoRR arXiv:1604.00708 (2016)

  2. Cheriyan, J., Jordán, T., Ravi, R.: On 2-coverings and 2-packings of laminar families. In: Proceedings, European Symposium on Algorithms, pp. 510–520 (1999). A longer version is on the web: http://www.math.uwaterloo.ca/~jcheriyan/publications.html

  3. Cheriyan, J., Karloff, H.J., Khandekar, R., Könemann, J.: On the integrality ratio for tree augmentation. Oper. Res. Lett. 36(4), 399–401 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  4. Cohen, N., Nutov, Z.: A (1 + ln 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius. Theor. Comput. Sci. 489–490, 67–74 (2013)

    Article  MATH  Google Scholar 

  5. Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2010)

    Google Scholar 

  6. Even, G., Feldman, J., Kortsarz, G., Nutov, Z.: A 3/2-approximation algorithm for augmenting the edge-connectivity of a graph from 1 to 2 using a subset of a given edge set. In: Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, APPROX-RANDOM 2001, Proceedings. Lecture Notes in Computer Science, vol. 2129, pp. 90–101 (2001)

  7. Fiorini, S., Mutsanas, N.: Notes on the tree augmentation problem. Personal Communication (2011)

  8. Frederickson, G.N., Ja’Ja’, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10(2), 270–283 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  9. Georgiou, K.: Tree augmentation. Personal Communication (2011)

  10. Even, G., Feldman, J., Kortsarz, G., Nutov, Z.: A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. ACM Trans. Algorithms 5, 21:6–21:17 (2009)

    Article  MathSciNet  Google Scholar 

  11. Nagamochi, H.: An approximation for finding a smallest 2-edge connected subgraph containing a specified spanning tree. Discrete Appl. Math. 126, 83–113 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  12. Jain, K.: A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21(1), 39–60 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  13. Karlin, A.R., Mathieu, C., Nguyen, C.T.: Integrality gaps of linear and semi-definite programming relaxations for Knapsack. In: Integer Programming and Combinatoral Optimization. Lecture Notes in Computer Science, vol. 6655. Springer, Berlin/Heidelberg, pp. 301–314 (2011)

  14. Kortsarz, G., Krauthgamer, R., Lee, J.R.: Hardness of approximation for vertex-connectivity network design problems. SIAM J. Comput. 33(3), 704–720 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  15. Kortsarz, G., Nutov, Z.: LP-relaxations for tree augmentation. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX-RANDOM 2016, September 7–9, 2016, Paris, France, pp. 13:1–13:16 (2016)

  16. Kortsarz, G., Nutov, Z.: A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. ACM Trans. Algorithms 12(2), 23 (2016)

    MathSciNet  Google Scholar 

  17. Lasserre, J.B.: An explicit equivalent positive semidefinite program for nonlinear 0–1 programs. SIAM J. Optim. 12(3), 756–769 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  18. Maduel, Y., Nutov, Z.: Covering a laminar family by leaf to leaf links. Discrete Appl. Math. 158(13), 1424–1432 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  19. Rothvoß, T.: Directed Steiner tree and the Lasserre hierarchy. CoRR arXiv:1111.5473 (2011)

  20. Rothvoß, T.: The Lasserre hierarchy in approximation algorithms. MAPSP Tutorial: Lecture Notes http://www.math.washington.edu/~rothvoss/lecturenotes/lasserresurvey.pdf (2013)

Download references

Acknowledgements

We thank André Linhares for many discussions. We thank several other colleagues who read preliminary drafts and gave us insightful comments.

Funding was provided by Natural Sciences and Engineering Research Council of Canada (Grant No. RGPIN-2014-04351).

Author information

Authors and Affiliations

  1. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, N2L3G1, Canada

    Joseph Cheriyan & Zhihan Gao

Authors
  1. Joseph Cheriyan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Zhihan Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Joseph Cheriyan.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cheriyan, J., Gao, Z. Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP. Algorithmica 80, 530–559 (2018). https://doi.org/10.1007/s00453-016-0270-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-016-0270-4

Keywords

Search

Navigation