Beyond BFS: A Comparative Study of Rooted Spanning Tree Algorithms on GPUs

Researchers Abhijeet Sahu and Srikar Vilas Donur have published a paper challenging the long-standing dominance of Breadth-First Search (BFS) for constructing Rooted Spanning Trees (RSTs) on GPUs. RSTs are a fundamental building block for parallel graph analytics, used in tasks like finding biconnected components and testing planarity. While BFS has been the go-to method due to its simplicity, its O(D) step complexity—where D is the graph's diameter—severely limits parallelism on complex, high-diameter graphs like social networks or power grids. This bottleneck has become a significant performance hurdle in large-scale graph processing.

To overcome this, the team introduced a GPU-optimized version of the Path Reversal RST (PR-RST) algorithm and evaluated a novel, integrated approach. This approach combines a state-of-the-art connectivity framework called GConn with an Eulerian tour-based rooting technique. The key breakthrough is algorithmic: connectivity-based methods have a more favorable O(log n) step complexity. By meticulously optimizing pointer-jumping and broadcast operations for modern GPU architecture, the researchers demonstrated that this theoretical advantage translates into massive real-world gains. Their evaluation across more than 10 real-world graphs showed the GConn-based method achieving speedups of up to 300x compared to highly optimized BFS implementations on challenging, high-diameter graphs.

This study provides compelling evidence that the GPU graph analytics stack needs an update. The findings suggest that the structural overhead of more complex connectivity algorithms is now outweighed by their superior parallelism on contemporary hardware. This work effectively motivates a fundamental rethinking of core graph primitive construction, paving the way for faster analysis of massive, real-world networks in fields from social network analysis to computational biology and infrastructure modeling.