pith. sign in

arxiv: 2604.07515 · v1 · submitted 2026-04-08 · 💻 cs.DS · cs.DC

Parallel Batch-Dynamic Maximal Independent Set

Guy Blelloch , Andrew Brady , Laxman Dhulipala , Jeremy Fineman , Jared Lo This is my paper

Pith reviewed 2026-05-10 16:53 UTC · model grok-4.3

classification 💻 cs.DS cs.DC
keywords batch-dynamic algorithmsmaximal independent setparallel graph algorithmsdynamic graphsinfluence setwork-efficient parallel algorithms
0
0 comments X

The pith

A parallel algorithm maintains a graph's maximal independent set under batches of b edge updates using O(b log^3 n) expected work and polylog depth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces the first parallel batch-dynamic algorithm for maintaining a maximal independent set after groups of edge insertions and deletions. For any batch size b it performs only O(b log^3 n) expected work while keeping parallel depth polylogarithmic in the number of vertices with high probability. The method preserves the same random-order lexicographically first MIS used by prior sequential dynamic algorithms yet improves their per-update cost even when b equals 1. The advance rests on a fresh analysis that builds a single batch influence set rather than treating each update's influence separately.

Core claim

The algorithm maintains a lexicographically first maximal independent set induced by a random vertex ordering. For each batch of b updates it constructs a batch influence set whose expected size is O(log^3 n) per update, then re-computes only the necessary vertices inside that set. The construction yields O(b log^3 n) expected work overall. Depth is bounded by showing that the number of sub-rounds required matches the depth of known parallel static MIS algorithms, giving polylogarithmic depth with high probability.

What carries the argument

The batch influence set, a new construction that captures all vertices whose MIS membership can change after a simultaneous batch of updates, used both to bound work and to guide the parallel update procedure.

If this is right

  • The algorithm is work-efficient relative to sequential processing for every batch size b.
  • It improves the best known sequential dynamic MIS bound even when each batch contains only a single update.
  • The same sub-round structure that gives polylog depth also lets the procedure run on standard parallel models such as the PRAM.
  • The maintained MIS remains identical to the one produced by the sequential algorithms of Chechik-Zhang and Behnezhad et al.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The batch-influence technique may transfer to other dynamic graph problems whose single-update analyses rely on influence sets, such as coloring or matching.
  • Fixing the random ordering in advance could produce a deterministic variant whose expected bounds become worst-case under suitable graph assumptions.
  • Because the analysis is described as simpler than prior single-update proofs, it may shorten the development of batch-dynamic versions for additional graph properties.

Load-bearing premise

That the newly defined batch influence set has expected size O(log^3 n) per update and that re-computing membership only inside this set suffices to restore a correct maximal independent set.

What would settle it

An experiment on a sequence of random batches where the measured expected work per update grows faster than O(log^3 n) or where the observed parallel depth exceeds any polylogarithmic function of n.

Figures

Figures reproduced from arXiv: 2604.07515 by Andrew Brady, Guy Blelloch, Jared Lo, Jeremy Fineman, Laxman Dhulipala.

Figure 1
Figure 1. Figure 1: Example of (sequential) influence set from CHK [18]. The MIS of the graph (before the [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Consider the above graph, where vertices that are marked (in the old graph, before the [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Our batch influence set propagation. The question marks indicate undecided vertices and [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Example of repeating processing of a vertex. In response to the edge insert (dotted), [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Example graph, marked vertices are shaded red. In this example, vertex 5 has later [PITH_FULL_IMAGE:figures/full_fig_p010_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Conservative algorithm for the influence analysis problem for LFMIS. The algorithm [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Our Parallel Change Propagation Algorithm. Given a set of edges [PITH_FULL_IMAGE:figures/full_fig_p017_8.png] view at source ↗
read the original abstract

We develop the first theoretically-efficient algorithm for maintaining the maximal independent set (MIS) of a graph in the parallel batch-dynamic setting. In this setting, a graph is updated with batches of edge insertions/deletions, and for each batch a parallel algorithm updates the maximal independent set to agree with the new graph. A batch-dynamic algorithm is considered efficient if it is work efficient (i.e., does no more asymptotic work than applying the updates sequentially) and has polylogarithmic depth (parallel time). In the sequential setting, the best known dynamic algorithms for MIS, by Chechik and Zhang (CZ) [FOCS19] and Behnezhad et al. (BDHSS) [FOCS19], take $O(\log^4 n)$ time per update in expectation. For a batch of $b$ updates, our algorithm has $O(b \log^3 n)$ expected work and polylogarithmic depth with high probability (whp). It therefore outperforms the best algorithm even in the sequential dynamic case ($b = 1)$. As with the sequential dynamic MIS algorithms of CZ and BDHSS, our solution maintains a lexicographically first MIS based on a random ordering of the vertices. Their analysis relied on a result of Censor-Hillel, Haramaty and Karnin [PODC16] that bounded the ``influence set" for a single update, but surprisingly, the influence of a batch is not simply the union of the influence of each update therein. We therefore develop a new approach to analyze the influence set for a batch of updates. Our construction of the batch influence set is natural and leads to an arguably simpler analysis than prior work. We then instrument this construction to bound the work of our algorithm. To argue our depth is polylogarithmic, we prove that the number of subrounds our algorithm takes is the same as depth bounds on parallel static MIS.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper presents the first work-efficient parallel batch-dynamic algorithm for maintaining a maximal independent set (MIS) in an undirected graph under batches of b edge insertions and deletions. It maintains a lexicographically-first MIS induced by a random vertex ordering and achieves O(b log³ n) expected work and polylogarithmic depth with high probability. The key technical contribution is a new construction and analysis of the batch influence set (which is not the union of per-update influence sets) whose size is bounded to instrument the work of the algorithm; depth is argued by reduction to known parallel static MIS subround bounds.

Significance. If the central bounds hold, the result is significant: it supplies the first theoretically efficient parallel algorithm for dynamic MIS in the batch setting and improves on the best sequential dynamic bounds (O(log⁴ n) per update from Chechik-Zhang and Behnezhad et al.) even for b = 1. The new batch-influence-set analysis is described as natural and arguably simpler than the single-update analysis of Censor-Hillel et al. that prior sequential work relied upon.

major comments (2)
  1. [Batch influence set construction and work analysis] The O(b log³ n) expected-work claim rests entirely on showing that the expected size of the newly constructed batch influence set is O(b log² n) (or an equivalent bound after multiplying by per-vertex work). The abstract and high-level description state that a new construction is required because batch influence is not the union of individual influences, but the manuscript must supply the full derivation and size analysis of this construction (presumably in the section containing the work analysis) for the central claim to be verifiable.
  2. [Depth analysis] The depth claim re-uses an existing parallel static-MIS subround bound. While this is less exposed than the work bound, the manuscript should explicitly state which static-MIS result is invoked and confirm that the batch-dynamic subround count is identical (or at most a constant factor larger).
minor comments (2)
  1. [Abstract] The abstract claims the algorithm 'outperforms the best algorithm even in the sequential dynamic case (b = 1)'; this comparison is correct only in the work metric and should be qualified to avoid implying a depth improvement for b = 1.
  2. [Algorithm and analysis sections] Notation for the batch influence set (size, construction steps, and how it differs from the single-update influence set) should be introduced with a clear definition or pseudocode before the size analysis begins.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their positive evaluation of the significance of our result and for the constructive comments. We address each major comment below and will revise the manuscript to improve clarity and verifiability while preserving the technical contributions.

read point-by-point responses

  1. Referee: [Batch influence set construction and work analysis] The O(b log³ n) expected-work claim rests entirely on showing that the expected size of the newly constructed batch influence set is O(b log² n) (or an equivalent bound after multiplying by per-vertex work). The abstract and high-level description state that a new construction is required because batch influence is not the union of individual influences, but the manuscript must supply the full derivation and size analysis of this construction (presumably in the section containing the work analysis) for the central claim to be verifiable.

    Authors: We agree that the full derivation of the batch influence set and its size bound is essential for verifying the O(b log³ n) work bound. The manuscript presents the batch influence set construction in Section 4 (Definition 4.1) and states the size bound in Theorem 4.2, with the proof appearing in the appendix. However, the proof sketch in the main body is concise and relies on the reader following the appendix for all steps. To address the concern, we will expand the main-text presentation of the construction and proof with additional intermediate lemmas, a concrete small example illustrating why the batch influence set differs from the union of single-update influence sets, and explicit calculation of the O(b log² n) expectation. These changes will be made in the revised version. revision: yes

  2. Referee: [Depth analysis] The depth claim re-uses an existing parallel static-MIS subround bound. While this is less exposed than the work bound, the manuscript should explicitly state which static-MIS result is invoked and confirm that the batch-dynamic subround count is identical (or at most a constant factor larger).

    Authors: We agree that the depth reduction should be stated more explicitly. The manuscript (Section 5) proves that the number of subrounds in the batch-dynamic algorithm is identical to the number of subrounds in the parallel static MIS algorithm of Blelloch, Fineman, and Shun (SPAA 2012), which is known to be O(log n) with high probability. We will revise the text to name this result directly, quote the relevant depth bound, and add a short paragraph confirming that our subround count matches theirs exactly (no constant-factor blowup). This will make the polylogarithmic depth claim self-contained. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new batch influence construction is independent

full rationale

The paper explicitly states that batch influence is not the union of per-update influences and develops a new construction and analysis for it, which is then instrumented to bound work as O(b log^3 n). This does not reduce by definition or self-citation to prior quantities; the cited single-update result (Censor-Hillel et al.) is external and the batch version is presented as a distinct, simpler approach. Depth reuses standard static MIS subround bounds without circularity. No fitted parameters, self-definitional steps, or load-bearing self-citations appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper introduces no free parameters or invented entities. It relies on standard models of parallel computation and extends prior analysis techniques without introducing new postulates.

axioms (2)
  • standard math Parallel random access machine (PRAM) model for defining work and depth
    Standard model invoked for parallel algorithm analysis and polylogarithmic depth claims.
  • domain assumption Random vertex ordering defines the lexicographically first MIS
    Inherited from the sequential dynamic MIS algorithms of Chechik-Zhang and Behnezhad et al.

pith-pipeline@v0.9.0 · 5662 in / 1481 out tokens · 43308 ms · 2026-05-10T16:53:53.733787+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

53 extracted references · 53 canonical work pages

  1. [1]

    Acar, Daniel Anderson, Guy E

    Umut A. Acar, Daniel Anderson, Guy E. Blelloch, and Laxman Dhulipala. Parallel batch- dynamic graph connectivity. InACM Symposium on Parallelism in Algorithms and Architec- tures (SPAA). ACM, 2019

    work page 2019

  2. [2]

    Acar, Daniel Anderson, Guy E

    Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. Parallel batch-dynamic trees via change propagation. InEuropean Symposium on Algorithms (ESA), 2020. 29

    work page 2020

  3. [3]

    Acar, Guy E

    Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, and Shan Leung Maverick Woo. Dynamizing static algorithms, with applications to dynamic trees and history indepen- dence. InProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’04, page 531–540, USA, 2004. Society for Industrial and Applied Mathematics

    work page 2004

  4. [4]

    Aggregating inconsistent information: Ranking and clustering.J

    Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering.J. ACM, 55(5), November 2008

    work page 2008

  5. [5]

    A fast and simple randomized parallel algorithm for the maximal independent set problem.Journal of Algorithms, 7(4):567–583, 1986

    Noga Alon, L´ aszl´ o Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem.Journal of Algorithms, 7(4):567–583, 1986

    work page 1986

  6. [6]

    Blelloch

    Daniel Anderson and Guy E. Blelloch. Parallel minimum cuts inO(mlog 2 n) work and low depth.ACM Transactions on Parallel Computing (TOPC), 10(4):18:1–18:28, 2023

    work page 2023

  7. [7]

    Blelloch

    Daniel Anderson and Guy E. Blelloch. Deterministic and low-span work-efficient parallel batch- dynamic trees. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 247–258. ACM, 2024

    work page 2024

  8. [8]

    Blelloch, and Kanat Tangwongsan

    Daniel Anderson, Guy E. Blelloch, and Kanat Tangwongsan. Work-efficient batch-incremental minimum spanning trees with applications to the sliding-window model. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020

    work page 2020

  9. [9]

    Fully dynamic maximal independent set with sublinear update time

    Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear update time. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 815–826, New York, NY, USA, 2018. Association for Computing Machinery

    work page 2018

  10. [10]

    Fully dynamic maximal independent set with sublinear innupdate time

    Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear innupdate time. InACM-SIAM Symposium on Discrete Algorithms (SODA), 2019

    work page 2019

  11. [11]

    Optimal fully dynamick-center clustering for adaptive and oblivious adversaries

    MohammadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Ra- jesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamick-center clustering for adaptive and oblivious adversaries. InACM-SIAM Symposium on Discrete Algorithms (SODA), 2023

    work page 2023

  12. [12]

    Fully dynamic maximal independent set with polylogarithmic update time

    Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. InIEEE Symposium on Foundations of Computer Science (FOCS), pages 382–405, 2019

    work page 2019

  13. [13]

    Separations between oblivious and adaptive adversaries for natural dynamic graph problems

    Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, and Thatchaphol Saranurak. Separations between oblivious and adaptive adversaries for natural dynamic graph problems. InACM-SIAM Symposium on Discrete Algorithms (SODA), 2026

    work page 2026

  14. [14]

    Faster parallel batch-dynamic algorithms for low out-degree orientation.CoRR, abs/2602.17811v1

    Guy Blelloch, Andrew Brady, Laxman Dhulipala, Jeremy Fineman, Kishen Gowda, and Chase Hutton. Faster parallel batch-dynamic algorithms for low out-degree orientation.CoRR, abs/2602.17811v1

    work page arXiv

  15. [15]

    Blelloch and Andrew C

    Guy E. Blelloch and Andrew C. Brady. Parallel batch-dynamic maximal matching with con- stant work per update. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025. 30

    work page 2025

  16. [16]

    Blelloch, Jeremy T

    Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. Optimal parallel algorithms in the binary-forking model. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020

    work page 2020

  17. [17]

    Blelloch, Jeremy T Fineman, and Julian Shun

    Guy E. Blelloch, Jeremy T Fineman, and Julian Shun. Greedy sequential maximal independent set and matching are parallel on average. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2012

    work page 2012

  18. [18]

    Optimal dynamic distributed MIS

    Keren Censor-Hillel, Elad Haramaty, and Zohar Karnin. Optimal dynamic distributed MIS. InProceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC ’16, page 217–226, New York, NY, USA, 2016. Association for Computing Machinery

    work page 2016

  19. [19]

    Fully dynamic maximal independent set in expected poly-log update time

    Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 370–381, 2019

    work page 2019

  20. [20]

    Stephen A. Cook. A taxonomy of problems with fast parallel algorithms.Inf. Control, 64, March 1985

    work page 1985

  21. [21]

    History-independent maximal matchings can be sur- prisingly efficient, and lead to better worst-case guarantees

    Rathish Das and William Kuszmaul. History-independent maximal matchings can be sur- prisingly efficient, and lead to better worst-case guarantees. InACM-SIAM Symposium on Discrete Algorithms (SODA), 2026

    work page 2026

  22. [22]

    Leader election in shared spectrum radio networks

    Sebastian Daum, Seth Gilbert, Fabian Kuhn, and Calvin Newport. Leader election in shared spectrum radio networks. InProceedings of the 2012 ACM Symposium on Principles of Dis- tributed Computing, PODC ’12, page 215–224, New York, NY, USA, 2012. Association for Computing Machinery

    work page 2012

  23. [23]

    Towards scalable and practical batch-dynamic connectivity.Proc

    Quinten De Man, Laxman Dhulipala, Adam Karczmarz, Jakub Lacki, Julian Shun, and Zhongqi Wang. Towards scalable and practical batch-dynamic connectivity.Proc. VLDB Endow., 18(3):889–901, November 2024

    work page 2024

  24. [24]

    Ufo trees: Practical and provably-efficient parallel batch-dynamic trees

    Quinten De Man, Atharva Sharma, Kishen N Gowda, and Laxman Dhulipala. Ufo trees: Practical and provably-efficient parallel batch-dynamic trees. InProceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP ’26, page 109–122, New York, NY, USA, 2026. Association for Computing Machinery

    work page 2026

  25. [25]

    Parallel batch-dynamic k-clique counting

    Laxman Dhulipala, Quanquan C Liu, Julian Shun, and Shangdi Yu. Parallel batch-dynamic k-clique counting. InACM-SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), 2021

    work page 2021

  26. [26]

    Improved Algorithms for Fully Dynamic Maximal Independent Set.CoRR, abs/1804.08908, 2018

    Yuhao Du and Hengjie Zhang. Improved Algorithms for Fully Dynamic Maximal Independent Set.CoRR, abs/1804.08908, 2018

    work page arXiv 2018

  27. [27]

    Tight analysis of parallel randomized greedy MIS.ACM Transactions on Algorithms (TALG), 16(1), December 2019

    Manuela Fischer and Andreas Noever. Tight analysis of parallel randomized greedy MIS.ACM Transactions on Algorithms (TALG), 16(1), December 2019

    work page 2019

  28. [28]

    Near-optimal deterministic network decomposition and ruling set, and improved MIS

    Mohsen Ghaffari and Christoph Grunau. Near-optimal deterministic network decomposition and ruling set, and improved MIS. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 2148–2179, 2024. 31

    work page 2024

  29. [29]

    Nearly work-efficient parallel DFS in undirected graphs

    Mohsen Ghaffari, Christoph Grunau, and Jiahao Qu. Nearly work-efficient parallel DFS in undirected graphs. InProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’23, page 273–283, New York, NY, USA, 2023. Association for Com- puting Machinery

    work page 2023

  30. [30]

    Dynamic graph coloring: Sequential, parallel, and dis- tributed.CoRR, abs/2512.09218, 2025

    Mohsen Ghaffari and Jaehyun Koo. Dynamic graph coloring: Sequential, parallel, and dis- tributed.CoRR, abs/2512.09218, 2025

    work page arXiv 2025

  31. [31]

    Parallel batch-dynamic algorithms for spanners, and extensions

    Mohsen Ghaffari and Jaehyun Koo. Parallel batch-dynamic algorithms for spanners, and extensions. InProceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’25, page 299–313, New York, NY, USA, 2025. Association for Computing Machinery

    work page 2025

  32. [32]

    Parallel batch-dynamic coreness decomposition with worst- case guarantees

    Mohsen Ghaffari and Jaehyun Koo. Parallel batch-dynamic coreness decomposition with worst- case guarantees. InProceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’25, page 225–239, New York, NY, USA, 2025. Association for Computing Machinery

    work page 2025

  33. [33]

    Parallel dynamic maximal matching

    Mohsen Ghaffari and Anton Trygub. Parallel dynamic maximal matching. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2024

    work page 2024

  34. [34]

    A top-down parallel semisort

    Yan Gu, Julian Shun, Yihan Sun, and Guy E Blelloch. A top-down parallel semisort. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2015

    work page 2015

  35. [35]

    Manoj Gupta and Shahbaz Khan.Simple dynamic algorithms for Maximal Independent Set, Maximum Flow and Maximum Matching, pages 86–91

    work page

  36. [36]

    Parallel batch-dynamic vertex coloring inO(log ∆) amortized update time.CoRR, abs/2512.08742, 2025

    Chase Hutton and Adam Melrod. Parallel batch-dynamic vertex coloring inO(log ∆) amortized update time.CoRR, abs/2512.08742, 2025

    work page arXiv 2025

  37. [37]

    Brady, Daniel Anderson, and Guy E

    Humza Ikram, Andrew C. Brady, Daniel Anderson, and Guy E. Blelloch. Parallel batch queries on dynamic trees: Algorithms and experiments. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2025

    work page 2025

  38. [38]

    Addison Wesley Longman Publishing Co., Inc., USA, 1992

    Joseph J´ aJ´ a.An Introduction to Parallel Algorithms. Addison Wesley Longman Publishing Co., Inc., USA, 1992

    work page 1992

  39. [39]

    Karp and Avi Wigderson

    Richard M. Karp and Avi Wigderson. A fast parallel algorithm for the maximal independent set problem. InProceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC ’84, page 266–272, New York, NY, USA, 1984. Association for Computing Machinery

    work page 1984

  40. [40]

    Fully dynamic maximall independent set in polylogarithmic update time

    Bob Krekelberg. Fully dynamic maximall independent set in polylogarithmic update time. Master’s thesis, Eindhoven University of Technology, 2023

    work page 2023

  41. [41]

    Distributive graph algorithms global solutions from local data

    Nathan Linial. Distributive graph algorithms global solutions from local data. In28th Annual Symposium on Foundations of Computer Science, pages 331–335, 1987

    work page 1987

  42. [42]

    Parallel batch- dynamic algorithms for k-core decomposition and related graph problems

    Quanquan C Liu, Jessica Shi, Shangdi Yu, Laxman Dhulipala, and Julian Shun. Parallel batch- dynamic algorithms for k-core decomposition and related graph problems. InACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 191–204, 2022. 32

    work page 2022

  43. [43]

    A simple parallel algorithm for the maximal independent set problem.SIAM J

    Michael Luby. A simple parallel algorithm for the maximal independent set problem.SIAM J. on Computing, 15, 1986

    work page 1986

  44. [44]

    Nguyen and Krzysztof Onak

    Huy N. Nguyen and Krzysztof Onak. Constant-time approximation algorithms via local im- provements. InProceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’08, page 327–336, USA, 2008. IEEE Computer Society

    work page 2008

  45. [45]

    Fast maximal independent sets on dynamic graphs

    Prajjwal Nijhara, Aditya Trivedi, and Dip Sankar Banerjee. Fast maximal independent sets on dynamic graphs. In2025 33rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), pages 78–85, 2025

    work page 2025

  46. [46]

    Fully dynamic MIS in uniformly sparse graphs.ACM Transactions on Algorithms (TALG), 16(2):1–19, 2020

    Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. Fully dynamic MIS in uniformly sparse graphs.ACM Transactions on Algorithms (TALG), 16(2):1–19, 2020

    work page 2020

  47. [47]

    Cambridge University Press, 2014

    Ryan O’Donnell.Analysis of Boolean Functions. Cambridge University Press, 2014

    work page 2014

  48. [48]

    Work-efficient parallel union-find with applications to incremental graph connectivity

    Natcha Simsiri, Kanat Tangwongsan, Srikanta Tirthapura, and Kun-Lung Wu. Work-efficient parallel union-find with applications to incremental graph connectivity. InEuropean Confer- ence on Parallel Processing (Euro-Par), 2016

    work page 2016

  49. [49]

    Fast mis on incremental graphs

    Aditya Trivedi, Prajjwal Nijhara, and Dip Sankar Banerjee. Fast mis on incremental graphs. In2024 IEEE 31st International Conference on High Performance Computing, Data and An- alytics Workshop (HiPCW), pages 139–140, 2024

    work page 2024

  50. [50]

    Batch-parallel Euler tour trees.Algo- rithm Engineering and Experiments (ALENEX), 2019

    Thomas Tseng, Laxman Dhulipala, and Guy Blelloch. Batch-parallel Euler tour trees.Algo- rithm Engineering and Experiments (ALENEX), 2019

    work page 2019

  51. [51]

    Parallel batch-dynamic minimum spanning forest and the efficiency of dynamic agglomerative graph clustering

    Tom Tseng, Laxman Dhulipala, and Julian Shun. Parallel batch-dynamic minimum spanning forest and the efficiency of dynamic agglomerative graph clustering. InProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’22, page 233–245, New York, NY, USA, 2022. Association for Computing Machinery

    work page 2022

  52. [52]

    Parallel minimum cost flow in near-linear work and square root depth for dense instances

    Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang, and Tjin de Vos. Parallel minimum cost flow in near-linear work and square root depth for dense instances. InProceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’25, page 1–16, New York, NY, USA, 2025. Association for Computing Machinery. 33 8 Appendix 8.1 Batch ...

    work page 2025

  53. [53]

    This encapsualtes maximality and the lexicographic first condition

    for allu̸∈M, there existsv∈N(u)∩Mwithπ(v)< π(u)(all unmarked vertices have an earlier marked neighbor). This encapsualtes maximality and the lexicographic first condition. Note thatN(u)means the neighbors ofu. 2.Mis independent (for allu, v∈M,(u, v)̸∈E) Proof.For the forward direction of the implication, suppose thatMis the LFMIS. Then all un- marked vert...

    work page