Convenient Tool for Solving the Prize-Collecting Steiner Tree Problem

The Prize-Collecting Steiner Tree problem asks to find a subgraph connecting a given set of vertices with the most expensive nodes and least expensive edges. Since it is proven to be NP-hard, exact and efficient algorithm does not exist. This package provides convenient functionality for obtaining an approximate solution to this problem using loopy belief propagation algorithm.

pcSteiner

The Steiner tree problem is a well-known combinatorial optimization problem which asks a minimum spanning subtree containing a given subset of vertices (terminals). However, in many practical applications nodes and edges have an additional numerical value which represents their significance. That is where the Prize-Collecting Steiner Tree problem arises: the goal is to find a subgraph connecting all the terminals with the most expensive nodes and least expensive edges. Since this problem is proven to be NP-hard, exact and efficient algorithm does not exist. Loopy belief propagation can be utilised to obtain an approximate solution to this problem [1,2].

Installation

To get the latest version of the package and install it from CRAN run the following command:

install.packages("pcSteiner")

References

1. M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour, and R. Zecchina, "Statistical Mechanics of Steiner Trees". PRL, 2008.
2. I. Biazzo, A. Braunstein and R. Zecchina, "Performance of a cavity-method-based algorithm for the prize-collecting Steiner tree problem on graphs". PRL, 2012.