Document Open Access Logo

On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree

Authors Andreas Emil Feldmann, Jochen Könemann, Neil Olver, Laura Sanità

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2014.176.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Andreas Emil Feldmann
Jochen Könemann
Neil Olver
Laura Sanità

Cite As Get BibTex

Andreas Emil Feldmann, Jochen Könemann, Neil Olver, and Laura Sanità. On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 176-191, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.176

Abstract

The bottleneck of the currently best (ln(4) + epsilon)-approximation algorithm for the NP-hard Steiner tree problem is the solution of its large, so called hypergraphic, linear programming relaxation (HYP). Hypergraphic LPs are NP-hard to solve exactly, and it is a formidable computational task to even approximate them sufficiently well.

We focus on another well-studied but poorly understood LP relaxation of the problem: the bidirected cut relaxation (BCR). This LP is compact, and can therefore be solved efficiently. Its integrality gap is known to be greater than 1.16, and while this is widely conjectured to be close to the real answer, only a (trivial) upper bound of 2 is known.

In this paper, we give an efficient constructive proof that BCR and HYP are polyhedrally equivalent in instances that do not have an (edge-induced) claw on Steiner vertices, i.e., they do not contain a Steiner vertex with 3 Steiner neighbors. This implies faster ln(4)-approximations for these graphs, and is a significant step forward from the previously known equivalence for (so called quasi-bipartite) instances in which Steiner vertices form an independent set. We complement our results by showing that even restricting to instances where Steiner vertices induce one single star, determining whether the two relaxations are equivalent is NP-hard.

Subject Classification

Keywords
  • Steiner tree
  • bidirected cut relaxation
  • hypergraphic relaxation
  • polyhedral equivalence
  • approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Borchers and D. Du. The k-Steiner ratio in graphs. SIAM Journal on Computing, 26(3):857-869, 1997. Google Scholar
  2. J. Byrka, F. Grandoni, T. Rothvoß, and L. Sanità. Steiner tree approximation via iterative randomized rounding. Journal of the ACM, 60(1):6:1-6:33, 2013. Google Scholar
  3. D. Chakrabarty, J. Könemann, and D. Pritchard. Hypergraphic LP relaxations for Steiner trees. In International Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 383-396, 2010. Google Scholar
  4. D. Chakrabarty, J. Könemann, and D. Pritchard. Integrality gap of the hypergraphic relaxation of steiner trees: A short proof of a 1.55 upper bound. Operations Research Letters, pages 567-570, 2010. Google Scholar
  5. M. Chlebík and J. Chlebíková. Approximation hardness of the Steiner tree problem on graphs. In Proceedings, Scandinavian Workshop on Algorithm Theory, pages 170-179, 2002. Google Scholar
  6. J. Edmonds. Optimum branchings. Journal of Research of the National Bureau of Standards B, 71B:233-240, 1967. Google Scholar
  7. J. Edmonds. Matroids and the greedy algorithm. Math. Programming, 1:127-136, 1971. Google Scholar
  8. DIMACS Center for Discrete Mathematics and Theoretical Computer Science. 11th DIMACS implementation challenge in collaboration with ICERM: Steiner tree problems. http://dimacs11.cs.princeton.edu/, 2014.
  9. I. Fung, K. Georgiou, J. Könemann, and M. Sharpe. Efficient algorithms for solving hypergraphic steiner tree relaxations in quasi-bipartite instances. CoRR, abs/1202.5049, 2012. Google Scholar
  10. M. X. Goemans and Y. Myung. A catalog of Steiner tree formulations. Networks, 23(1):19-28, 1993. Google Scholar
  11. M. X. Goemans, N. Olver, T. Rothvoß, and R. Zenklusen. Matroids and integrality gaps for hypergraphic steiner tree relaxations. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing (STOC), pages 1161-11762, 2012. Google Scholar
  12. F.K. Hwang, D.S. Richards, and P. Winter. The Steiner tree problem. Monograph in Annals of Discrete Mathematics, 53. Elsevier, 1992. Google Scholar
  13. K. Jain. A factor 2 approximation algorithm for the generalized Steiner network problem. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 448-457, 1998. Google Scholar
  14. R. M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations, pages 85-103. Plenum Press, NY, 1972. Google Scholar
  15. J. Könemann, D. Pritchard, and K. Tan. A partition-based relaxation for Steiner trees. Math. Programming, 127(2):345-370, 2011. Google Scholar
  16. N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30(4):852-865, 1983. Google Scholar
  17. T. Polzin and S. Vahdati-Daneshmand. On Steiner trees and minimum spanning trees in hypergraphs. Operations Research Letters, 31(1):12-20, 2003. Google Scholar
  18. S. Rajagopalan and V. V. Vazirani. On the bidirected cut relaxation for the metric Steiner tree problem. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 742-751, 1999. Google Scholar
  19. D. Warme. Spanning Trees in Hypergraphs with Applications to Steiner Trees. PhD thesis, University of Virginia, 1998. Google Scholar
  20. R. T. Wong. A dual ascent approach for Steiner tree problems on a directed graph. Math. Programming, 28:271-287, 1984. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact