A Parallel Greedy Algorithm for Maximal b-Matching in Hypergraphs

A Parallel Greedy Algorithm for Maximal b-Matching in Hypergraphs∗

arXiv:2611.15615v1 [cs.DS] 11 Nov 2026

Saeed Bakhshan†

Daniel Grosu‡

Abstract. We present PB-bM, a parallel batchvote 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(log2 m′ ) depth with high probability, and thus the total depth of the algorithm is O(m log2 m′ ) with high probability. We implement the parallel algorithm in CUDA and evaluate it on real-world hypergraphs with capacities b ∈ {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. Keywords. hypergraph b-matching, parallel algorithms, graph algorithms. AMS subject classifications. 05C65, 05C70.

68W10, 68W20,

Code & experimental data. We provide the code at github.com/HeiHGM/Parallel, an archived version can be found at 10.5281/zenodo.24085030. 1 Introduction. Given a hypergraph G = (V, E) with n = |V | vertices and m = |E| hyperedges, where each edge e ∈ E is a set V (e) of vertices, and a capacity function b : V → Z≥1 , a b-matching is a set M ⊆ E such that no vertex v is incident to more than b(v) edges of M . A b-matching is maximal if no edge in E \ M can be added without exceeding the capacity of one of its vertices. The maximal hypergraph b-matching problem asks to compute such a maximal b-matching. ∗ This work was supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number 543787284. † Wayne State University, Detroit, MI, USA. ‡ Wayne State University, Detroit, MI, USA. § Heidelberg University, Heidelberg, Germany. ¶ Heidelberg University, Heidelberg, Germany.

Henrik Reinstädtler§

Christian Schulz¶

Hypergraph b-matchings arise naturally in several application domains. In scheduling, consider assigning jobs to machines where each job needs a group of machines at once, and each machine v can run at most b(v) jobs concurrently. This models settings in which a task holds several resources at the same time and no resource may be oversubscribed. bmatchings are used in online advertising, where advertiser budgets act as capacities [19, 54], and in reconfigurable datacenter networks [12]. In machine learning they build balanced similarity graphs [43], enforce diversity in recommendation [1], and provide privacy-preserving anonymization [21]. Computing a maximum b-matching in hypergraphs is NP-hard, and even hard to approximate [59, 60]. This motivates the study of maximal bmatchings, which can be computed in linear time by a simple sequential greedy algorithm (called SeqGreedy). SeqGreedy processes the edges in some fixed order and adds each edge whose vertices are all having some capacity available. It runs in O(m′ ) P time and produces a maximal b-matching, where m′ = e∈E |V (e)| is the number of vertex–edge incidences of G. The particular matching obtained depends on the order in which the edges are processed. We call such an order a priority order π, and the result the lexicographically first maximal b-matching with respect to π. While SeqGreedy underlies widely used b-matching heuristics [37, 55], these are all sequential, and the question of how to parallelize them efficiently has not been addressed. When b(v) = 1, for all v ∈ V , and every edge is a pair, the problem is the maximal matching in graphs, for which parallel algorithms have been studied extensively. Israeli and Itai [42] gave a randomized maximal matching algorithm that achieves O(log n) expected depth. However, these algorithms do not preserve the output of SeqGreedy. In many settings a deterministic output that matches the sequential result is desirable, because it allows switching between sequential and parallel execution based on available resources while returning the same matching [14]. A natural question is whether SeqGreedy can be parallelized efficiently while producing the same output. To the best of our knowledge, no work-efficient parallel algorithm that computes the lexicographically

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

first maximal b-matching in both graphs and hypergraphs has been proposed prior to this work. One might consider splitting each vertex v into b(v) copies, which reduces b-matching to matching with unit capacities, and then applying the algorithm of Blelloch and Brady [14]. However, a hyperedge (u, v) with two vertices then expands into a complete bipartite graph between the copies of u and v, inflating the edge count by Θ(β 2 ), where β = maxv∈V b(v) is the largest capacity. The blow-up is β |V (e)| for a hyperedge e, making the reduction not work-efficient. The construction also fails to preserve the lexicographically first order, since a matching may use one original edge several times, once per matched pair of copies. Furthermore, since computing the lexicographically first maximal independent set is P-complete for worst-case orderings [22], efficient parallelization of the lexicographically first maximal bmatching may also be difficult in the worst case. However, the situation changes when we consider random orderings. Under a random order on edges the greedy algorithm for maximal matching in hypergraphs [16, 30] has polylogarithmic dependence depth, the number of rounds obtained by repeatedly matching, in parallel, every edge with no higher-priority conflict, where the priority of edges is given by the random order. Blelloch and Brady [14] turned this into a work-efficient parallel maximal hypergraph matching algorithm that reproduces the output of SeqGreedy for unit capacities. Considering vertex capacities change this dependence structure. A vertex is removed only when it saturates, not when it is first matched, thus an edge can wait on b(v) earlier decisions at each of its vertices instead of one. Contributions. Building on this framework, we make the following contributions: • We propose PB-bM, a parallel algorithm for maximal b-matching in hypergraphs in which each vertex votes for all of its remaining capacity at once rather than one slot at a time (Section 4). • We prove that it returns the lexicographically first maximal b-matching for every priority order, no matter how the rounds are scheduled. and that it performs O(m′ ) expected work in the binary fork– join model (Section 4). • We show that PB-bM performs at most m rounds for every priority order, where m is the number of edges. Every round has O(log2 m′ ) depth with high probability (w.h.p.). Thus, PB-bM has a depth of O(m log2 m′ ) w.h.p. (Subsection 4.4). • We implement the algorithm in CUDA and evaluate it on real-world hypergraphs with capacities

b ∈ {1, 3, 5}, where depending on the priority it is up to 19.07 times faster than a sequential greedy implementation (Section 5), while delivering the same matching. 2 Related work. We summarize here the results our algorithm builds on and the closest parallel b-matching algorithms. Appendix A provides a more comprehensive discussion of the related work. Greedy matching and dependence depth. Reproducing the solution obtained by a sequential greedy algorithm amounts to computing the lexicographically first maximal solution. For the lexicographically first maximal independent set this is P-complete [22, 56], so such problems are in general resistant to parallelism under a fixed adversarial order. The standard remedy is to randomize the order. Blelloch, Fineman, and Shun [16] proved that on any graph a uniformly random order yields a dependence depth of O(log2 m) w.h.p., where the dependence depth is the number of rounds obtained by repeatedly matching, in parallel, every edge having no higher-priority conflict. Fischer and Noever [30] tightened this bound to O(log m) w.h.p. Building on this framework, Blelloch and Brady [14] obtained a work-efficient parallel algorithm for maximal matching in hypergraphs with O(m′ ) expected work and O(log2 m) depth w.h.p., which returns exactly the solution of SeqGreedy for unit capacities. Their approach is the starting point for our algorithm. No analogue of these round bounds is known once vertex capacities are considered. In Subsection 4.4 we give a simple bound on the number of rounds of our algorithm, and we leave the derivation of a tighter bound to future work. Parallel matching and b-matching. Parallel maximal matching and maximal independent set are classical problems [4, 42, 45, 53], and the degree-constrained generalization appeared early [34]. Each of these algorithms computes some maximal solution, which depends on the schedule. Parallel algorithms for hypergraph matching have been developed along several lines [27, 38, 40, 62], but none of them accounts for vertex capacities. For b-matching the parallel literature offers only approximation guarantees, and it concerns ordinary graphs almost exclusively. The b-Suitor family [48, 49] computes 1 2 -approximations that scale to billions of edges, with a GPU implementation [58]. In the massively parallel (MPC) model, Ghaffari, Grunau, and Mitrović [36] gave ¯ rounds, where d¯ a (1 + ε)-approximation in O(log log d) is the average degree. None of the parallel algorithms discussed above computes the lexicographically-first maximal bmatching in hypergraphs. This is the gap that our parallel algorithm closes. Table 2.1 lists only the parallel algorithms, each covering some subset of the three

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

Table 2.1: Parallel maximal matching and b-matching algorithms. (Unless noted, the bounds hold under a uniformly random priority order, w.h.p. for depth and rounds and in expectation for work. The label “rounds” is shown where no work–depth bound is available for the MPC (Massively Parallel P Computing model). ∆ is the maximum degree, r is the maximum edge size, d¯ is the average degree, and B = v b(v). The b(v)-split row is the vertex-splitting reduction to ordinary matching. ‡ b-Suitor’s bounds are in expectation and hold under uniformly random edge weights, and are extended to general b in [47] only by a sketched reduction to the unit-capacity case.) Algorithm

b ≥ 1 Hypergraph Greedy Output

Garrido et al. [34] (f -match) Khan et al. [47] (b-Suitor) Ghaffari et al. [36] b(v)-split +Blelloch and Brady [14] Reinstädtler et al. [62] Blelloch and Brady [14]

yes yes yes yes no no

no no no no yes yes

no no no no no yes

PB-bM (this paper)

yes

yes

yes

Work

Depth

– O(log2 n) O(βB)‡ O(log ∆ log B)‡ ¯ rounds – O(log log d) O(β 2 m′ ) O(log2 m) O(m′ log m) O(log log ∆ log m) O(m′ ) O(log2 m) O(m′ )

O(m log2 m′ )

maximum edge size, and ∆ for its maximum degree, the largest number of edges that contain one vertex. We measure the size P of G by its number of vertex–edge incidences, m′ = e∈E |V (e)|. We call each incidence a pin, i.e., a pair (v, e) with v ∈ V (e), thus m′ is the 3 Preliminaries. number of pins in G. For ordinary graphs m′ = 2m. We 3.1 Hypergraphs and b-matching. Let G = assume′ that every vertex lies on at least one edge, thus ′ (V, E) be a hypergraph with n = |V | vertices and n ≤ m . Since edges are nonempty, we have m ≤ m . A priority order on the set of edges is a bijection m = |E| (hyper)edges. Each edge e ∈ E is a nonempty π : E → {1, . . . , m}. We say that edge e has higher set of vertices denoted by V (e) ⊆ V . The vertices priority than e′ if π(e) < π(e′ ). A random order on in V (e) are called the endpoints of e. We extend edges is one chosen uniformly at random among all m! this S notation to any set of edges S, that is, V (S) = bijections. The sequential greedy algorithm (SeqGreedy, e∈S V (e). An ordinary graph is the special case of two-vertex edges. A capacity function b : V → Z≥1 Algorithm 3.1) considers the edges from the highest to gives each vertex v a positive integer capacity b(v), the lowest priority and takes each edge whose all vertices and we write β = maxv∈V b(v) [37]. No vertex can have some capacity available. The matching it returns lie on more edges than it is incident to. We therefore is the lexicographically first maximal b-matching with assume throughout that b(v) is at most the degree of respect to π. Our proposed parallel algorithm computes vertex v for all v ∈ V . Thus, β is bounded by the this same matching for a given π (Theorem 4.5). We take π to be a random order, the assumption under maximum degree in G, and hence by m. A b-matching is a set M ⊆ E in which no vertex v which SeqGreedy can be parallelized efficiently [16]. Throughout the paper, an event holds with high belongs to more than b(v) edges of M . It is maximal probability (w.h.p.) if it fails with probability at most when every edge outside M has at least one vertex al−c m , for a constant c that can be made arbitrarily ready at its capacity, so that adding the edge would large. The constants hidden in the bounds may depend exceed the capacity of that vertex. The case of unit caon c. Since m ≤ m′ , a failure probability of at pacities, i.e., b(v) = 1 for every vertex v ∈ V , represents ′ −c the maximal matching problem in hypergraphs. In this most (m ) is also enough. paper, we focus on the maximal b-matching problem in 3.2 The fork-join cost model. We analyze hypergraphs. The maximum b-matching problem in hy- our algorithms in the fork-join model with work and pergraphs is NP-hard and hard to approximate [59, 60], depth as the measures of cost, the same model used whereas a maximal b-matching can be computed in lin- in [14]. A computation starts as a single task. Any ear time by SeqGreedy. Our goal is to compute a maxi- task may fork child tasks, which execute in parallel and asynchronously. The parent resumes when all of its chilmal b-matching in hypergraphs in parallel. We write r = maxe∈E |V (e)| for the rank of G, its dren have finished (the join), and forks may be nested. properties listed in columns two to four, i.e., vertex capacities (b ≥ 1), hypergraphs, and the greedy output. Our parallel algorithm covers all three properties and is listed in the last row of the table.

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

Two operations are dependent if one precedes the other in the series–parallel order induced by forks and joins. The operations of a task are ordered by program order, a task’s operations before a fork precede those of the forked children, and the children’s operations precede the operations the parent performs after the corresponding join. Otherwise they are concurrent. The work of a computation is the total number of operations it performs, and its depth (or span) is the length of its longest chain of dependent operations. We adopt the binary-forking convention, under which a fork spawns exactly two children [15]. A parfor over k items then expands into a balanced spawn tree, which adds O(k) work and O(log k) depth beyond the cost of the iterations. Blelloch and Brady [14] allow a task to fork any number of children at once. Binary forking is a special case, so our bounds hold unchanged in their model. Tasks share memory, and concurrent reads and writes are permitted. As in [14], the values read must be consistent with some sequential ordering of the operations that respects the dependences above, so concurrent writes to the same location have a welldefined but nondeterministic outcome. Bounds in this model transfer to the PRAM, a computation with work w and depth d can be simulated on a p-processor PRAM in O(w/p + d log∗ w) time w.h.p. [14]. 3.3 Sequential greedy maximal b-matching algorithm (SeqGreedy). The sequential greedy algorithm for computing a maximal b-matching in hypergraphs, called SeqGreedy and shown in Algorithm 3.1, processes edges according to a priority order π. It maintains a matching M and a counter bcount(v) for each vertex v, holding the number of edges of M incident on v. An edge e is added to M if and only if every endpoint of e still has capacity available (bcount(v) < b(v) for all v ∈ V (e)), and bcount(v) is then increased by one at each endpoint of e. We call b(v) − bcount(v)

Algorithm 3.1 SeqGreedy: sequential greedy for maximal b-matching Input: G = (V, E): a hypergraph; b : V → Z≥1 : capacities; π: a priority order on E Output: M : a maximal b-matching 1: M ← ∅ 2: bcount(v) ← 0 for all v ∈ V 3: for i = 1, . . . , m do 4: let e be the i-th edge in π 5: if bcount(v) < b(v) for all v ∈ V (e) then 6: M ← M ∪ {e} 7: bcount(v) ← bcount(v) + 1 for all v ∈ V (e) 8: return M

the remaining capacity of v, and v is saturated when it reaches zero. The output is the lexicographically first maximal b-matching with respect to π. The algorithm runs in O(m′ ) time. Testing an edge e and incrementing the counters at its endpoints take O(|V (e)|), which is O(m′ ) summed over all edges, and n ≤ m′ and m ≤ m′ (Section 3). Maximality follows from the fact that any edge not in M was rejected at an endpoint saturated by previously added edges, and bcount never decreases. 4 Parallel batch-vote maximal b-matching algorithm (PB-bM). We first introduce some of the notation used in describing the algorithm and state some assumptions. Every vertex v stores its incident edges in edges(v) in the priority order induced by π. N(v) is the set of alive edges incident on v. Initially N(v) holds all edges of edges(v), and each round of the algorithm removes from these sets the edges that are not alive, thus membership in N(v) coincides with being alive. An edge that is no longer alive is dead, and S the flag done(e) records this. We write N(U ) = matching built v∈U N(v). Throughout, M denotes theP so far, and deg(v) = |edges(v)|, so that v∈V deg(v) = P ′ |V (e)| = m . e∈E Blelloch and Brady [14] parallelize SeqGreedy for unit capacities by letting every vertex vote. A vertex points at its highest-priority alive edge, denoted by top(v), and votes for it by incrementing an atomic counter counter(e), which thus counts the vertices of e that have voted for it. Once every vertex of e has voted, that is, once counter(e) = |V (e)|, the alive edge e becomes a root and joins the matching. A root is the highest-priority alive edge at each of its vertices, so SeqGreedy selects it as well, and two roots never share a vertex, so all roots of a round may be added at once. A round then removes the roots together with every other edge incident on a newly matched vertex. A possible direct route to obtain a parallel maximal b-matching algorithm from this scheme is to keep its voting rule intact and change only what a vertex remembers, i.e., give each vertex the same single pointer top(v), have it count the matched edges it has collected, and remove an edge not when one of its vertices is matched but when one of them reaches its capacity. This generalized version is correct, but it makes every vertex a single-vote vertex, and that is expensive for two reasons. First, a vertex holding one pointer votes for one edge per round, thus it acquires at most one match per round and needs b(v) rounds merely to fill its slots, and β = maxv∈V b(v) rounds for the largest capacity. For example on a star graph whose center has capacity β and leaves have capacity one, every leaf votes for its only edge at initialization and then waits. The center’s

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

Algorithm 4.1 PB-bM: parallel batch-voting maximal b-matching Input: G = (V, E): a hypergraph; b : V → Z≥1 : capacities Output: M : a maximal b-matching 1: π ← getRandomPermutation() 2: parfor v ∈ V do 3: edges(v) ← sort({e | v ∈ e}, π) 4: bcount(v) ← 0 5: vote(v) ← b(v) highest-priority edges of edges(v) 6: next(v) ← the first entry of edges(v) after entries 7: 8:

in vote(v) parfor e ∈ vote(v) do increment(counter(e))

9: W ← {e ∈ E | counter(e) = |V (e)|} 10: M ← ∅ 11: while |W | > 0 do 12: M ←M ∪W 13: parfor v ∈ V (W ) do 14: bcount(v) ← bcount(v) + |{e ∈ W : v ∈ e}| 15: 16: 17: 18: 19:

sat ← {v ∈ V (W ) | bcount(v) = b(v)} finished ← W ∪ N(sat) parfor e ∈ finished, v ∈ V (e) do done(e) ← true delete(N(v), e); delete(vote(v), e)

parfor v ∈ V (finished) \ sat do refill vote(v): advance next(v) along edges(v), adding each alive edge, until |vote(v)| = b(v) − bcount(v) or edges(v) is exhausted 22: parfor e newly added to vote(v) do 23: increment(counter(e)) 24: A ← edges newly added to a vote set this round 25: W ← {e ∈ A | counter(e) = |V (e)|} 26: return M 20: 21:

single pointer then lets exactly one edge hold both of its votes in any round, and execution takes β rounds for every priority order. Second, rounds are spent on one vertex refilling a pointer it could have filled all at once. Our proposed parallel batch-vote maximal bmatching algorithm (PB-bM) removes the above serialization, a vertex with remaining capacity b(v) − bcount(v) votes for its top b(v) − bcount(v) alive edges at once, where bcount(v) is the number of edges incident to v that belongs to the current matching. Thus, it can acquire many matches in a single round. On the star graph example considered above, it finishes in one round. Here, vote(v) is the set of edges for which vertex v currently votes. As before, counter(e) counts the number of votes for e and e is a root when

counter(e) = |V (e)|. PB-bM, shown in Algorithm 4.1, differs from the unit-capacity scheme of Blelloch and Brady [14] in two aspects: (i) it tracks bcount(v), and (ii) it replaces the single pointer top(v) (i.e., single vote) by a set of votes. Each vertex v maintains the set vote(v) of its top b(v) − bcount(v) alive edges, or of all alive edges if fewer remain, together with a pointer next(v) which indicates the first entry in the ordered set edges(v) after the entries that have been added to vote(v). The computation begins by drawing a random priority π, sorting each vertex’s incident edges by π, initializing bcount, and having every vertex cast its votes (Lines 1– 8). The edges that already gather a full count form the first root set W (Line 9). After a round commits the roots W , every vertex updates in parallel its bcount (Lines 13–14). The newly saturated vertices are placed in sat, the set of saturated vertices. The saturated vertices and their incident edges are removed, with each removed edge deleted from the N and vote sets of its vertices (Lines 15–19). Each surviving affected vertex then refills vote(v) to its new remaining capacity by advancing next(v), incrementing the counters of the edges it newly votes for (Lines 20– 23). The next root set is collected from A, the set of edges newly voted for in the round, where an edge gaining votes from several endpoints at once is collected once (Lines 24–25). This loses no root, an alive edge whose counter was already full when the previous root set was formed belonged to that root set and was committed and removed, so a new root must have gained a vote in the current round. Unlike under single voting, the root set W may contain several edges incident to the same vertex, since a vertex now casts several votes. In PB-bM, a vertex votes for an edge e by incrementing the edge’s counter, counter(e), thus several vertices may increment the same counter within a round. The pseudocode treats increment as a primitive; we charge each call O(1) work, and the calls of a round, O(log m′ ) depth in total. Blelloch and Brady [14] realize it in the model by grouping a round’s increments by counter (a semisort) and applying each group’s sum as a single update, in expected amortized work linear in the number of increments and logarithmic depth w.h.p. A hardware fetch-and-add provides the operation directly. The two realizations differ in when an increment becomes visible, and PB-bM is not affected by the difference. It defers every counter test past the round’s join (Algorithm 4.1), thus either realization serves it. The same grouping primitive builds the sets of a round, removing duplicates at expected work linear in the number of items. We import two further primitives from [14]. The first is findNext, which advances an index past entries

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

failing a predicate, at O(d) work and O(log d) depth for a slide of distance d. The second is the deletion from a set at O(1) amortized work. PB-bM also needs the extension of findNext that returns the next k entries satisfying the predicate; doubling to a window that contains k of them and selecting by prefix sums costs O(d) work and O(log2 d) depth. In Appendix B, we provide an example illustrating the execution of PB-bM on a small hypergraph. 4.1 Correctness. We first show that the votes are persistent and identify the invariants of the while loop of PB-bM, and then, show that the algorithm terminates and returns a lexicographically first maximal b-matching. Lemma 4.1 (Vote persistence). In every run of PB-bM, votes are persistent, that is, each vertex increments counter(e) at most once, counters never decrease, and vote(v) loses an edge only when that edge is removed. Consequently, while e is alive, counter(e) equals the number of vertices currently voting for e. Proof. The proof is given in Appendix D. Lemma 4.2 (Loop invariants). At the start of every iteration of the while loop in PB-bM, and when the loop terminates, the following invariants hold: (I1) every alive edge has all of its vertices unsaturated. (I2) for every unsaturated vertex v, the set vote(v) consists of the b(v) − bcount(v) highest-priority alive edges incident on v, or of all alive edges incident on v if fewer remain. (I3) the current root set W consists of exactly the alive edges with a full counter. (I4) M is a valid b-matching. Indeed bcount(v) is the number of edges of M incident on v, and bcount(v) ≤ b(v) for every v ∈ V . Proof. The proof is given in Appendix D.

edges (I3), and a removed edge is never alive again, thus each iteration consumes at least one fresh edge, and the while loop terminates after at most m iterations. Next, no edge is alive when the loop exits. Suppose otherwise, and let e⋆ be the highest-priority alive edge. By (I1) every endpoint of e⋆ is unsaturated, and e⋆ is its highest-priority alive edge, thus (I2) places e⋆ in every endpoint’s vote set, and by persistence of votes (Lemma 4.1), counter(e⋆ ) = |V (e⋆ )|. By (I3) the current root set contains e⋆ , therefore it is nonempty and the loop cannot have exited. Finally, M is maximal. An edge is removed only as a member of finished = W ∪ N(sat), and a round’s W is added to M before the marking, thus a removed edge outside M entered N(sat), and some vertex v of it had bcount(v) = b(v) in that round. Since bcount never decreases and never exceeds b(v) (I4), at exit v still lies in b(v) edges of M , and adding the edge would exceed its capacity. Every edge is matched or removed unmatched, therefore M is maximal. The key correctness property is that batching does not change which matching is produced. This requires care: unlike under single voting, a vertex can acquire a lower-priority match while a higher-priority incident edge is still alive, when that edge has yet to receive the votes of its other vertices. Thus, the matches at a vertex need not arrive in priority order. The proof instead uses three consequences of Lemma 4.2. First, a vertex never votes for an edge without also voting for every alive higher-priority incident edge, since by (I2) the vote set is a priority prefix of the alive edges. Second, a vote, once cast, is kept while its edge is alive. Third, a vertex saturates only in a round that commits every edge of its vote set (Lemma 4.4, below). The last consequence rules out the bad case, a vertex v saturating while a higher-priority incident edge e is still alive. Any vote v casts for a lower-priority edge places e in vote(v) as well, and e then stays there as long as it lives. The round in which v saturates commits all of vote(v), hence e itself, rather than removing it. The proof uses the following fact about saturating vertices.

Theorem 4.3 (Correctness). PB-bM terminates Lemma 4.4 (Saturation). If a vertex u saturates and, at termination, every edge is removed, and the in some round, then that round commits every edge of returned M is a maximal b-matching. vote(u) as it is at the start of the round, and vote(u) is Proof. Every iteration of the while loop in PB-bM not empty. Also, the returned matching M has exactly commits and removes at least one edge, and therefore, b(u) edges at u, and each of them has higher priority the while loop terminates. The highest-priority alive than every edge at u that is alive at the start of that edge sits in every endpoint’s vote set, thus, its counter round and not in vote(u). is full and (I3) puts it into the root set. And an Proof. Let Cu be the set of roots at u committed unmatched edge is removed only at a saturated vertex, in the round. It is not empty, since bcount(u) grows which stays saturated. Each iteration commits its nonempty root set and in the round. Each edge of Cu is alive with a full removes it as part of finished. Root sets hold only alive counter (I3), so u votes for it by Lemma 4.1. Thus Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

Cu ⊆ vote(u). The vertex u lies on the alive edges of Cu , so it is unsaturated at the start of the round (I1). Since u saturates, bcount(u) + |Cu | = b(u). By (I2), |vote(u)| ≤ b(u) − bcount(u) = |Cu |, so Cu = vote(u). Now let f be an edge at u that is alive at the start of the round and not in vote(u). Since f is alive and not in vote(u), (I2) says that vote(u) is the priority prefix of the alive edges at u of size b(u) − bcount(u). Thus, every edge of Cu = vote(u) has higher priority than f . Next, let h be an edge committed at u in an earlier round. At the start of that round, h was in vote(u), u was unsaturated since it lies on the alive edge h (I1), and f was alive as well. If h had lower priority than f , then by (I2) f would have been in vote(u) with it, and by Lemma 4.1 it would have stayed there. Thus, h has higher priority than f . Finally, the edges of M at u are the bcount(u) edges committed at u in earlier rounds (I4) and the edges of Cu , since u has no alive edge after it saturates (I1) and roots are alive (I3). Their count bcount(u) + |Cu | = b(u).

(⇐) Suppose e ∈ Mg , thus, each endpoint v is incident to cv < b(v) higher-priority edges of Mg , which by induction are exactly the higher-priority edges of M incident on v. Assume that no round commits e. Every edge is removed when the loop exits (Theorem 4.3), and an uncommitted edge is removed only through N(sat). Thus, some round, call it R, has an endpoint v ∈ V (e) in its sat with e alive at its start. If e ∈ vote(v) at that start, round R commits all of vote(v) (Lemma 4.4), hence e, a contradiction. Thus, e ∈ / vote(v). By Lemma 4.4, v carries b(v) matched edges of higher priority than e. By induction, all of them lie in Mg , thus cv ≥ b(v), contradicting cv < b(v). Hence, some round commits e: e ∈ M . In particular, PB-bM produces the same output no matter how the parallel work within each round is scheduled.

4.2 Work analysis. Batching changes how many votes a vertex casts at once, not how often it Theorem 4.5 (Lexicographically first maximal b- touches any one pin: by Lemma 4.1 a vertex votes matching). For every priority π, PB-bM re- for a given edge at most once, and vote(v) is refilled turns the lexicographically first maximal b-matching by scanning edges(v) forward, so every cost can be charged to the pins. Deleting a dead edge from a with respect to π. vote set charges its pin once more, and collecting the Proof. One direction is a counting argument: a root set from A costs O(1) per vote cast in the round, ′ matched edge occupies a slot at each endpoint, so each at most m in total. endpoint holds fewer than b(v) higher-priority matches, Theorem 4.6 (Work). PB-bM performs O(m′ ) and by induction SeqGreedy sees the same counts and work in expectation over the random priority order and takes the edge. The other direction rules out the one the randomization of the primitives of Section 4. way batching could lose an edge e taken by SeqGreedy, Proof. Charge everything to pins. The scans that an endpoint saturating while e is alive. The saturating round commits the entire vote set, thus, either e is fill vote(v) cost O(deg(v)) in total, and a pin (v, e) in it and is committed too, or the vote set and the is voted once and deleted once from N(v) and once earlier matches at that endpoint form b(v) higher- from vote(v). The root set of a round is collected priority matched edges. In the latter case, SeqGreedy among the round’s new votes, so it, too, is paid for by pins. The permutation, the sort, and the batched filled the endpoint before reaching e. Let Mg be the matching obtained by SeqGreedy increments are expected-linear. The randomized costs are unchanged. Generating under π. SeqGreedy adds an edge e iff every endpoint v is incident to fewer than b(v) higher-priority edges of π takes O(m) work, bucket sorting the lists edges(v) Mg , since it takes the edges in priority order and never by random priorities takes O(m′ ) work in expectation removes one, thus, the edges it holds when it reaches e (as in the proof of [14, Theorem 3.2]), and the batched are exactly the higher-priority edges of Mg . We prove realization of increment costs expected amortized that e ∈ M ⇔ e ∈ Mg by induction on π(e), assuming O(1) work per call (see above). The sets a round builds the equivalence for all higher-priority edges. (V (W ), sat, N(sat), finished, V (finished) \ sat, (⇒) Suppose e ∈ M . At each endpoint v, the edges and A) are realized by the same grouping primitive, of M incident on v number at most b(v) (I4), and e at expected work linear in the pins they touch. The is one of them, thus, at most b(v) − 1 of them have scans that fill vote(v), at initialization and in the refills, higher priority than e. By induction, the higher-priority only advance next(v), and one that advances it by d edges of M at v are exactly the higher-priority edges costs O(d), thus, the scans cost O(m′ ) over all vertices. of Mg at v, therefore every endpoint of e holds fewer Every other pin operation occurs a constant number of than b(v) higher-priority edges of Mg , and SeqGreedy times over the whole run. Also v increments counter(e) at most once (Lemma 4.1). When e is removed, the adds e: e ∈ Mg . Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

deletion pass processes the pin once, marking e and deleting it from N(v) and vote(v), since each edge enters finished at most once, being removed, and struck from every N set, in its round. The b-matching bookkeeping is also O(1) per pin. Each vertex enters sat at most once: a saturated vertex has no alive incident edge (I1), and root sets hold only alive edges (I3), so it never reenters V (W ). Hence the sat filter and the bcount updates run over the pins of the round’s matched edges, and the construction of N(sat), finished, and V (finished) \ sat runs over the pins of the round’s finished edges. Every edge is matched at most once and finished at most once, so all of this is O(1) per pin. A round collects its root set among its newly voted edges A, at O(1) per new vote, and each pin is voted at most once. The initialization, the scan forming the initial root set, and the loop control cost O(m′ + m + n) = O(m′ ) in total, using n ≤ m′ and the bound of at most m iterations (Theorem 4.3). Summing the per-pin charges and adding the randomized costs gives O(m′ ) expected work. 4.3 Fork–join structure. PB-bM is a sequence of rounds, and each round is a nested fork-join computation: the outer parfor forks one thread per vertex, and each vertex thread itself forks one thread per vote to increment edge counters. The while loop is serial: each round’s fork tree must fully join before the next round begins, so the rounds form a chain of join barriers. The depth of a round is that of its spawn trees, O(log m′ ), plus the cost of the heaviest leaf, which is a vertex refilling its vote set. With the k-entry form of findNext (introduced above) that refill costs O(log2 m′ ) depth, so a round has depth O(log2 m′ ). Taken literally as a serial scan the refill would instead cost Ω(deg(v)) in a single round, so this primitive is not a convenience but a requirement. The depth is the number of rounds times the per-round depth. Bounding the number of rounds is the subject of Subsection 4.4.

w.h.p. [14]. The bcount updates and the increment calls of a round are grouped sums at O(log m′ ) depth, and the sets of a round (sat, finished, A, and the new root set) are built by the same grouping primitive at logarithmic depth w.h.p. (primitive introduced when describing the algorithm in Section 4. A primitive of [14] on an input of size k ≤ m′ has O(log k) depth w.h.p. in k. As in [14], we take the failure probability relative to m′ rather than k, which gives O(log m′ ) depth with failure probability at most (m′ )−c for the constant c of Section 3, whatever k is. The one step above O(log m′ ) is the refill: the extension of findNext that returns the next alive entries up to the remaining capacity costs O(log2 d) depth for a slide of distance d ≤ deg(v). The refills run in parallel, so a round has depth O(log2 m′ ) w.h.p. Next, we bound the number of rounds and the depth of the algorithm. Theorem 4.8 (PB-bM depth). For every priority order, PB-bM performs at most m rounds. Its depth is O(m log2 m′ ) w.h.p. Proof. Every round commits its root set. The root set is not empty, since the highest-priority alive edge is always a root (proof of Theorem 4.3). A root is alive by (I3) of Lemma 4.2, the round removes it as part of finished, and a removed edge is never alive again. Thus, every round commits at least one edge that no earlier round committed, and there are at most m rounds. By Lemma 4.7, applied with the exponent raised by one, every round has O(log2 m′ ) depth w.h.p. A union bound over the at most m ≤ m′ rounds keeps the failure probability within the convention of Section 3. The initialization generates π and sorts the lists edges(v) in O(log m′ ) depth w.h.p. [14], and its scans of the lists cost no more depth than a refill. Multiplying the number of rounds by the depth of a round gives the bound.

The bound of Theorem 4.8 is loose. It holds for every priority order, and it does not depend on the rank r, on the capacities of vertices, or on the degrees of the vertices. On the star graph example of Section 4, the Lemma 4.7 (Depth of a round). Each round of algorithm finishes in one round for every priority order, PB-bM has O(log2 m′ ) depth w.h.p. while the bound allows m rounds. Under a uniformly random priority order the algorithm may perform far Proof. A round is a constant number of parfors fewer rounds, but the current bound does not capture whose bodies are primitive calls, so its depth is this. Proving a tighter bound on the number of rounds the depth of the costliest primitive plus the spawn in terms of r and the largest vertex capacity β is left to ′ trees. Each parfor ranges over at most m pins and future work. ′ adds O(log m ) depth. Committing W and marking done have O(1) bodies. The deletion pass is a 5 Experimental evaluation. In this section, batch of at most m′ deletions from the sets N(·) and we report our experimental results for the proposed vote(·), grouped by set and applied at O(log m′ ) depth algorithm and competitors. We run experiments on 4.4 Depth analysis. The fork–join structure of Section 4 leaves two quantities to bound: the depth of one round and the number of rounds.

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

uniform capacity b(v) ∈ {1, 3, 5}. All prior parallel competitors are limited to capacity b ≡ 1. The priorities of our matching are set to negative edge size. This prioritizes smaller edges first and should lead to bigger sized matchings. We use the edge id as tie-breaker. Furthermore, we test the impact of perturbing the priorities with random numbers from the start. 5.1 Methodology. Our experiments were run on a machine outfitted with a NVIDIA RTX 4090 and a 16-core Intel Xeon w5-3435X running at 3.10 GHz equipped with a L3 cache of 45 MB and 128 GB RAM. We repeated every experiment three times, while ordering all runs randomly and never running experiments in parallel. We use the median for averaging runs of one instance and the geometric mean to average across instances. The running time for algorithms on the GPU does not include the conversion and copying of the hypergraph to it, since our algorithm is usually a step in a bigger computation. The CPU competitor algorithms’ running time also do not include the initial setup of the data structures and reads from disk. Data set. We use the data set described by Reinstädtler et al. [62] for hypergraph matching. The 91 instances stem from the SAT competition 2014 [9], non-linear programming problems [64], general matrices from the Suite Sparse Collection [26], the DAC challenge [67] and data collected from wikipedia [63]. Compared algorithms. Main competitor is the algorithm HLM-CUDA from [62] that uses small random noise to speed up computation and limited to capacity b ≡ 1. The Greedy method in [37] uses data structures optimized to run a local search afterward, so we provide a simpler and faster implementation called SeqGreedy (1.95 times on average). We implemented our two versions of our algorithm PB-bM with batch and single voting (SV) in CUDA 12.8. The sorting of the adjacent edges is done in parallel on the GPU and included in the overall running time. If the number of adjacent edges exceeds ten thousand, sorting is done on the CPU and transfer time for this is included in the running time.

Rel. Size 1.0 0.8

DAC12 NLP Other SAT14 Wiki

0.6 0.4 0.2 0.0

HLM:C GPU

PB-bM

PB-bM (SV) SeqGreedy

Figure 5.1: Quality Comparison for Hypergraph 1Matching. PB-bM achieves the same results as SeqGreedy. Speedup (higher is better) DAC12 NLP Other SAT14 Wiki

101

100

HLM:C GPU

PB-bM

PB-bM (SV)

Figure 5.2: Speedup over SeqGreedy for Hypergraph 1Matching. HLM-CUDA uses random noise to speed-up computation.

produces worse results (reaching 79.9 to 92.6 % in size) since it uses small perturbations on the edge weights to speed up computations. Running time. Figure 5.2 shows the speedup over the SeqGreedy algorithm. Our algorithms are slower than HLM-CUDA by a factor of 3.28x to 9.7x, but still achieve a speedup of 1.07 to 6.43 times. Arguably, this difference can be explained by the stricter priority 5.2 Results. We discuss the results for capac- that our algorithm follows and the resulting bigger ity 1 matchings and higher capacities b ∈ {3, 5}. Fur- matchings. There is no difference between single-vote thermore, we show the impact of changed orderings in- and the batch voting algorithm, as the capacity is 1 and per vertex we cast one vote at max. duced by random noise. 5.2.1 1-matching. For capacity of b ≡ 1, we compare with HLM-CUDA, which is a true GPU implementation by [62] using small random perturbations to speed up their matching process between rounds. Quality comparison. Our algorithms produces the same matchings as the SeqGreedy algorithms, as shown in Figure 5.1. As expected, the voting mechanism does not impact the quality. The competing HLM-CUDA

5.2.2 b-matching. For higher capacities of 3 and 5, our algorithms match the output of state-of-theart greedy CPU methods. There is no difference and we place the plots in the Appendix (Figure C.1 and C.2). Running time. The speedups over the SeqGreedy algorithm are shown in Figure 5.3 and 5.4. Our new algorithms are up to 7.68 times faster than the SeqGreedy baseline when using the edge sized induced priorities.

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

Speedup (higher is better)

Speedup (higher is better) DAC12 NLP Other SAT14 Wiki 100 PB-bM

100

PB-bM (SV)

Figure 5.3: Speedup over SeqGreedy for capacity b ≡ 3. Speedup (higher is better) DAC12 NLP Other SAT14 Wiki

100 PB-bM

PB-bM (SV)

Figure 5.4: Speedup over SeqGreedy for capacity b ≡ 5.

On SAT14 hypergraphs we get the highest speedups, closely followed by the DAC12 instances, similar to the results on b ≡ 1. The Wiki and Other instances are the most challenging instances in the data set, with a speedup less than 1.08 and 1.33 times respectively. This is most-likely due to the structure of the hypergraphs. The difference between single-vote and batch vote is measurable for b ≡ 3, allowing multiple votes enables an average relative speedup of between 1.11 (Wiki) and 2.55 times (SAT14). For the Wiki instance we see a slow down to 0.97 times the running time of the greedy baseline. For higher capacities (b ≡ 5) on the Other hypergraphs, single voting slows down to 0.53 times the greedy baseline, whereas batch voting maintains a 1.05x speedup, running 1.98x faster. The overall gap reaches 3x on the SAT14 instances. 5.3 Priorities and randomness. We added uniformly distributed noise of two levels (U = 10 and U = 100) to randomize the ordering induced by the edge size. The randomization was done beforehand, simulating changed orderings. We ran the SeqGreedy and our algorithms on these new priorities.

DAC12 NLP Other SAT14 Wiki

101

HLM:C HLM HLM Pb-bM PB-bM PB-bM GPU U=10 U=100 U=0 U=10 U=100

Figure 5.5: Speedup over SeqGreedy with different levels of uniform randomness in the given priority (U = 0, 10, 100). Capacity is b ≡ 1.

Running time. In Figure 5.6 the relative speed-up to the SeqGreedy method on the respective level of noise is shown. For noise of up to size U = 10 we can see a speed-up for our method to 19.07 times on the DAC12 instances. Interestingly, with increasing noise (U = 100) for these hypergraphs the speed-up drops to 10.92. This trend also holds for all except the Wiki instance, which gains a higher speed up with more noise. Overall we can see that our algorithm benefits from more randomized orderings with less tie-breaking by id. Number of rounds. Figure 5.7 shows the number of rounds performed with batch and single-voting. We can clearly see that the number of rounds is reduced with higher randomness in the given permutation when using batch voting. For single voting, the number of rounds does stay the same or increase with higher randomness for some data sets. Quality. There is no general trend in the relative size of the matchings when applying random noise, see Figure 5.8. While in most sets, the size decreases (Other,SAT14) or stays the same (DAC12), in the NLP instances it even increases. However, both algorithms, our and the greedy baseline, produce the same matchings on a given priority. We also tested the impact of noise for lower capacities b ≡ 1, 3 (Figure 5.5 & 5.9) and were able to reproduce the speed-ups by noise. For b ≡ 1 introducing noise also helps the HLM-CUDA algorithm, reaching speed ups of up to 68 times. In general, we can observe that the priorities have a high impact on the overall performance of all parallel algorithms. The competitor HLM-CUDA relaxes the orderings and produces worse matchings, while our methods are guaranteed to produce the matching induced by the priorities.

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

Speedup (higher is better)

Rel. Size 1.0

101

100

DAC12 NLP Other SAT14 Wiki PB-bM

U=10

0.8 0.4 0.2 0.0

U=100

DAC12 NLP Other SAT14 Wiki

0.6

U=0

U=10

U=100

Figure 5.6: Speedup over SeqGreedy with different Figure 5.8: Relative size of matching with different levels of uniform randomness with given priority (U = levels of uniform randomness applied to the edge sized 0, 10, 100). Capacity is b ≡ 5. induced priority (U = 0, 10, 100). Capacity is b ≡ 5. Rounds

Speedup (higher is better) DAC12 NLP Natural SAT14 Wiki

102 101 U=0

U=10

U=100 SV U=0 SV U=10SV U=100

Figure 5.7: Number of rounds with different levels of uniform randomness (U = 10, 100) for batch and single vote (SV). Capacity is b ≡ 5. 6 Conclusion. We presented PB-bM, a parallel algorithm for maximal b-matching in hypergraphs. Every vertex votes at once for as many of its highestpriority edges as it has capacity left. An edge joins the matching once all of its vertices have voted for it. For a given priority order the algorithm returns the lexicographically first maximal b-matching, i.e., the same matching as the sequential greedy algorithm. The output does not depend on how the rounds are scheduled or on the number of cores. The algorithm performs O(m′ ) expected work in the binary fork–join model, where m′ is the number of pins. The algorithm performs at most m rounds and has depth O(m log2 m′ ) w.h.p. This bound is loose, since it does not depend on the rank or on the capacities. Proving a tighter bound on the number of rounds under a random priority order is left to future work. Batching is what removes the serialization that vertex capacities introduce. A vertex that votes for one edge per round fills its slots one at a time. Our experiments show this effect. For capacity b(v) = 3,

101

100

DAC12 NLP Other SAT14 Wiki PB-bM

U=10

U=100

Figure 5.9: Speedup over SeqGreedy with different levels of uniform randomness in the given priority(U = 0, 10, 100). Capacity is b ≡ 3. batch voting is on average between 1.12 and 2.54 times faster than single voting, and it needs fewer rounds once the priorities carry more randomness. With higher level of randomness in the priorities, our algorithms can produce a speedup of up to 19.07 times over the greedy baseline, while producing the same matching.

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

References

[10] S. Bhattacharya, M. Gupta, and D. Mohan, Improved algorithm for dynamic b-matching, [1] F. Ahmed, J. P. Dickerson, and M. Fuge, in Proceedings of the 25th Annual European SymDiverse weighted bipartite b-matching, in Proceedposium on Algorithms (ESA), vol. 87 of Leibniz ings of the 26th International Joint Conference International Proceedings in Informatics (LIPIcs), on Artificial Intelligence (IJCAI), 2017, pp. 35–41, Schloss Dagstuhl – Leibniz-Zentrum für Inforhttps://doi.org/10.24963/ijcai.2017/6. matik, 2017, pp. 15:1–15:13, https://doi.org/10. 4230/LIPIcs.ESA.2017.15. [2] K. J. Ahn and S. Guha, Near linear time approximation schemes for uncapacitated and capacitated [11] S. Bhattacharya, M. Henzinger, and b-matching problems in nonbipartite graphs, in ProG. F. Italiano, Design of dynamic algoceedings of the 25th Annual ACM-SIAM Symrithms via primal-dual method, in Proceedposium on Discrete Algorithms (SODA), SIAM, ings of the 42nd International Colloquium 2014, pp. 239–258, https://doi.org/10.1137/1. on Automata, Languages, and Programming 9781611973402.18. (ICALP), vol. 9134 of Lecture Notes in Computer Science, Springer, 2015, pp. 206–218, [3] S. Albers and S. Schubert, Online b-matching https://doi.org/10.1007/978-3-662-47672-7_17. with stochastic rewards, in Proceedings of the 50th International Conference on Current Trends in [12] M. Bienkowski, D. Fuchssteiner, Theory and Practice of Computer Science (SOFJ. Marcinkowski, and S. Schmid, Online SEM), vol. 15538 of Lecture Notes in Computer dynamic B-matching: With applications to reconScience, Springer, 2025, pp. 37–50, https://doi. figurable datacenter networks, ACM SIGMETRICS org/10.1007/978-3-031-82670-2_4. Performance Evaluation Review, 48 (2020), pp. 99– 108, https://doi.org/10.1145/3453953.3453976. [4] N. Alon, L. Babai, and A. Itai, A fast and simple randomized parallel algorithm for the max[13] G. E. Blelloch, A. Brady, L. Dhulipala, imal independent set problem, Journal of AlgoJ. T. Fineman, and J. Lo, Parallel batchrithms, 7 (1986), pp. 567–583, https://doi.org/10. dynamic maximal independent set, 2026, https:// 1016/0196-6774(86)90019-2. arxiv.org/abs/2604.07515. [5] R. P. Anstee, A polynomial algorithm for b[14] G. E. Blelloch and A. C. Brady, Paralmatchings: An alternative approach, Information lel batch-dynamic maximal matching with constant Processing Letters, 24 (1987), pp. 153–157, https: work per update, in Proceedings of the 37th ACM //doi.org/10.1016/0020-0190(87)90178-5. Symposium on Parallelism in Algorithms and Architectures (SPAA ’25), 2025, pp. 429–442, https: [6] M. Bayati, C. Borgs, J. Chayes, and //doi.org/10.1145/3694906.3743313. R. Zecchina, Belief propagation for weighted bmatchings on arbitrary graphs and its relation to [15] G. E. Blelloch, J. T. Fineman, Y. Gu, and linear programs with integer solutions, SIAM JourY. Sun, Optimal parallel algorithms in the binarynal on Discrete Mathematics, 25 (2011), pp. 989– forking model, in Proceedings of the 32nd ACM 1011, https://doi.org/10.1137/090753115. Symposium on Parallelism in Algorithms and Architectures (SPAA ’20), 2020, pp. 89–102, https: [7] P. Beame and M. Luby, Parallel search for max//doi.org/10.1145/3350755.3400227. imal independence given minimal dependence, in Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 1990, [16] G. E. Blelloch, J. T. Fineman, and J. Shun, Greedy sequential maximal independent set and pp. 212–218. matching are parallel on average, in Proceedings of the 24th ACM Symposium on Paral[8] S. Behnezhad, M. Hajiaghayi, and D. G. lelism in Algorithms and Architectures (SPAA Harris, Exponentially faster massively parallel ’12), 2012, pp. 308–317, https://doi.org/10.1145/ maximal matching, Journal of the ACM, 70 (2023), 2312005.2312058. pp. 34:1–34:18, https://doi.org/10.1145/3617360. Preliminary version in FOCS 2019. [17] G. E. Blelloch, R. Peng, and K. Tang[9] A. Belov, D. Diepold, M. Heule, and wongsan, Linear-work greedy parallel approximate M. Järvisalo, The SAT competition 2014. http:// set cover and variants, in Proceedings of the 23rd www.satcompetition.org/2014/index.shtml, 2014. ACM Symposium on Parallelism in Algorithms

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

and Architectures (SPAA), ACM, 2011, pp. 23–32, [26] T. A. Davis and Y. Hu, The university of https://doi.org/10.1145/1989493.1989497. florida sparse matrix collection, ACM Trans. on Math. Software, (2011), https://doi.org/10.1145/ [18] F. Brandt-Tumescheit, F. Gerharz, and 2049662.2049663. H. Meyerhenke, A fully-dynamic approximation algorithm for maximum weight b-matchings [27] L. Dhulipala, M. Dinitz, J. Łącki, and S. Mitrović, Parallel set cover and hypergraph in graphs, in Complex Networks & Their Apmatching via uniform random sampling, in 38th plications XIII (COMPLEX NETWORKS 2024), International Symposium on Distributed Computvol. 1190 of Studies in Computational Intelligence, ing (DISC), vol. 319 of LIPIcs, Schloss Dagstuhl Springer, 2025, pp. 139–151, https://doi.org/10. – Leibniz-Zentrum für Informatik, 2024, pp. 19:1– 1007/978-3-031-82439-5_12. 19:23, https://doi.org/10.4230/LIPIcs.DISC.2024. 19. [19] N. Buchbinder, K. Jain, and J. Naor, Online primal-dual algorithms for maximizing adauctions revenue, in Proceedings of the 15th An- [28] J. Edmonds and E. L. Johnson, Matching, Euler tours and the Chinese postman, Mathematnual European Symposium on Algorithms (ESA), ical Programming, 5 (1973), pp. 88–124, https: vol. 4698 of Lecture Notes in Computer Science, //doi.org/10.1007/BF01580113. Springer, 2007, pp. 253–264, https://doi.org/10. 1007/978-3-540-75520-3_24. [29] S. M. Ferdous, A. Pothen, A. Khan, A. Panyala, and M. Halappanavar, A parallel ap[20] N. Calkin and A. Frieze, Probabilistic analyproximation algorithm for maximizing submodular sis of a parallel algorithm for finding maximal inb-matching, in Proceedings of the 2021 SIAM Condependent sets, Random Structures & Algorithms, ference on Applied and Computational Discrete Al1 (1990), pp. 39–50, https://doi.org/10.1002/rsa. gorithms (ACDA), SIAM, 2021, pp. 45–56, https: 3240010104. //doi.org/10.1137/1.9781611976830.5. [21] K. Choromanski, T. Jebara, and K. Tang, [30] M. Fischer and A. Noever, Tight analysis of Adaptive anonymity via b-matching, in Advances parallel randomized greedy MIS, ACM Transactions in Neural Information Processing Systems 26 on Algorithms, 16 (2020), pp. 6:1–6:13, https://doi. (NeurIPS), 2013, pp. 3192–3200. org/10.1145/3326165. [22] S. A. Cook, A taxonomy of problems with [31] H. N. Gabow, An efficient reduction technique fast parallel algorithms, Information and Confor degree-constrained subgraph and bidirected nettrol, 64 (1985), pp. 2–22, https://doi.org/10.1016/ work flow problems, in Proceedings of the 15th S0019-9958(85)80041-3. Annual ACM Symposium on Theory of Computing (STOC), ACM, 1983, pp. 448–456, https://doi. [23] S. A. Cook, Y. Filmus, and D. T. M. Lê, The org/10.1145/800061.808776. complexity of the comparator circuit value problem, ACM Transactions on Computation Theory, [32] H. N. Gabow, Data structures for weighted 6 (2014), pp. 15:1–15:44, https://doi.org/10.1145/ matching and extensions to b-matching and f 2635822. factors, ACM Transactions on Algorithms, 14 (2018), pp. 39:1–39:80, https://doi.org/10.1145/ [24] D. Coppersmith, P. Raghavan, and 3183369. M. Tompa, Parallel graph algorithms that are efficient on average, in 28th An- [33] H. N. Gabow and P. Sankowski, Algebraic alnual Symposium on Foundations of Comgorithms for b-matching, shortest undirected paths, puter Science (FOCS), 1987, pp. 260–269, and f -factors, in 54th Annual IEEE Symposium on https://doi.org/10.1109/SFCS.1987.34. Foundations of Computer Science (FOCS), IEEE, 2013, pp. 137–146, https://doi.org/10.1109/FOCS. [25] W. H. Cunningham and I. Alfred B. Marsh, 2013.23. A primal algorithm for optimum matching, in Polyhedral Combinatorics, vol. 8 of Mathematical [34] O. Garrido, S. Jarominek, A. Lingas, and Programming Studies, Springer, 1978, pp. 50–72, W. Rytter, A simple randomized parallel algohttps://doi.org/10.1007/BFb0121194. rithm for maximal f -matchings, in LATIN ’92: 1st

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

Latin American Symposium on Theoretical Inforpp. 77–80, https://doi.org/10.1016/0020-0190(86) matics, vol. 583 of Lecture Notes in Computer Sci90144-4. ence, Springer, 1992, pp. 165–176, https://doi.org/ [43] T. Jebara, J. Wang, and S.-F. Chang, Graph 10.1007/BFb0023827. construction and b-matching for semi-supervised [35] M. Ghaffari and C. Grunau, Towards true learning, in Proceedings of the 26th Internawork-efficiency in parallel derandomization: MIS, tional Conference on Machine Learning (ICML), maximal matching, and hitting set, in 2025 IEEE ACM, 2009, pp. 441–448, https://doi.org/10.1145/ 66th Annual Symposium on Foundations of Com1553374.1553432. puter Science (FOCS), IEEE, 2025, pp. 2694–2727, [44] B. Kalyanasundaram and K. Pruhs, An https://doi.org/10.1109/FOCS63196.2025.00139. optimal deterministic algorithm for online b[36] M. Ghaffari, C. Grunau, and S. Mitrović, matching, Theoretical Computer Science, 233 Massively parallel algorithms for b-matching, in (2000), pp. 319–325, https://doi.org/10.1016/ Proceedings of the 34th ACM Symposium on ParS0304-3975(99)00140-1. allelism in Algorithms and Architectures (SPAA), 2022, pp. 35–44, https://doi.org/10.1145/3490148. [45] R. M. Karp and A. Wigderson, A fast parallel algorithm for the maximal independent set problem, 3538589. Journal of the ACM, 32 (1985), pp. 762–773, https: [37] E. Großmann, F. Joos, H. Reinstädtler, //doi.org/10.1145/4221.4226. and C. Schulz, Engineering hypergraph bmatching algorithms, Journal of Graph Algorithms [46] P. Kelsen, On the parallel complexity of comand Applications, 30 (2026), pp. 1–24, https://doi. puting a maximal independent set in a hyperorg/10.7155/jgaa.v30i1.3166. graph, in Proceedings of the 24th Annual ACM Symposium on Theory of Computing (STOC), [38] O. Hanguir and C. Stein, Distributed algoACM, 1992, pp. 339–350, https://doi.org/10.1145/ rithms for matching in hypergraphs, in Approx129712.129745. imation and Online Algorithms (WAOA 2020), vol. 12806 of Lecture Notes in Computer Sci- [47] A. Khan, A. Pothen, and S. M. Ferdous, ence, Springer, 2021, pp. 30–46, https://doi.org/ Parallel algorithms through approximation: b-edge 10.1007/978-3-030-80879-2_3. cover, in 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, [39] D. G. Harris, Derandomized concentration 2018, pp. 22–33, https://doi.org/10.1109/IPDPS. bounds for polynomials, and hypergraph maximal 2018.00013. independent set, in Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algo- [48] A. Khan, A. Pothen, M. M. A. Patwary, rithms (SODA), SIAM, 2018, pp. 2161–2180, https: M. Halappanavar, N. R. Satish, N. Sun//doi.org/10.1137/1.9781611975031.141. daram, and P. Dubey, Designing scalable bmatching algorithms on distributed memory mul[40] D. G. Harris, Distributed local approximatiprocessors by approximation, in Proceedings of tion algorithms for maximum matching in graphs the International Conference for High Performance and hypergraphs, SIAM Journal on Computing, Computing, Networking, Storage and Analysis 49 (2020), pp. 711–746, https://doi.org/10.1137/ (SC), IEEE, 2016, pp. 773–783, https://doi.org/ 19M1279241. Preliminary version in FOCS 2019. 10.1109/SC.2016.65. [41] C.-C. Huang and F. Sellier, Maximum weight b-matchings in random-order streams, in Proceed- [49] A. Khan, A. Pothen, M. M. A. Patwary, N. R. Satish, N. Sundaram, F. Manne, ings of the 30th Annual European Symposium M. Halappanavar, and P. Dubey, Effion Algorithms (ESA), vol. 244 of Leibniz Incient approximation algorithms for weighted bternational Proceedings in Informatics (LIPIcs), matching, SIAM Journal on Scientific ComputSchloss Dagstuhl – Leibniz-Zentrum für Inforing, 38 (2016), pp. S593–S619, https://doi.org/10. matik, 2022, pp. 68:1–68:14, https://doi.org/10. 1137/15M1026304. 4230/LIPIcs.ESA.2022.68. [42] A. Israeli and A. Itai, A fast and simple [50] C. Koufogiannakis and N. E. Young, Disrandomized parallel algorithm for maximal matchtributed algorithms for covering, packing and maxing, Information Processing Letters, 22 (1986), imum weighted matching, Distributed Comput-

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

ing, 24 (2011), pp. 45–63, https://doi.org/10.1007/ s00446-011-0127-7.

bility, in Proceedings of the 6th International Conference on Combinatorial Optimization and Applications (COCOA), vol. 7402 of Lecture Notes in Computer Science, Springer, 2012, pp. 200–211, https://doi.org/10.1007/978-3-642-31770-5_18.

[51] J. Łącki, S. Mitrović, S. Ramachandran, and W.-H. Sheu, Faster MPC algorithms for approximate allocation in uniformly sparse graphs, in Proceedings of the 37th ACM Symposium on Paral- [60] O. Parekh and D. Pritchard, Generalized hypergraph matching via iterated packing and local lelism in Algorithms and Architectures (SPAA ’25), ratio, in Approximation and Online Algorithms ACM, 2025, pp. 339–349, https://doi.org/10.1145/ (WAOA 2014), vol. 8952 of Lecture Notes in Com3694906.3743319. puter Science, Springer, 2015, pp. 207–223, https: [52] Q. C. Liu, Y. Ke, and S. Khuller, Scal//doi.org/10.1007/978-3-319-18263-6_18. able auction algorithms for bipartite maximum matching problems, in Approximation, Random- [61] H. Reinstädtler, S. M. Ferdous, A. Pothen, B. Uçar, and C. Schulz, Semi-streaming alization, and Combinatorial Optimization (APgorithms for hypergraph matching, in 33rd AnPROX/RANDOM), vol. 275 of Leibniz Internanual European Symposium on Algorithms (ESA), tional Proceedings in Informatics (LIPIcs), Schloss vol. 351 of LIPIcs, Schloss Dagstuhl – LeibnizDagstuhl – Leibniz-Zentrum für Informatik, 2023, Zentrum für Informatik, 2025, pp. 79:1–79:19, pp. 28:1–28:24, https://doi.org/10.4230/LIPIcs. https://doi.org/10.4230/LIPIcs.ESA.2025.79. APPROX/RANDOM.2023.28.

[53] M. Luby, A simple parallel algorithm for the [62] H. Reinstädtler, C. Schulz, N. Sitchinava, and F. Walliser, Efficient parallel algorithms maximal independent set problem, SIAM Journal for hypergraph matching, in Euro-Par 2026: Paron Computing, 15 (1986), pp. 1036–1053, https: allel Processing, vol. 16782 of Lecture Notes in //doi.org/10.1137/0215074. Computer Science, Springer, 2026, pp. 526–540, [54] A. Mehta, A. Saberi, U. Vazirani, and https://doi.org/10.1007/978-3-032-35251-4_36. V. Vazirani, Adwords and generalized online matching, Journal of the ACM, 54 (2007), pp. 22:1– [63] H. Reinstädtler, S. Ferdous, A. Pothen, B. Uçar, and C. Schulz, Wiki hypergraphs 22:19, https://doi.org/10.1145/1284320.1284321. for the paper "semi-streaming algorithms for [55] J. Mestre, Greedy in approximation algorithms, hypergraph matching", June 2025, https://doi. in Algorithms – ESA 2006, vol. 4168 of Lecorg/10.5281/zenodo.15778413, https://doi.org/10. ture Notes in Computer Science, Springer, 2006, 5281/zenodo.15778413. pp. 528–539, https://doi.org/10.1007/11841036_ [64] O. Schenk, A. Wächter, and M. Weiser, 48. Inertia-revealing preconditioning for large-scale [56] S. Miyano, The lexicographically first maximal nonconvex constrained optimization, SIAM Journal subgraph problems: P-completeness and NC algoon Scientific Computing, 31 (2009), pp. 939–960. rithms, Mathematical Systems Theory, 22 (1989), [65] A. Schrijver, Combinatorial Optimization: Polypp. 47–73, https://doi.org/10.1007/BF02088292. hedra and Efficiency, vol. 24 of Algorithms and [57] M. Müller-Hannemann and A. Schwartz, Combinatorics, Springer, 2003. Implementing weighted b-matching algorithms: Insights from a computational study, ACM Journal of [66] J. Shun, Practical parallel hypergraph algorithms, in Proceedings of the 25th ACM SIGPLAN SymExperimental Algorithmics, 5 (2000), p. 8, https: posium on Principles and Practice of Parallel Pro//doi.org/10.1145/351827.384250. gramming (PPoPP), ACM, 2020, pp. 232–249, [58] M. Naim and F. Manne, Scalable b-matching https://doi.org/10.1145/3332466.3374527. on GPUs, in 2018 IEEE International Parallel and Distributed Processing Symposium Workshops [67] N. Viswanathan, C. J. Alpert, C. C. N. Sze, Z. Li, and Y. Wei, DAC 2012 routability-driven (IPDPSW), IEEE, 2018, pp. 637–646, https://doi. placement contest and benchmark suite, in DAC org/10.1109/IPDPSW.2018.00104. ’12, P. Groeneveld, D. Sciuto, and S. Hassoun, eds., [59] M. E. Ouali and G. Jäger, The b-matching San Francisco, CA, USA, 2012, ACM, pp. 774–782, problem in hypergraphs: Hardness and approximahttps://doi.org/10.1145/2228360.2228500.

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

A Extended related work. This appendix gives the full discussion of related work summarized in Section 2. Parallel maximal matching and independent set. Computing a maximal matching in graphs, or the closely related maximal independent set (MIS), in parallel is a classical problem addressed by a long line of algorithms. Karp and Wigderson [45] gave the first NC algorithm for MIS, i.e., one running in polylogarithmic time on polynomially many processors. Luby [53] and Alon, Babai, and Itai [4] gave randomized O(log n)-round algorithms which were adapted to maximal matching by Israeli and Itai [42]. The degree-constrained generalization appeared early: Garrido et al. [34] gave an RNC (randomized NC) algorithm for maximal f matchings, the closest classical relative of parallel bmatching. Subsequent work has refined the round and work complexity substantially, including O(log log ∆)round maximal matching, where ∆ is the maximum degree, in the massively parallel (MPC) model [8] and nearly work-efficient deterministic algorithms [35]. Each of these computes some maximal solution, which depends on the schedule. None returns the specific solution a given sequential greedy algorithm would, which is precisely what reproducibility across machines and core counts requires. Greedy matching and dependence depth. Reproducing the solution obtained by a sequential greedy algorithm amounts to computing the lexicographically first maximal solution. For the lexicographically first maximal independent set this is P-complete [22, 56], so lexicographically first problems are in general resistant to parallelism under a fixed adversarial order. For matching on ordinary graphs the picture is different. That problem is complete for the class CC rather than known to be P-complete [23]. The standard remedy is to randomize the order. Coppersmith, Raghavan, and Tompa [24] and Calkin and Frieze [20] first established that the greedy algorithm is shallow on random graphs. Furthermore, Blelloch, Fineman, and Shun [16] proved the stronger statement that on any graph a uniformly random order yields a dependence depth of O(log2 m) w.h.p., where the dependence depth is the number of rounds obtained by repeatedly matching, in parallel, every edge having no higher-priority conflict. Fischer and Noever [30] subsequently tightened this bound to O(log m) w.h.p. Building on this framework, Blelloch and Brady [14] obtained a work-efficient parallel algorithm for maximal matching in hypergraphs with O(m′ ) expected work and O(log2 m) depth w.h.p. The parallel algorithm returns exactly the solution obtained by the sequential greedy maximal matching algorithm. Their approach is the starting point for the

design of our parallel algorithm for maximal b-matching in hypergraphs. The same lexicographically-first-underrandom-order principle has recently been extended to the parallel batch-dynamic maximal independent set problem [13]. No analogue of these round bounds is known once vertex capacities are considered. In Subsection 4.4 we give a simple bound on the number of rounds of our algorithm, and we leave a tighter bound to future work. Parallel hypergraph matching. Parallel algorithms for hypergraph matching have been developed along several methodological lines. The local-max approach of Reinstädtler et al. [62] adds, in each round, all locally maximal edges under freshly randomized weights, in the spirit of Luby’s MIS, and terminates in O(log m) rounds. The same authors also gave semi-streaming algorithms [61]. In the distributed and massively parallel models, Harris [40] and Hanguir and Stein [38] propose approximation algorithms, while Dhulipala et al. [27] gave PRAM (parallel random-access machine) and MPC algorithms for hypergraph matching together with the related set cover and packing problems, continuing the work-efficient parallel-greedy line of Blelloch, Peng, and Tangwongsan [17] and the practical sharedmemory framework of Shun [66]. A natural reduction takes maximal hypergraph matching to MIS on the line graph, to be solved by a parallel hypergraph-MIS algorithm [7, 39, 46]. However, the line graph may contain Ω(m2 ) edges, so the reduction is far from workefficient. None of these algorithms accounts for vertex capacities, and thus they do not solve the b-matching problem in hypergraphs. Sequential b-matching algorithms. b-matching in graphs is a thoroughly studied generalization of matching. Its polyhedral structure and exact polynomialtime solvability were established by Edmonds and Johnson [28], Cunningham and Marsh [25], and Anstee [5], and are surveyed by Schrijver [65]. Exact algorithms range from Gabow’s combinatorial reductions and blossom data structures [31, 32] to algebraic matrixmultiplication methods [33], with message-passing and LP-based solvers used in practice [6]. On hypergraphs the problem is considerably harder, computing a maximum b-matching is NP-hard and admits no PTAS [59]. The best known polynomial-time guarantees are LP-relative approximations [60]. Thus, the practical target is a maximal solution, produced in linear time by SeqGreedy. Greedy and approximation algorithms for b-matching are themselves well studied, including a 12 -approximation via k-extendible systems in O(βm) time [55], an early appearance of the factor β = maxv∈V b(v), near-linear-time approximation schemes [2], and careful engineering studies [37, 57]. All

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

of these, however, are sequential. C Additional experimental results. Parallel b-matching algorithms. Beyond the early RNC algorithm of Garrido et al. [34] mentioned above, Rel. Size the literature on parallel b-matching offers only ap1.0 proximation guarantees, and it concerns ordinary 0.8 graphs almost exclusively. For shared memory, the DAC12 1 NLP b-Suitor family [48, 49] computes 2 -approximations 0.6 Other that scale to billions of edges, with a GPU imSAT14 0.4 Wiki plementation [58] and extensions to submodular b0.2 matching [29] and b-edge-cover [47]. Auction algorithms give (1 − ε)-approximate maximum-cardinality bipar0.0 PB-bM PB-bM (SV) SeqGreedy tite b-matchings in the work–depth model [52]. In the distributed model, weighted hypergraph b-matching has also been addressed [50]. In the massively parallel (MPC) model, Ghaffari, Grunau, and Mitro- Figure C.1: There is no difference in the quality of the ¯ vić [36] gave a (1 + ε)-approximation in O(log log d) computed matchings for b(v) = 3. ¯ rounds, where d is the average degree, and recent work improves the round complexity of approximate allocation on sparse graphs [51]. Rel. Size Other models. Finally, b-matching has been studied 1.0 extensively in the dynamic [10, 11, 18], streaming [41], 0.8 and online [3, 19, 44, 54] settings. These models are DAC12 orthogonal to the problem considered in this paper and NLP 0.6 Other the associated algorithms are not discussed in detail and SAT14 0.4 are not listed in Table 2.1. Wiki 0.2 B Illustrative example. In Figure B.1, we provide an example of PB-bM execution on a small hypergraph with three edges. The priority order is π(e1 ) = 1, π(e2 ) = 2, π(e3 ) = 3, and the capacity of every vertex is listed in the table on the left of the figure. Each edge is the shaded region around its vertices, in its own color and labeled with its priority π(e). In Figure B.1(b) the two matched edges are drawn bold and e3 , left unmatched, is in faded gray. Arrows indicate the votes cast at initialization. On Figure B.1(a), vertices v1 and v3 each have two slots and vote for their top two edges at once, thus e1 and e2 collect a vote from every endpoint in the same round, while e3 still lacks v4 ’s vote. The root set W = {e1 , e2 } therefore contains two edges sharing v1 , which a singlevote rule could never produce. Figure B.1(b) shows that committing W saturates v1 , v2 , v4 , v5 , so e3 is removed through v4 even though v3 keeps a free slot. The sets vote(v3 ) and vote(v6 ) are empty, and the execution of PB-bM ends after this single round. An algorithm allowing v1 only one vote per round would instead need two rounds here, one per matched edge.

0.0

PB-bM

PB-bM (SV)

SeqGreedy

Figure C.2: There is no difference in the quality of the computed matchings for b(v) = 5. D D.1

Proofs. Proof of Lemma 4.1.

Proof. A vote, once cast, stays until its edge dies, since the deletion pass is the only place a vote set shrinks, and the scans that fill vote sets only move forward along edges(v), thus no edge is voted for twice. Validity holds because the roots at a vertex all lie in its vote set, which never exceeds the capacity the vertex has left. No root escapes the collection from A, because an alive edge whose counter was already full at the previous collection joined that root set and was removed with it. The set vote(v) shrinks only in the deletion pass, which deletes from it exactly the edges of finished, the edges removed in that round, thus vote(v) loses an edge only when that edge is removed. The initialization takes the first b(v) entries of edges(v) and leaves next(v) on the entry after them. A refill only advances next(v), therefore next(v) passes each entry of edges(v) at most once, and the entries it has passed form a growing prefix.

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

v

b(v)

v1 v2 v3 v4 v5 v6

2 1 2 1 1 1

π(e1 )=1

e1 ∈ M

v2

v2 bcount(v1 )=2

v1

v3

v4

v5 π(e2 )=2

bcount(v3 )=1

v1

v6

v5

π(e3 )=3

e2 ∈ M

(a) after initialization

v3

v4

v6 e3 ∈ E \ M

(b) after the round

Figure B.1: Example: PB-bM execution on a small hypergraph with three edges. The table on the left lists the capacity of every vertex. An edge enters vote(v) only when next(v) passes its entry and it is alive, hence at most once. It cannot return after leaving, since it leaves only by dying, and the scans add alive edges only. A vertex increments counter(e) exactly when it adds e to its vote set, hence at most once, and only endpoints of e do so, since vote(v) ⊆ edges(v). No counter is ever decremented. Thus, counter(e) counts the vertices that have ever added e to their vote sets. While e is alive, each of them still votes for e, thus counter(e) is the number of current voters, it never exceeds |V (e)|, and a full counter means that every endpoint votes for e. D.2

Proof of Lemma 4.2.

Proof. The invariants hold before the first iteration: M is empty and bcount(v) = 0. No edge is removed, and b(v) ≥ 1 leaves every vertex unsaturated. The set vote(v) holds the b(v) highest-priority edges of edges(v), which is (I2) for bcount(v) = 0. The initial root set is computed over all of E, every edge alive, which is (I3). We show that one iteration preserves the four, assuming them at its start. The loop exits at such a start, thus the invariants hold there as well. (I1). bcount changes only at vertices of V (W ), so a vertex reaches b(v) in this round exactly if it lies in V (W ) with its new count at b(v), which is membership in sat. For v ∈ sat, the set N(v) holds every edge alive at the round’s start that is incident on v. All of them enter finished = W ∪N(sat) and are removed. A vertex saturated in an earlier round has no alive incident edge already at the round’s start (I1), and bcount never decreases, thus after the round no alive edge has a saturated vertex.

(I2). If no edge at v was removed this round, then v ∈ / V (finished), and since the committed edges of any v ∈ V (W ) lie in W ⊆ finished, also v ∈ / V (W ), so the alive edges at v, the count bcount(v), and vote(v) are all unchanged, and (I2) carries over. Otherwise v ∈ V (finished). Suppose v is unsaturated when the next iteration begins. Then v ∈ / sat, the vertex was unsaturated already at the round’s start, as bcount never decreases, and the round refills v. After the deletion pass, vote(v) is its old set of edges minus the set of removed edges. It is still a prefix of the alive edges in priority order: an alive edge of higher priority than a surviving member was in the old prefix (I2) and, being alive, was not deleted. It also has room: vote(v) lost at least its |Cv | committed members, while bcount(v) increased by exactly |Cv |, so |vote(v)| ≤ b(v) − bcount(v) holds for the new count. Every alive edge among the entries next(v) has passed is already in vote(v): it was alive when next(v) passed it, thus it was added, and it has not left since. The refill therefore extends the prefix by exactly the next alive edges in edges(v), until |vote(v)| = b(v) − bcount(v) or no entries remain, which restores (I2). (I3). Every edge of the new root set is collected from A with a full counter, and it is alive when the next iteration begins: it was alive when the refill added it, and the round removes nothing after its deletion pass. Conversely, let e be alive at the next start with counter(e) = |V (e)|. If e gained no vote in this round, its counter was full already at the round’s start, and e was alive then, thus e ∈ W by (I3), and the round committed and removed it, a contradiction. Therefore, e gained a vote, lies in A, and is collected.

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

Hence the new root set is exactly the set of alive edges with a full counter. (I4). Let v ∈ V (W ), and let Cv = {e ∈ W : v ∈ e} be the roots committed at v. Each e ∈ Cv is alive with a full counter (I3), thus, by the persistence of votes (Lemma 4.1), every endpoint of e votes for it: Cv ⊆ vote(v). The vertex v is unsaturated, its edges in W being alive (I1), thus by (I2) |vote(v)| ≤ b(v) − bcount(v), and bcount(v) increases by |Cv | ≤ b(v) − bcount(v), to at most b(v). No other bcount changes. The edges of W are new to M : they are alive (I3), while an edge committed earlier was removed in its round, as a member of its finished, and stays removed. Thus, M ∪W adds exactly the edges of W , and bcount(v) remains the number of edges of M incident on v.

Copyright © 2027 by SIAM Unauthorized reproduction of this article is prohibited

Related documents

• Double-Partition Coloring problem: a unified approach for conflict-free coloring of hypergraphs and other coloring problems in graphs#1233193
• Compact Partial Symmetry Breaking for Graph Search Problems#1035952
• The Popular Dimension of Matchings#971711
• Digraphs of Large Girth and Dichromatic Number in Tournaments with Large Dichromatic Number#1036284
• Ramsey achievement games on graphs : algorithms and bounds#796468