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

Andreas Feldmann

Abstract

(Joint work with Jochen Könemann, Neil Olver, and Laura Sanita)

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 strongly 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 work, we give an efficient constructive proof that BCR and HYP are polyhedrally equivalent in instances that do