Premium
Reduction techniques for the prize collecting Steiner tree problem and the maximum‐weight connected subgraph problem
Author(s) -
Rehfeldt Daniel,
Koch Thorsten,
Maher Stephen J.
Publication year - 2019
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21857
Subject(s) - steiner tree problem , reduction (mathematics) , benchmark (surveying) , solver , mathematics , computer science , tree (set theory) , mathematical optimization , combinatorics , maximum cut , vertex connectivity , focus (optics) , graph , vertex (graph theory) , physics , geometry , geodesy , optics , geography
The concept of reduction has frequently distinguished itself as a pivotal ingredient of exact solving approaches for the Steiner tree problem in graphs. In this article we broaden the focus and consider reduction techniques for three Steiner problem variants that have been extensively discussed in the literature and entail various practical applications: The prize‐collecting Steiner tree problem, the rooted prize‐collecting Steiner tree problem and the maximum‐weight connected subgraph problem. By introducing and subsequently deploying numerous new reduction methods, we are able to drastically decrease the size of a large number of benchmark instances, already solving more than 90% of them to optimality. Furthermore, we demonstrate the impact of these techniques on exact solving, using the example of the state‐of‐the‐art Steiner problem solver SCIP‐Jack .