Gabow Arborescence Packing In SageMath

Edge-disjoint spanning arborescences are a fundamental structure in directed graph theory, with applications in connectivity and network design. SageMath currently relies on Mixed Integer Linear Programming (MILP) to compute them, which can be slow on complex instances and depends on external solvers. This project will add a native combinatorial backend based on Gabow’s algorithm, implemented in Cython and integrated into SageMath’s public API. Deliverables include validation tools, randomized regression tests, documentation, and performance benchmarks against the existing MILP-based implementation.