An Exact Algorithmic Pipeline Certifies the Minimum Binary Seed for Rebuilding Software Package Ecosystems from Source

Authors

  • Luis Eduardo Muñoz Guerrero Facultad de Ingenierías, Universidad Tecnológica de Pereira, Colombia

DOI:

https://doi.org/10.70917/ijcisim-2026-6153

Keywords:

feedback vertex set, integer programming, algorithm engineering, software package ecosystems, build from source, software supply chain

Abstract

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).

Downloads

Download data is not yet available.

Downloads

Published

2020-01-01

How to Cite

Luis Eduardo Muñoz Guerrero. (2020). An Exact Algorithmic Pipeline Certifies the Minimum Binary Seed for Rebuilding Software Package Ecosystems from Source. International Journal of Computer Information Systems and Industrial Management Applications, 12, 1–20. https://doi.org/10.70917/ijcisim-2026-6153

Issue

Section

Original Articles