On the equivalence of the bidirected and hypergraphic relaxations for steiner tree

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

The bottleneck of the currently best (ln(4)+ε)-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.

Original languageEnglish
Title of host publicationLeibniz International Proceedings in Informatics, LIPIcs
EditorsKlaus Jansen, Cristopher Moore, Nikhil R. Devanur, Jose D. P. Rolim
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages176-191
Number of pages16
ISBN (Electronic)9783939897743
DOIs
Publication statusPublished - 1 Sep 2014
Externally publishedYes
Event17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014 - Barcelona, Spain
Duration: 4 Sep 20146 Sep 2014

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume28
ISSN (Print)1868-8969

Conference

Conference17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014
CountrySpain
CityBarcelona
Period4/09/146/09/14

Keywords

  • Approximation algorithms
  • Bidirected cut relaxation
  • Hypergraphic relaxation
  • Polyhedral equivalence
  • Steiner tree

Fingerprint Dive into the research topics of 'On the equivalence of the bidirected and hypergraphic relaxations for steiner tree'. Together they form a unique fingerprint.

  • Cite this

    Feldmann, A. E., Könemann, J., Olver, N., & Sanità, L. (2014). On the equivalence of the bidirected and hypergraphic relaxations for steiner tree. In K. Jansen, C. Moore, N. R. Devanur, & J. D. P. Rolim (Eds.), Leibniz International Proceedings in Informatics, LIPIcs (pp. 176-191). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 28). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.176