An Exact Algorithmic Pipeline Certifies the Minimum Binary Seed for Rebuilding Software Package Ecosystems from Source
DOI:
https://doi.org/10.70917/ijcisim-2026-6153Keywords:
feedback vertex set, integer programming, algorithm engineering, software package ecosystems, build from source, software supply chainAbstract
Rebuilding a software ecosystem from source requires accepting some packages as binaries whenever dependency cycles would otherwise leave no build order. We ask how many packages this binary seed must contain in language package ecosystems and which kinds of dependency force them. The minimum seed is a minimum directed feedback vertex set, an NP-hard problem that admits no constant-factor approximation under the Unique Games Conjecture, so we built an exact algorithmic pipeline that reduces each dependency graph, solves the remaining components by integer programming with lazily generated cycle constraints, and certifies every answer with lower and upper bounds. On the Libraries.io dump of 15 June 2017, with 1,237,945 packages, all 33 instances (11 ecosystems under runtime, build, and development and test scenarios) were solved to proven optimality in 120 s, including reading the extracted dependencies, and the reductions left only 6 components for the integer program. Seeds range from 1 to 2,206 packages when development and test dependencies are required; npm needs 394 binary packages for its runtime dependencies alone and 2,206 with them, and, in an exploratory count, 50% of all runtime seed packages declare a dependency on themselves. A pre-specified hypothesis that development and test dependencies account for most of the seed was positive in the primary specification (7 of 8 ecosystems, sign test = 0.0352) and passed a label-permutation placebo check in 6 of 8 ecosystems, but it held in only 8 of 16 pre-specified specifications, below the 80% required, and is reported as not valid. A greedy heuristic stayed within 6.4% of the optimum in every ecosystem (exploratory), and suspending at most 3.1% of the development and test dependencies (up to 68.7% of those on a cycle) brought each seed down to its size without them (in npm, by an exploratory rerun).