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

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 strongly NP-hard to solve exactly, and it is a formidable computation...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 2016-11, Vol.160 (1-2), p.379-406
Main Authors: Feldmann, Andreas Emil, Könemann, Jochen, Olver, Neil, Sanità, Laura
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Calculus of Variations and Optimal Control
Optimization
Combinatorics
Complement
Equivalence
Full Length Paper
Graph theory
Graphs
Linear programming
Mathematical analysis
Mathematical and Computational Physics
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Mathematics of Computing
Numerical Analysis
Polyhedra
Studies
Tasks
Texts
Theoretical
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 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 article, 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 three Steiner neighbours. 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.
ISSN:0025-5610
1436-4646
DOI:10.1007/s10107-016-0987-5