On the equivalence of the bidirected and hypergraphic relaxations for Steiner tree (Q344954): Difference between revisions

The paper improves recent result of \textit{J. Byrka} et al. [J. ACM 60, No. 1, Article No. 6, 33 p. (2013; Zbl 1281.68234)]: an \((\ln(4)+\epsilon)\)-approximation algorithm for the Steiner tree problem which is based on a hypergraphic linear programming relaxation (HYP). The authors employ another well-studied LP relaxation of the problem, the bidirected cut relaxation (BCR), which is compact, and can therefore be solved more efficiently than the HYP. The principal result of this paper is 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 three Steiner neighbours. It is not quite possible to prove a generic polyhedral equivalence of BCR and HYP: the authors prove that even for instances where Steiner vertices induce one single star, determining whether the two relaxations are equivalent, is NP-hard.