Fast and Accurate Heuristics for Bus-Factor Estimation

The bus-factor is a critical risk indicator that quantifies how many key contributors a project can afford to lose before core knowledge or functionality is compromised. Despite its practical importance, accurately computing the bus-factor is NP-Hard under established formalizations, making scalable analysis infeasible for large software systems. In this paper, we model software projects as bipartite graphs of developers and tasks and propose two novel approximation heuristics, Minimum Coverage and Maximum Coverage, based on iterative graph peeling, for two influential bus-factor formalizations. Our methods significantly outperform the widely adopted degree-based heuristic, which we show can yield severely inflated estimates. We conduct a comprehensive empirical evaluation on over $1\,000$ synthetic power-law graphs and demonstrate that our heuristics provide tighter estimates while scaling to graphs with millions of nodes and edges in minutes. Our results reveal that the proposed heuristics are not only more accurate but also robust to structural variations in developer-task assignment graph. We release our implementation as open-source software to support future research and practical adoption.