Performance of a cavity-method-based algorithm for the prize-collecting Steiner tree problem on graphs

We study the behavior of an algorithm derived from the cavity method for the prize-collecting steiner tree (PCST) problem on graphs. The algorithm is based on the zero temperature limit of the cavity equations and as such is formally simple (a fixed point equation resolved by iteration) and distributed (parallelizable). We provide a detailed comparison with state-of-the-art algorithms on a wide range of existing benchmarks, networks, and random graphs. Specifically, we consider an enhanced derivative of the Goemans-Williamson heuristics and the dhea solver, a branch and cut integer linear programming based approach. The comparison shows that the cavity algorithm outperforms the two algorithms in most large instances both in running time and quality of the solution. Finally we prove a few optimality properties of the solutions provided by our algorithm, including optimality under the two postprocessing procedures defined in the Goemans-Williamson derivative and global optimality in some limit cases.

Figure 1

A schematic representation of the prize collecting Steiner tree problem and its local representation. Numbers next to the nodes are the distances (depths) from the root node (square node). The prize value is proportional to the darkness of the nodes. Arrows are the pointers from node to node. Distances and pointers are used to define the connectivity constraints which appear in the message-passing equations.

Figure 2

Gap from the optimum found by dhea program of, respectively, (a) mgw and (b) msgsteiner as a function of the number of nodes. msgsteiner gaps are always under $0.05\%$. mgw gaps are always over $1\%$ and for intermediate sizes of the solution tree the gaps of mgw are over $3\%$.

Figure 3

Result on the random graphs class $R$. Points correspond to the running time of msgsteiner and dhea versus graph size. The four cases show how running time behavior depends on the size of the expected solution tree. The plots (a), (b), (c), (d) have, respectively, $\lambda =1.2,1.5,2,3$ and an average value of the fraction of nodes that belongs to the solution, respectively, $\left|V\right(T\left)\right|/\left|V\right(G\left)\right|=0.14,0.33,0.51,0.67$. The quantities shown in the figure are averaged over ten different realizations. Data are fitted with function $y=a{x}^b$. The $b$ values found for dhea are for (a), (b), (c), (d), respectively: 2.4, 2.8, 2.8, 2.8. BP performance is as expected roughly linear in the number of vertices. The fitted $b$ parameters are for (a), (b), (c), (d), respectively: 1.5, 1.3, 1, 1. For instances that are large enough, the running time of msgsteiner is smaller than the one of dhea and the difference increases with the expected solution tree.