Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems

This article introduces new reduction techniques for the Steiner tree problem in graphs (SPG) and one of its most popular relatives, the maximum-weight connected subgraph problem. Several of the techniques generalize previous results from the literature. In particular, we introduce a generalization of the Steiner bottleneck distance—the arguably most important reduction concept for SPG. While several methods require to solve NP-hard problems, relaxations allow for a strong practical efficiency of these techniques. Initial computational tests with the exact Steiner tree solver SCIP-Jack show a significant improvement of the preprocessing strength.

Article

Download

View PDF