Where Does the 1.79 Come From? An Empirical Anatomy of the New Prize-Collecting Steiner Tree Algorithm

The prize-collecting Steiner tree problem asks how to wire up a network when you are allowed to skip customers. Each customer (node) carries a penalty that you pay if you leave it unconnected. The goal is to minimize the cost of the cables you build plus the penalties for everyone left out. For more than a decade the best provable guarantee was a cost within 1.967 times optimal. In 2024, Prize-Collecting Steiner Tree: A 1.79 Approximation lowered it to 1.7994 with an algorithm called IPCST, which builds three candidate trees and keeps the cheapest. The paper contains no implementation at all, and its authors say plainly that empirical studies are needed to compare it with "the traditional 2-approximation heuristics used in industry."

We propose to do more than race IPCST against the classical method. We will take the algorithm apart. It has three ingredients: a rescaling of penalties inside the classical Goemans–Williamson primal-dual method, a re-solve of a compulsory Steiner tree on the nodes that method marks as worth connecting, and a recursion on the nodes it marks as not worth connecting. We will measure which of these ingredients produces savings on realistic and on adversarial instances, and whether that ingredient survives when the impractical subroutine the proof relies on is replaced by one that can actually be run. We expect most of the practical gain to come from the Steiner re-solve on the "live" nodes. If so, a two-stage hybrid that costs little more than Goemans–Williamson would capture most of what the new theory offers, and we would have a principled explanation of why.

Core Claim

The worst-case improvement from 1.967 to 1.7994 comes from a proof that averages three candidates over a four-way partition of nodes. That proof does not tell us which candidate wins on the instances people actually solve. Our hypothesis is that the winning candidate depends on one quantity: the ratio of typical node penalty to typical path cost. It is an informative quantity because the problem becomes easy at both extremes (connect everyone, or connect no one) and genuinely hard only in the middle.

In that middle band we expect the candidate that re-solves a compulsory Steiner tree on the scaled method's live set to account for the large majority of IPCST's advantage over plain Goemans–Williamson. We expect the recursive candidate to matter mainly on structured adversarial instances. The contribution is therefore a measured, per-ingredient account of the algorithm, together with a simplified algorithm whose worst-case guarantee we re-derive rather than assume.

What Prior Work Establishes and Leaves Open

Two theory lines motivate the problem. The first shows that penalties make network design qualitatively harder: Prize-collecting Network Design on Planar Graphs proves prize-collecting Steiner forest stays APX-hard on planar graphs, where the compulsory version is much easier. The second shows the natural linear-programming relaxation is weak: On the Integrality Gap of the Prize-Collecting Steiner Forest LP shows the relaxation can pay fractional penalties instead of buying fractional edges, with a gap of at least 9/4. The algorithmic breakthroughs, IPCST and the coloring-based 2-Approximation for Prize-Collecting Steiner Forest, were designed specifically to escape these structures. None of this work measures anything.

On the empirical side, FrontierCO benchmarks machine-learning solvers on real, large instances. It includes only the compulsory Steiner tree problem, and it compares against Gurobi and local search, not against approximation algorithms. Nearly Optimal Steiner Trees using GNN Assisted MCTS and Multi-level Steiner Trees also study only compulsory variants. We reuse their instance sources (SteinLib, random graph families) but add penalties.

The closest methodological precedent is Best of Both Worlds. It showed that a theoretically optimal parallel submodular algorithm, once carefully engineered, beat a fast unproven heuristic on wall-clock time across all six of its applications. Our study asks the analogous question for prize-collecting trees, with one difference: we isolate which piece of the theory matters rather than engineering the whole thing.

Research Program

We will build a single open implementation of the following:

  • classical Goemans–Williamson for this problem, with standard pruning;
  • the penalty-scaled variant with the paper's factor $\beta \approx 1.252$ as a tunable knob;
  • the live-set Steiner re-solve;
  • the recursive dead-set candidate, with a configurable depth cap;
  • full IPCST as the minimum over the three candidates.

The paper's Steiner candidate calls the 1.39-approximation of Byrka et al. as a black box. That algorithm is not practical to run. We will therefore substitute three alternatives:

  • an exact integer-programming Steiner solver on small and medium instances;
  • a practical Steiner heuristic;
  • the classical minimum-spanning-tree 2-approximation.

For each substitution we will redo the paper's weighted-average argument with the black-box Steiner ratio treated as a parameter $\rho$. This yields the guarantee that the runnable variant actually carries. We will not quote 1.7994 for code that does not achieve it. If the argument is not cleanly parametric in $\rho$, we will report that as a finding.

Every run will log several quantities:

  • which candidate won;
  • how the four-way node partition from the proof looks on that instance, measured against the optimal solution where one is known;
  • the Goemans–Williamson dual value, which is a lower bound on the optimum;
  • wall-clock time for each phase.

The dual bound lets us report a certified gap per instance even where exact solutions are out of reach.

Instances will come from three sources:

  • SteinLib instances, including the I080 and I160 sets used by the GNN-MCTS paper;
  • road networks from the 9th DIMACS Implementation Challenge used by Learning-Augmented Algorithms for Online Steiner Tree;
  • the Steiner tree instances in FrontierCO, plus Erdős–Rényi, Barabási–Albert and random geometric graphs.

