arXiv:2611.15615 · v1

A Parallel Greedy Algorithm for Maximal b-Matching in Hypergraphs

首次提交 2026-11-11 23:32

版本更新 2026-11-11 23:32

雷达观测 2026-11-13 14:16

摘要

We present \parallelBatchBMatch, a parallel batch-vote algorithm for maximal $b$-matching in hypergraphs. The algorithm is deterministic for a given ordering of edges and produces the same output as the sequential greedy algorithm, i.e., the lexicographically first maximal $b$-matching. Under a uniformly random priority order it performs $O(m')$ expected work in the binary fork--join model, where $m'$ is the number of pins, the total number of vertex--edge incidences. The algorithm performs at most $m$ rounds for every priority order, where $m$ is the number of edges. Every round of the algorithm has $O(\log^2 m')$ depth with high probability, and thus the total depth of the algorithm is $O(m \log^2 m')$ with high probability. We implement the parallel algorithm in CUDA and evaluate it on real-world hypergraphs with capacities $b \in \{1, 3, 5\}$. The parallel algorithm computes the same matchings as the greedy algorithms and for the case of $b = 5$ it is up to $19.07$ times faster than the existing state-of-the art greedy algorithm.

作者备注：19 pages. Accepted to the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA 2027)