In the PCSPG problem, the input is a graph with a subset of its vertices marked as terminals. Each edge has a nonnegative cost, and each terminal a nonnegative penalty. The goal is to find a tree of minimum weight, given by the sum of its edge costs plus the penalties associated with the terminals that are not spanned by the tree.
The following instances have been made available for the challenge by Mauricio Resende:
The following instances, tested by Biazzo et al. (2013), have been made available for the challenge by Indaco Biazzo:
The instances below were also made available by Indaco Biazzo:
- H2: Hypercubes based on SPG instances originally proposed by Rossetti et al. (2001). They have the same parameters of class H above, but use different random seeds. These are not the instances that appear in Biazzo et al. (2013).
The following instances were made available by Gunnar W. Klau and Mohammed El-Kebir:
- ACTMODPC: Instances
from integrative biological network analysis, in which the task is to find active modules (sets of connected genes likely involved in a common cellular
mechanism). The instances are not necessarily connected. These PCSPG instances were created by Daniel Juhl by transforming instances for the Maximum-Weight Connected Subgraph Problem (also available) following the reduction described in Dittrich et al. (2008).
The following class of instances was made available for the challenge by Ludwig Schmidt:
- Hand: Images of hand-written text derived from an application of the PCSPG problem in signal processing (sparse approximation). These instances were introduced in A Fast, Adaptive Variant of the Goemans-Williamson Scheme for the Prize-Collecting Steiner Tree Problem (by Chinmay Hegde, Piotr Indyk, and Ludwig Schmidt), which will be presented at the challenge. A link to the actual paper will be added once the final version is available.