On the first three sources we add penalties drawn from uniform, heavy-tailed and spatially clustered distributions. For every instance we sweep the penalty scale across the full range from "skip everyone" to "connect everyone." We also build adversarial families from the structure of the IPCST proof and from the integrality-gap constructions of Könemann et al. These are the only places where theory predicts plain Goemans–Williamson should lose badly.

A secondary, smaller arm will profile the coloring-based 2-approximation for Steiner forest on the same road networks. It asks a narrower question: does its max-flow step over the auxiliary "set-pair" graph dominate runtime? We will not attempt a full ingredient analysis there.

Baselines

The naive reference point is the better of two trivial answers: an empty network paying every penalty, and a compulsory Steiner tree connecting every terminal. Any method that does not clearly beat this on mid-range penalty scales is not solving the prize-collecting part of the problem. Its value also tells us where the hard penalty band lies.

The strongest practical competitor is unscaled Goemans–Williamson with pruning. This is the "traditional 2-approximation heuristic" the IPCST authors name as the thing to beat. We will also run a version followed by simple node-add/node-drop local search at matched wall-clock time, because that is the realistic industrial pipeline. Both receive the same instances and time limits as IPCST and its variants. The only tuned parameter anywhere is $\beta$, and we give the same sweep budget to a penalty-scaling knob added to the baseline.

The exact reference is a branch-and-cut integer program (Gurobi or SCIP) with fixed time limits. It gives optima on small and medium instances and anytime gaps on large ones.

No reported result was found on Lacuna for any of these methods on prize-collecting instances. The file explicitly records no benchmark numbers for either new algorithm, so every baseline number will be produced here.

Beating Goemans–Williamson means lower total cost, at statistical significance over instance families in the hard penalty band, at no more than a stated constant factor in runtime. Beating the local-search pipeline means the same at equal wall-clock time.

The ablations that isolate our key ingredient are these:

  • IPCST with each candidate removed;
  • the scaled method alone versus unscaled;
  • the two-stage hybrid (scaled method, then Steiner re-solve on the live set) versus full IPCST.

Why not just…?

Why not just solve everything with a commercial integer-programming solver? On instances it can finish, it is the gold standard, and we use it exactly that way. The evidence in adjacent Steiner work is that exact solvers stop scaling well before real network sizes. ReSPack could not run SCIP on its larger Steiner packing sets. Multi-level Steiner Trees reports integer-programming runtime growing sharply even below 500 nodes. The weak relaxation documented by Könemann et al. suggests prize-collecting instances should be harder still for branch-and-cut. Our time-limited runs on DIMACS road networks will show directly whether this holds. If the solver closes gaps on million-edge road graphs within minutes, the practical case for approximation algorithms shrinks, and we will say so.

Why not just run Goemans–Williamson plus local search? This is the real threat. It may match IPCST on nearly all natural instances, since local search can repair many of the exclusion errors that IPCST's recursion targets. We treat it as the main competitor at equal wall-clock time rather than arguing around it. The per-instance candidate logs and the adversarial families will settle the question. If local search matches IPCST on natural instances but fails on the proof-derived families, the new theory's value is robustness. If it matches everywhere, that is a negative result worth publishing.

Why not just drop cheap-penalty nodes by a threshold and then solve a compulsory Steiner tree? Such a filter decides each node in isolation. Prior theory explains why that fails: whether a node is worth connecting depends on sharing paths with other nodes, which is why A Unified PTAS for Prize Collecting TSP and Steiner Tree in Doubling Metrics needed adaptive rather than fixed decompositions. The two-stage hybrid we study is exactly this idea done right: it replaces the naive threshold with the primal-dual method's own live/dead classification. Running both side by side shows how much that classification is worth.

Why not just train a graph neural network? FrontierCO found neural solvers fall into a "locality trap" on Steiner trees and lose to classical solvers there. The primal-dual reasoning model of Primal-Dual Neural Algorithmic Reasoning explicitly does not extend to the moat-growing dual structure this problem needs. Neural methods are therefore out of scope until the classical picture is measured.

Decisive Checks

The central test concerns cost within the hard penalty band on SteinLib and DIMACS instances with known optima. If removing the recursive candidate leaves IPCST's average cost essentially unchanged, while removing the Steiner re-solve erases most of its advantage over Goemans–Williamson, the hypothesis holds. The hybrid then becomes the recommended practical algorithm, with its re-derived guarantee. If instead the recursion wins often on natural instances, the hypothesis is wrong and the full algorithm is justified in practice.

The second test locates where the methods differ. Plotting cost relative to the dual lower bound against penalty scale should show all methods agreeing at the extremes and diverging only in a middle band. The width and position of that band, per graph family, is a finding in its own right.

The third test concerns the adversarial families. Goemans–Williamson should degrade toward its worst case there while IPCST and the hybrid should not. If this fails to appear even on instances built from the proof, then the analysis is loose in ways worth reporting back to the theory community.