Faster Vertex Cover Algorithms on GPUs With Component-Aware Parallel Branching
- 23 December 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 37 (2) , 504-517
Abstract
Algorithms for finding minimum or bounded vertex covers in graphs use a branch-and-reduce strategy, which involves exploring a highly imbalanced search tree. Prior GPU solutions assign different thread blocks to different sub-trees, while using a shared worklist to balance the load. However, these prior solutions do not scale to large and complex graphs because their unawareness of when the graph splits into components causes them to solve these components redundantly. Moreover, their high memory footprint limits the number of workers that can execute concurrently. We propose a novel GPU solution for vertex cover problems that detects when a graph splits into components and branches on the components independently. Although the need to aggregate the solutions of different components introduces non-tail-recursive branches which interfere with load balancing, we overcome this challenge by delegating the post-processing to the last descendant of each branch. We also reduce the memory footprint by reducing the graph and inducing a subgraph before exploring the search tree. Our solution substantially outperforms the state-of-the-art GPU solution, finishing in seconds when the state-of-the-art solution exceeds 6 hours. To the best of our knowledge, our work is the first to parallelize non-tail-recursive branching patterns on GPUs in a load balanced manner.Keywords
All Related Versions
Funding Information
- University Research Board of the American University of Beirut (AUB-URB-104391-26749)
This publication has 50 references indexed in Scilit:
- Computing Maximum Independent Sets over Large Sparse Graphs2019
- A refined algorithm for maximum independent set in degree-4 graphsJournal of Combinatorial Optimization, 2017
- Lessons Learned from Exploring the Backtracking Paradigm on the GPU2011
- Accelerating Large Graph Algorithms on the GPU Using CUDA2008
- Scalable Parallel Algorithms for FPT ProblemsAlgorithmica, 2006
- Improvement on vertex cover for low-degree graphsNetworks, 2000
- Parameterized Complexity1999
- Vertex Cover: Further Observations and Further Improvements1999
- Fixed-parameter complexity and cryptography1993
- Algorithms for maximum independent setsJournal of Algorithms, 1986