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

A.E. Feldmann, J. Könemann, N.K. Olver, L. 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 publicationProceedings of APPROX-RANDOM 2014
EditorsK. Jansen, J.D.P. Rolim, N.R. Devanur, C. Moore
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Pages176-191
ISBN (Print)9783939897743
DOIs
Publication statusPublished - 2014
EventAPPROX -
Duration: 4 Sep 20146 Sep 2014

Conference

ConferenceAPPROX
Period4/09/146/09/14

Fingerprint

Steiner Tree
NP-complete problem
Equivalence
Claw
LP Relaxation
Steiner Tree Problem
Linear Programming Relaxation
Integrality
Independent Set
Approximation Algorithms
Star
Trivial
Complement
Upper bound
Imply
Approximation
Graph in graph theory
Vertex of a graph

Cite this

Feldmann, A. E., Könemann, J., Olver, N. K., & Sanità, L. (2014). On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree. In K. Jansen, J. D. P. Rolim, N. R. Devanur, & C. Moore (Eds.), Proceedings of APPROX-RANDOM 2014 (pp. 176-191). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.176
Feldmann, A.E. ; Könemann, J. ; Olver, N.K. ; Sanità, L. / On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree. Proceedings of APPROX-RANDOM 2014. editor / K. Jansen ; J.D.P. Rolim ; N.R. Devanur ; C. Moore. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2014. pp. 176-191
@inproceedings{d1bf2d7e2bde4f51b619d8eb0045fb29,
title = "On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree",
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.",
author = "A.E. Feldmann and J. K{\"o}nemann and N.K. Olver and L. Sanit{\`a}",
year = "2014",
doi = "10.4230/LIPIcs.APPROX-RANDOM.2014.176",
language = "English",
isbn = "9783939897743",
pages = "176--191",
editor = "K. Jansen and J.D.P. Rolim and N.R. Devanur and C. Moore",
booktitle = "Proceedings of APPROX-RANDOM 2014",
publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",

}

Feldmann, AE, Könemann, J, Olver, NK & Sanità, L 2014, On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree. in K Jansen, JDP Rolim, NR Devanur & C Moore (eds), Proceedings of APPROX-RANDOM 2014. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, pp. 176-191, APPROX, 4/09/14. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.176

On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree. / Feldmann, A.E.; Könemann, J.; Olver, N.K.; Sanità, L.

Proceedings of APPROX-RANDOM 2014. ed. / K. Jansen; J.D.P. Rolim; N.R. Devanur; C. Moore. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2014. p. 176-191.

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

TY - GEN

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

AU - Feldmann, A.E.

AU - Könemann, J.

AU - Olver, N.K.

AU - Sanità, L.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

U2 - 10.4230/LIPIcs.APPROX-RANDOM.2014.176

DO - 10.4230/LIPIcs.APPROX-RANDOM.2014.176

M3 - Conference contribution

SN - 9783939897743

SP - 176

EP - 191

BT - Proceedings of APPROX-RANDOM 2014

A2 - Jansen, K.

A2 - Rolim, J.D.P.

A2 - Devanur, N.R.

A2 - Moore, C.

PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

ER -

Feldmann AE, Könemann J, Olver NK, Sanità L. On the Equivalence of the Bidirected and Hypergraphic Relaxations for Steiner Tree. In Jansen K, Rolim JDP, Devanur NR, Moore C, editors, Proceedings of APPROX-RANDOM 2014. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. 2014. p. 176-191 https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.176