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

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10335055" target="_blank" >RIV/00216208:11320/16:10335055 - isvavai.cz</a>

Result on the web

<a href="http://dx.doi.org/10.1007/s10107-016-0987-5" target="_blank" >http://dx.doi.org/10.1007/s10107-016-0987-5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s10107-016-0987-5" target="_blank" >10.1007/s10107-016-0987-5</a>

Result language

angličtina

Original language name

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

Original language description

The bottleneck of the currently best -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 -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.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2016

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Mathematical Programming, Series A

ISSN

0025-5610

e-ISSN

—

Volume of the periodical

160

Issue of the periodical within the volume

1-2

Country of publishing house

DE - GERMANY

Number of pages

28

Pages from-to

379-406

UT code for WoS article

000385191700014

EID of the result in the Scopus database

2-s2.0-84990861372