Faster Vertex Cover Algorithms on GPUs with Component-Aware Parallel Branching
Hussein Amro, Basel Fakhri, Amer E. Mouawad, Izzat El Hajj · 2025
Read Faster Vertex Cover Algorithms on GPUs with Component-Aware Parallel Branching by Hussein Amro, Basel Fakhri, Amer E. Mouawad, Izzat El Hajj (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-18334.txt.
Introduction
Hussein Amro, Basel Fakhri, Amer E. Mouawad, and Izzat El Hajj race a classic graph puzzle on graphics chips. A vertex cover picks points so every link touches a picked point, and the best solvers branch down a lopsided search tree. Past chip versions farmed branches to thread groups but solved split off pieces again and again, and their memory hunger capped the crew size.
Their solver notices when the graph breaks into separate pieces and branches on each piece alone. A tidy hand off scheme lets the last worker on a branch do the joining work, and a slimmed graph cuts memory before the search starts. Jobs that took the prior best over 6 hours now finish in seconds.
Catalog record
| CREATOR | Hussein Amro, Basel Fakhri, Amer E. Mouawad, Izzat El Hajj |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-18334
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Faster Vertex Cover Algorithms on GPUs with Component-Aware Parallel Branching Hussein Amro, Basel Fakhri, Amer E. Mouawad, Izzat El Hajj 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. I Introduction A vertex cover for a graph is a set of vertices in the graph such that every edge in the graph is incident on at least one of the vertices in the set. Finding vertex covers of minimum or bounded size has applications in multiple domains such as computational biology, networks, artificial intelligence, and others [ 9 , 12 ] . The typical algorithms for finding vertex covers of minimum or bounded size adopt a branch-and-reduce strategy, which ultimately involves exploring a search tree covering the solution space, while pruning the tree using stopping conditions and reduction rules. Prior works for parallelizing vertex cover algorithms on GPUs [ 31 , 1 , 57 ] assign different branches of the search tree to different thread blocks, which explore the branches concurrently using private stack data structures. Load balance is particularly challenging because of the highly imbalanced nature of the search tree, so the state-of-the-art GPU solution [ 57 ] uses a shared worklist to offload tree nodes from busy thread blocks to idle thread blocks. Still, even the state-of-the-art GPU solution struggles to scale to large and complex graphs due to two limitations. The first limitation is that it is unaware of when the graph splits into multiple components during the search, causing it to solve the same component redundantly. The second limitation is that its high memory footprint prevents it from launching enough workers to fully utilize the GPU. We propose a novel GPU solution for vertex cover problems that overcomes these two limitations. To overcome the first limitation, we detect when a graph splits into multiple components during the search and branch on different components independently to avoid processing them redundantly. The main challenge is that the need to aggregate the solutions of different components introduces non-tail-recursive branches into our search tree. Non-tail recursive branches interfere with the ability to send different children to different thread blocks for the purpose of load balancing. To address this challenge, we register every non-tail-recursive branch on components in a shared space and track the active descendants of a branch, then delegate the post-processing to the thread block that solves the last descendant. Our solution works for multiple nesting of non-tail-recursive branches. To overcome the second limitation, we aggressively apply reduction rules to the graph and induce a subgraph prior to exploring the search tree. Using the induced subgraph allows us to decrease the memory footprint of the intermediate graph representation, thereby unleashing more parallelism when scaling to large graphs. We also leverage sparsity in the intermediate graph representation to reduce the number of vertices we visit, and we use small integer data types where possible to further reduce the memory footprint. Our evaluation shows that our GPU solution for vertex cover substantially outperforms the state-of-the-art GPU solution, finishing in seconds or minutes when the state-of-the-art solution times out after 6 hours. It demonstrates that our component-aware branching significantly reduces the number of search tree nodes visited, and that our optimizations to the intermediate graph representation enable many more thread blocks to participate in the computation. Beyond vertex cover algorithms, numerous works parallelize branching algorithms on GPUs [ 16 , 17 , 33 , 30 , 53 , 6 , 5 ] and load balancing is a common challenge that they deal with. However, all these works parallelize branching patterns that are tail recursive. To the best of our knowledge, our work is the first to parallelize non-tail-recursive branching patterns on GPUs, while retaining load balancing capabilities. Our code has been open sourced to enable reproducibility and further research on parallel branching algorithms for GPUs 1 1 1 https://github.com/HusseinAmro/component-aware-vertex-cover-gpu . II Background II-A Definitions Let G=(V,E) denote an undirected simple graph with vertex set V(G) and edge set E(G) . Let N(v) denote the set of vertices adjacent to a vertex v\in V(G) , also called the neighborhood of v . Let d(v) denote the number of edges incident on a vertex v\in V(G) , also called the degree of v . \Delta(G) denotes the maximum degree in G , i.e., the degree of a vertex with the highest degree. Given a set of vertices S\subseteq V(G) , G-S denotes the subgraph induced on the set of vertices V(G)\setminus S . A vertex cover for a graph G is a set of vertices S\subseteq V(G) , such that for every edge v_{1}v_{2}\in E(G) , S contains at least one of v_{1} or v_{2} , i.e., \{v_{1},v_{2}\}\cap S\neq\emptyset . The Minimum Vertex Cover (MVC) problem is to find a vertex cover S for G such that there is no vertex cover T for G where |S|>|T| . The Parameterized Vertex Cover (PVC) problem is to find, for a given integer k>0 , a vertex cover S for G such that |S|\leq k (if such a vertex cover exists). II-B Vertex Cover Algorithms The typical algorithms for solving the MVC and PVC problems adopt the branch-and-reduce strategy. Branch-and-reduce algorithms explore the solution space of a problem by successively breaking the problem into smaller alternative sub-problems (i.e., branching), and solving these sub-problems recursively. For vertex cover problems, we observe that for any vertex in the graph, a vertex cover must contain either that vertex or all of the vertex’s neighbors to ensure that all the edges incident on that vertex are covered. This observation is the basis for breaking a problem into two alternative sub-problems when branching: one where the solution contains a vertex of our choice and one where the solution contains all of that vertex’s neighbors. A convenient vertex to choose for branching is a vertex of maximum degree, which ensures the largest number of edges is covered when we branch. The branching pattern in these algorithms forms a search tree, where every internal node in the search tree is an intermediate sub-problem, and the leaf nodes are solutions or