betaFeedback

WorksComputer Science

Faster Dynamic Maximal Independent Set against Adaptive Adversaries

Abstract

We study the fully dynamic maximal independent set (MIS) problem: maintaining an MIS in an undirected graph on nn vertices with at most mm edges under edge insertions and deletions. Against an oblivious adversary, which fixes the edge update sequence in advance, the randomized algorithms of Behnezhad et al. (2019) and Chechik and Zhang (2019) achieve polylogarithmic update time. Against an adaptive adversary, which may choose each update after observing the previously reported MISs, the best previously known update bound was O(m2/3)O(m^{2/3}), given by the deterministic algorithm of Gupta and Khan (2018, 2021). Assuming the combinatorial Boolean matrix multiplication hypothesis, Bernstein et al. (2026) proved that any combinatorial algorithm against an adaptive adversary requires at least m1/2−o(1)m^{1/2-o(1)} update time even under edge insertions alone, leaving a polynomial gap between upper and lower bounds. We present a randomized fully dynamic MIS algorithm with O~(m5/8)=O~(m2/3−1/24)\widetilde O(m^{5/8})=\widetilde O(m^{2/3-1/24}) update time against adaptive adversaries. This gives the first polynomial improvement over the m2/3m^{2/3} bound for adaptive fully dynamic MIS.

Introduction

Dynamic graph algorithms maintain information about a graph as its edges are inserted and deleted, aiming to process each update much faster than recomputing a solution from scratch. Fundamental problems studied in this setting include connectivity and related connectivity notions [32, 38 HNRS25], minimum spanning forest [32 NSW17, 36], reachability and transitive closure [44, 33, 46], shortest paths [22, 20, 46], matching [12, 48, 40, 10], and network flow [30, 47], among many others.

We study the fully dynamic maximal independent set (MIS) problem. We consider an undirected graph G=(V,E)G = (V, E) with nn vertices that undergoes a sequence of edge insertions and deletions. Throughout, mm denotes an upper bound on the number of edges ∣E∣|E| present at any time. Updates are revealed online, and the algorithm receives no predictions of future updates. A set M⊆V\mathcal{M} \subseteq V is an independent set if no two vertices in M\mathcal{M} are adjacent. It is a maximal independent set (MIS) if no proper superset of M\mathcal{M} is independent; equivalently, every vertex in V∖MV \setminus\mathcal{M} has a neighbor in M\mathcal{M}. A vertex outside M\mathcal{M} is dominated if it has a neighbor in M\mathcal{M}, and undominated otherwise. MIS is a fundamental symmetry-breaking problem in parallel and distributed computation, with applications to coloring, matching, and network coordination. Although a static MIS can be computed by a single greedy scan, the fully dynamic MIS problem requires maintaining such a set after every edge update. This is substantially more challenging: if an inserted edge joins two vertices of the current MIS, one of these vertices must leave, potentially leaving many of its neighbors undominated and triggering a cascade of further repairs.

An elementary deterministic algorithm maintains an MIS in O(max⁡v∈V{deg⁡G(v)})=O(n)O(\max_{v \in V}\{\deg_G(v)\}) = O(n) amortized update time. Assadi, Onak, Schieber, and Solomon gave the first nontrivial fully dynamic MIS algorithm with update time sublinear in the number of edges, obtaining a deterministic O(m3/4)O(m^{3/4}) amortized bound [1]. Gupta and Khan subsequently improved this to O(m2/3)O(m^{2/3}) with a particularly simple deterministic algorithm, first announced in a 2018 preprint [27] and published in 2021 [28]; Du and Zhang independently obtained O(m2/3log⁡m)O(m^{2/3}\sqrt{\log m}) update time [23]. The resulting O(min⁡{n,m2/3})O(\min\{n, m^{2/3}\}) amortized update time remains the best known deterministic bound.

For randomized algorithms, the adversarial model is important. An oblivious adversary fixes the entire update sequence in advance without revealing it to the algorithm. In this model, Assadi, Onak, Schieber, and Solomon achieved O~(n)\widetilde{O}(\sqrt{n}) expected amortized update time [2], and two independent works subsequently obtained polylogarithmic update time [9, 19]. These guarantees rely on the update sequence being fixed before the execution begins and, in particular, being independent of the algorithm’s randomness.

An adaptive adversary, in contrast, may choose each update after observing the solutions reported by the algorithm so far. Since a deterministic algorithm uses no random choices, its guarantee is unaffected by such adaptivity. In particular, the deterministic O(m2/3)O(m^{2/3}) amortized update bound of Gupta and Khan [28] is automatically robust against adaptive adversaries. For algorithms that explicitly maintain the MIS, an adaptive adversary can force Ω(n)\Omega(n) membership changes in a single edge update [1 Appendix A]. Consequently, o(n)o(n) worst-case update time is impossible in general, necessitating amortization for sublinear update bounds.

Beimel et al. [13] explain why committing to random choices, as in fast oblivious MIS algorithms, does not directly extend to this setting: an adaptive adversary can target the revealed choices to force costly recomputation. Recent work establishes a conditional lower bound for dynamic MIS against adaptive adversaries. Assuming the combinatorial Boolean matrix multiplication hypothesis, Bernstein, Bhattacharya, Fischer, Kiss, and Saranurak proved an n1−o(1)n^{1-o(1)} amortized update lower bound for combinatorial algorithms against adaptive adversaries, even under edge insertions alone [4]. By adding isolated vertices to the graphs in the dense hard instances, this lower bound extends to m1/2−o(1)m^{1/2-o(1)} amortized update time for every graph sparsity from m=Θ(n)m = \Theta(n) to m=Θ(n2)m = \Theta(n^2). This leaves a gap between the m1/2−o(1)m^{1/2-o(1)} lower bound and the O(m2/3)O(m^{2/3}) upper bound. Gupta, Khan, and Surendra recently obtained an alternative deterministic O(m2/3)O(m^{2/3}) fully dynamic algorithm and highlighted the goal of improving this bound to match their O(m)O(\sqrt{m}) incremental bound [29]. These results motivate the following question.

Open Problem Can a maximal independent set be maintained in a fully dynamic graph against an adaptive adversary in O(m2/3−ϵ)O(m^{2/3-\epsilon}) amortized update time for some constant ϵ>0\epsilon> 0?

Our Result

We answer this question affirmatively by giving the first polynomial improvement over the m2/3m^{2/3} update-time bound for fully dynamic MIS against adaptive adversaries.

Theorem 1.1. Let G=(V,E)G = (V, E) be an initially empty undirected graph on nn vertices that undergoes a sequence of edge insertions and deletions, with at most mm edges at any time. There is a randomized algorithm that maintains a maximal independent set of GG against adaptive adversaries with amortized update time O~(m5/8)=O~(m2/3−1/24)\widetilde{O}(m^{5/8}) = \widetilde{O}(m^{2/3-1/24}).

The basic O(m2/3)O(m^{2/3}) algorithm. Our starting point is the simple deterministic algorithm of Gupta and Khan [28]. Partition vertices into low and high degree classes at a threshold DD. Maintain an MIS of the low degree subgraph by tracking each vertex’s number of low degree MIS neighbors and greedily repairing maximality after each update, at an amortized cost of O(D)O(D). Then extend it to an MIS of the whole graph by rebuilding an MIS on the high degree vertices with no low degree MIS neighbor. There are O(m/D)O(m/D) high degree vertices, so rebuilding costs O((m/D)2)O((m/D)^2). Balancing the two costs with D=m2/3D = m^{2/3} gives the O(m2/3)O(m^{2/3}) bound.

Our approach. The main bottleneck is rebuilding the MIS on the high degree subgraph: lowering DD reduces the cost of low degree repairs but increases the rebuilding cost. Our approach avoids rebuilding the high layer after every update by maintaining a candidate set of low degree vertices outside the MIS that are dominated solely by high degree MIS vertices. We allow these candidates to remain outside the MIS, and include a candidate in the MIS only when it has few high degree MIS neighbors. This limits the conflicts caused when it joins the MIS and allows us to repair the high layer locally. This new candidate-set design introduces two main technical challenges.

Structural challenges. Maintaining the candidate set in less than m2/3m^{2/3} amortized time creates further bottlenecks: a high degree MIS change may affect many candidates, and candidates may accumulate so quickly that periodic rebuilding becomes too frequent to achieve the desired amortized update time. To resolve these bottlenecks, we develop additional data structures for maintaining the candidate set. These structures may be of independent interest; simplifying or extending them could yield further improvements for dynamic MIS.

Adaptivity challenges. Our design maintains randomly sampled high degree MIS neighbors to verify that candidates are dominated. The reported MIS can therefore leak information about these private samples to the adversary, whose future updates may exploit that information. To analyze this dependence, we develop a new tool for adaptivity analysis: probabilistic games. These games characterize the information revealed by the data structure and establish the sampling guarantees needed under adaptive updates. This adaptivity argument may also be of independent interest, and the games may provide tools for analyzing other randomized data structures against adaptive adversaries.

Further Related Work

Other Settings of Dynamic MIS

Partially dynamic MIS. In the decremental setting, where edges are only deleted, a simple monotone algorithm is optimal: include a vertex in the MIS whenever it ceases to have a neighbor in the MIS. No vertex ever needs to leave the MIS, and each vertex joins the MIS at most once, giving optimal total time linear in the size of the initial graph [28]. In the incremental setting, where edges are only inserted, Gupta, Khan, and Surendra gave a deterministic algorithm with O(m)O(\sqrt{m}) amortized update time [29]. Moreover, the conditional m1/2−o(1)m^{1/2-o(1)} lower bound against adaptive adversaries also holds for incremental MIS [4].

Bounded arboricity. For graphs whose arboricity—the minimum number of forests into which the edge set can be partitioned—remains at most α\alpha, Onak, Schieber, Solomon, and Wein gave a deterministic fully dynamic MIS algorithm with O(α2log⁡2n)O(\alpha^2 \log^2 n) amortized update time [43]. In particular, this gives polylogarithmic update time for graph families of bounded arboricity.

Dynamic MIS with predictions. Khan and Kumar [39] study dynamic MIS when a predicted update sequence is available for offline preprocessing. For a sequence of uu fully dynamic updates, their algorithm uses O(un)O(un) preprocessing time and space and achieves O(ηe+ηv∗)O(\eta_e+\eta_v^*) worst-case time per update after the first prediction error. In their basic error model, ηe\eta_e counts the distinct edges updated since the first mismatch. The parameter ηv∗\eta_v^* measures the sum of degrees of vertices whose MIS membership differs from that at the end of the correctly predicted prefix, maximized over subsequent updates processed so far; degrees are maximized over the relevant graphs.

Adaptive Algorithms for Symmetry-Breaking Problems

MIS, maximal matching, vertex coloring, and edge coloring are fundamental symmetry-breaking problems. Recent work has established improved update-time bounds for their dynamic variants against adaptive adversaries.

Maximal matching. Against oblivious adversaries, Baswana, Gupta, and Sen obtained O(log⁡n)O(\log n) expected amortized update time [12], which Solomon improved to O(1)O(1) expected amortized update time [45]. In the parallel setting, Ghaffari and Trygub gave a randomized dynamic maximal matching algorithm that processes batches of edge insertions and deletions with polylogarithmic amortized work per update and polylogarithmic depth per batch, with high probability over polynomial-length update sequences against oblivious adversaries [31]. Against adaptive adversaries, Neiman and Solomon gave a deterministic O(m)O(\sqrt{m}) worst-case update bound [41]. This bound is o(n)o(n) when m=o(n2)m=o(n^2), but remains O(n)O(n) when m=Θ(n2)m=\Theta(n^2). In 2025, Bernstein, Bhattacharya, Kiss, and Saranurak gave a deterministic algorithm with O~(n8/9)\widetilde{O}(n^{8/9}) amortized update time and a randomized algorithm with O~(n3/4)\widetilde{O}(n^{3/4}) amortized update time against adaptive adversaries [5]. In 2026, Chuzhoy, Khanna, and Song improved the deterministic bound to n1/2+o(1)n^{1/2+o(1)} amortized update time [17].

Vertex coloring. For (Δ+1)(\Delta+ 1)-coloring, the goal is to maintain a proper vertex coloring using one more color than a known upper bound Δ\Delta on the maximum degree over the update sequence. Bhattacharya, Grandoni, Kulkarni, Liu, and Solomon [11] and, independently, Henzinger and Peng [37] obtained randomized algorithms with O(1)O(1) expected amortized update time against oblivious adversaries. In 2025, Behnezhad, Rajaraman, and Wasim obtained an algorithm against adaptive adversaries with O~(n8/9)\widetilde{O}(n^{8/9}) amortized update time [14], which Flin and Halldórsson improved to O~(n2/3)\widetilde{O}(n^{2/3}) amortized update time [24]. Very recently, two independent concurrent works achieved O~(n1/2)\widetilde{O}(n^{1/2}) update time against adaptive adversaries [26, 3].

For arboricity-dependent coloring, Ghaffari and Grunau gave a randomized dynamic algorithm that maintains an implicit O(α)O(\alpha)-coloring, where α\alpha is the graph’s arboricity, with polylogarithmic worst-case update and query times against oblivious adversaries [25].

Edge coloring. Bhattacharya, Chakrabarty, Henzinger, and Nanongkai [6] gave a deterministic algorithm maintaining a (2Δ−1)(2\Delta- 1)-edge coloring in O(log⁡Δ)O(\log\Delta) worst-case update time. Duan, He, and Zhang [21] reduced the number of colors to (1+ϵ)Δ(1 + \epsilon)\Delta with poly⁡(log⁡n,ϵ−1)\operatorname{poly}(\log n,\epsilon^{-1}) amortized update time when Δ=Ω(ϵ−2log⁡2n)\Delta= \Omega(\epsilon^{-2}\log^2 n). Christiansen [15] removed this degree restriction and obtained poly⁡(log⁡n,ϵ−1)\operatorname{poly}(\log n,\epsilon^{-1}) worst-case update time against adaptive adversaries. For fixed ϵ>0\epsilon> 0 and Δ\Delta above an ϵ\epsilon-dependent polylogarithmic threshold, Bhattacharya, Costa, Panski, and Solomon [BCPS24b] achieved O(1)O(1) expected update time against oblivious adversaries. On the deterministic side, Christiansen [16] obtained (1+ϵ)Δ(1 + \epsilon)\Delta-edge coloring with no(1)n^{o(1)} amortized update time for fixed ϵ>0\epsilon> 0. For graphs of arboricity α\alpha, independent works of Bhattacharya, Costa, Panski, and Solomon [BCPS24a] and Christiansen, Rotenberg, and Vlieghe [18] give deterministic (Δ+O(α))(\Delta+ O(\alpha))-edge coloring with polylogarithmic amortized update time. More recently, Haeupler et al. [HMR+26] developed an approach based on the dynamic Lovász local lemma, obtaining (1+ϵ)Δ(1 + \epsilon)\Delta-edge coloring with polylogarithmic amortized update time against adaptive adversaries.

The distinction for MIS. MIS differs from these problems in that a polynomial conditional lower bound is known against adaptive adversaries. Under the combinatorial Boolean matrix multiplication hypothesis, Bernstein, Bhattacharya, Fischer, Kiss, and Saranurak proved that every combinatorial dynamic MIS algorithm requires n1−o(1)n^{1-o(1)} amortized update time, even for edge insertions only [4]. This gives a conditional separation from the polylogarithmic bounds against oblivious adversaries. For combinatorial dynamic MIS algorithms, the lower bound rules out matching the oblivious-adversary bounds in general, while leaving room to improve the polynomial dependence on mm. Our result pursues this goal within the broader effort to develop faster dynamic symmetry-breaking algorithms against adaptive adversaries.

Technical Overview

We consider an initially empty simple undirected graph G=(V,E)G = (V,E) on a fixed set of nn vertices, undergoing edge insertions and deletions. Let mm be a fixed upper bound on the number of edges throughout the update sequence. Initially, the maintained MIS is M=V\mathcal{M} = V. Write N(v)N(v) for the current neighbor set of vv, deg⁡(v)=∣N(v)∣\deg(v) = |N(v)|, N(S)=⋃v∈SN(v)N(S) = \bigcup_{v \in S} N(v), and G[S]G[S] for the subgraph induced by S⊆VS \subseteq V. An independent set M\mathcal{M} is maximal precisely when every vertex outside M\mathcal{M} has a neighbor in M\mathcal{M}; we call such a vertex dominated and such an MIS neighbor a domination witness. The edge joining the vertex to its witness is a domination edge.

The adversary is adaptive: it may choose each update using the entire sequence of previously reported MISs. It does not observe the algorithm’s private random bits, auxiliary data structures, memory accesses, or internal running times. An event holds with high probability if its failure probability is at most n−cn^{-c} for an arbitrarily large fixed constant c>0c > 0, with constants in the algorithm chosen accordingly. Our probabilistic guarantees apply over any fixed polynomial-length update sequence, including one chosen adaptively.

MIS Candidates and Domination Witnesses

The O(m2/3)O(m^{2/3}) amortized algorithm. We begin with Gupta and Khan’s deterministic algorithm [28], which provides the starting point for our improvement. Fix a degree threshold DD. Partition the vertices into VloV_{\mathrm{lo}}, with degree at most DD, and VhiV_{\mathrm{hi}}, with degree greater than DD. Maintain an MIS Mlo\mathcal{M}_{\mathrm{lo}} of G[Vlo]G[V_{\mathrm{lo}}], giving low vertices priority over high vertices, and extend it by an MIS Mhi\mathcal{M}_{\mathrm{hi}} of G[Vhi∖N(Mlo)]G[V_{\mathrm{hi}} \setminus N(\mathcal{M}_{\mathrm{lo}})]. We call Mlo\mathcal{M}_{\mathrm{lo}} and Mhi\mathcal{M}_{\mathrm{hi}} the low and high MIS layers: each consists of the vertices of the maintained MIS in its degree class.

The low layer can be repaired in O(D)O(D) amortized time per update. Maintain each vertex’s number of neighbors in Mlo\mathcal{M}_{\mathrm{lo}}, and greedily include a low vertex in Mlo\mathcal{M}_{\mathrm{lo}} when its count becomes zero. For each such vertex, scan at most DD edges to update these counts. Although many vertices can join Mlo\mathcal{M}_{\mathrm{lo}} during one update, the potential decreases enough to pay for all their scans: assign potential Θ(D)\Theta(D) to each low vertex outside Mlo\mathcal{M}_{\mathrm{lo}}, so that including it in Mlo\mathcal{M}_{\mathrm{lo}} releases enough potential to cover its scan. An edge insertion forces at most one low-MIS removal, and a deletion forces none. The potential increase from these removals is therefore only O(D)O(D) per update, giving the claimed amortized bound.

As illustrated in Figure 1, including even one vertex in Mlo\mathcal{M}_{\mathrm{lo}} can invalidate the current high-layer MIS. After restoring maximality in the low layer, rebuild Mhi\mathcal{M}_{\mathrm{hi}} from scratch. The counters identify the high vertices with no neighbor in Mlo\mathcal{M}_{\mathrm{lo}}, and ∣Vhi∣≤2m/D|V_{\mathrm{hi}}| \le2m/D, so this costs O((m/D)2)O((m/D)^2) time.

The bottleneck in the amortized algorithm, showing the low- and high-layer MIS before and after a low-degree vertex joins the low layer

Figure 1. The bottleneck in the O(m2/3)O(m^{2/3}) amortized algorithm. Before a low degree vertex vv joins Mlo\mathcal{M}_{\mathrm{lo}}, its high-MIS neighbors (crosses) leave Mhi\mathcal{M}_{\mathrm{hi}}. The algorithm rebuilds Mhi\mathcal{M}_{\mathrm{hi}} on Vhi∖N(Mlo)V_{\mathrm{hi}} \setminus N(\mathcal{M}_{\mathrm{lo}}), costing O(∣Vhi∣2)=O((m/D)2)O(|V_{\mathrm{hi}}|^2) = O((m/D)^2) per update.

Consequently, the amortized update time is

O(D+m2D2),O\left(D+\frac{m^2}{D^2}\right),

which is minimized at D=Θ(m2/3)D=\Theta(m^{2/3}).

References

  1. [1][AOSS18] Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear update time. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pages 815–826. ACM, 2018.arxiv.org/abs/1802.09709
  2. [2][AOSS19] Sepehr Assadi, Krzysztof Onak, Baruch Schieber, and Shay Solomon. Fully dynamic maximal independent set with sublinear in n update time. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 1919–1936. SIAM, 2019.arxiv.org/abs/1806.10051
  3. [3]Sepehr Assadi and Helia Yazdanyar. Dynamic (Δ + 1) vertex coloring with adaptive adversaries: Entropy compression to the rescue. In Proceedings of the 38th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2027). SIAM, 2027. To appear. Full version: arXiv:2610.38787.arxiv.org/abs/2610.38787
  4. [4]Aaron Bernstein, Sayan Bhattacharya, Nick Fischer, Peter Kiss, and Thatchaphol Saranurak. Separations between oblivious and adaptive adversaries for natural dynamic graph problems. In Proceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pages 5669–5687. SIAM, 2026.arxiv.org/abs/2510.20341
  5. [5]Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, and Thatchaphol Saranurak. Deterministic dynamic maximal matching in sublinear update time. In Proceedings of the 57th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2025), pages 132–143. ACM, 2025.arxiv.org/abs/2504.20780
  6. [6]Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger, and Danupon Nanongkai. Dynamic algorithms for graph coloring. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pages 1–20. SIAM, 2018.arxiv.org/abs/1711.04355
  7. [9]Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019), pages 382–405. IEEE Computer Society, 2019.arxiv.org/abs/1909.03478
  8. [10]Soheil Behnezhad and Alma Ghafari. Fully dynamic matching and ordered Ruzsa-Szemerédi graphs. In Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024), pages 314–327. IEEE Computer Society, 2024.arxiv.org/abs/2404.06069
  9. [11]Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni, Quanquan C. Liu, and Shay Solomon. Fully dynamic (Δ+1)-coloring in O(1) update time. ACM Transactions on Algorithms, 18(2):10:1–10:25, 2022.
  10. [12]Surender Baswana, Manoj Gupta, and Sandeep Sen. Fully dynamic maximal matching in O(log n) update time. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011), pages 383–392. IEEE Computer Society, 2011.
  11. [13]Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemm­er. Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), pages 1671–1684. ACM, 2022.arxiv.org/abs/2111.03980
  12. [14]Soheil Behnezhad, Rajmohan Rajaraman, and Omer Wasim. Fully dynamic (Δ + 1)-coloring against adaptive adversaries. In Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025), pages 4983–5026. SIAM, 2025.DOI
  13. [15]Aleksander B. G. Christiansen. The power of multi-step Vizing chains. In Proceedings of the 55th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2023), pages 1013–1026. ACM, 2023.arxiv.org/abs/2210.07363
  14. [16]Aleksander B. G. Christiansen. Deterministic dynamic edge colouring. In Proceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), pages 1047–1096. SIAM, 2026.arxiv.org/abs/2402.13139
  15. [17]Julia Chuzhoy, Sanjeev Khanna, and Junkai Song. A faster deterministic algorithm for fully dynamic maximal matching. In Proceedings of the 58th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2026), pages 1604–1615. ACM, 2026.
  16. [18]Aleksander B. G. Christiansen, Eva Rotenberg, and Juliette Vlieghe. Sparsity-parameterised dynamic edge colouring. In Proceedings of the 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024), volume 294 of LIPIcs, pages 20:1–20:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.arxiv.org/abs/2311.10616
  17. [19]Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019), pages 370–381. IEEE Computer Society, 2019.arxiv.org/abs/1909.03445
  18. [20]Julia Chuzhoy and Ruimin Zhang. A new deterministic algorithm for fully dynamic all-pairs shortest paths. In Proceedings of the 55th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2023), pages 1159–1172. ACM, 2023.arxiv.org/abs/2304.09321
  19. [21]Ran Duan, Haoqing He, and Tianyi Zhang. Dynamic edge coloring with improved approximation. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), pages 1937–1945. SIAM, 2019.
  20. [22]Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. Journal of the ACM, 51(6):968–992, 2004.
  21. [23]Yuhao Du and Hengjie Zhang. Improved algorithms for fully dynamic maximal independent set. arXiv:1804.08908, 2018.arxiv.org/abs/1804.08908
  22. [24]Maxime Flin and Magnús M. Halldórsson. Faster dynamic (Δ + 1)-coloring against adaptive adversaries. In Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025), volume 334 of LIPIcs, pages 79:1–79:21. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.DOI
  23. [25]Mohsen Ghaffari and Christoph Grunau. Dynamic O(Arboricity) coloring in polylogarithmic worst-case time. In Proceedings of the 56th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2024), pages 1184–1191. ACM, 2024.arxiv.org/abs/2410.19536
  24. [26]Yuval Gil and Magnús M. Halldórsson. Dynamic (Δ + 1)-coloring against an adaptive adversary: Faster, simpler, worst-case, and bounded recourse. In Proceedings of the 38th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2027). SIAM, 2027. To appear. Full version: arXiv:2610.26182.arxiv.org/abs/2610.26182
  25. [27]Manoj Gupta and Shahbaz Khan. Simple dynamic algorithms for maximal independent set and other problems. arXiv:1804.01823, 2018.arxiv.org/abs/1804.01823
  26. [28]Manoj Gupta and Shahbaz Khan. Simple dynamic algorithms for maximal independent set, maximum flow and maximum matching. In Proceedings of the 4th Symposium on Simplicity in Algorithms (SOSA 2021), pages 86–91. SIAM, 2021.DOI
  27. [29]Manoj Gupta, Shahbaz Khan, and Madhu Surendra. Dynamic MIS revisited: Incremental, fault tolerant and fully dynamic. In Proceedings of the 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026), volume 370 of LIPIcs, pages 21:1–21:11. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026.
  28. [30]Yu Gao, Yang P. Liu, and Richard Peng. Fully dynamic electrical flows: Sparse maxflow faster than Goldberg–Rao. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021), pages 516–527. IEEE, 2021.
  29. [31]Mohsen Ghaffari and Anton Trygub. Parallel dynamic maximal matching. In Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2024), pages 427–437. ACM, 2024.arxiv.org/abs/2409.15476
  30. [32]Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. In Proceedings of the 30th Annual ACM SIGACT Symposium on Theory of Computing (STOC 1998), pages 79–89. ACM, 1998.
  31. [33]Kathrin Hanauer, Monika Henzinger, and Christian Schulz. Faster fully dynamic transitive closure in practice. In Proceedings of the 18th International Symposium on Experimental Algorithms (SEA 2020), volume 160 of LIPIcs, pages 14:1–14:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.arxiv.org/abs/2002.00813
  32. [36]Monika Henzinger and Pan Peng. Constant-time dynamic weight approximation for minimum spanning forest. Information and Computation, 281:104805, 2021.arxiv.org/abs/2011.00977
  33. [37]Monika Henzinger and Pan Peng. Constant-time dynamic (Δ + 1)-coloring. ACM Transactions on Algorithms, 18(2):16:1–16:21, 2022.DOI
  34. [38]Wenyu Jin and Xiaorui Sun. Fully dynamic s-t edge connectivity in subpolynomial time (extended abstract). In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021), pages 861–872. IEEE, 2021.DOI
  35. [39]Shahbaz Khan and Anshul Kumar. Dynamic maximal independent set using predictions. arXiv:2610.16637, 2026.arxiv.org/abs/2610.16637
  36. [40]Yang P. Liu. On approximate fully-dynamic matching and online matrix-vector multiplication. In Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024), pages 228–243. IEEE Computer Society, 2024.arxiv.org/abs/2403.02582
  37. [41]Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. In Proceedings of the 45th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2013), pages 745–754. ACM, 2013.
  38. [43]Krzysztof Onak, Baruch Schieber, Shay Solomon, and Nicole Wein. Fully dynamic MIS in uniformly sparse graphs. ACM Transactions on Algorithms, 16(2):26:1–26:19, 2020.
  39. [44]Piotr Sankowski. Dynamic transitive closure via dynamic matrix inverse (extended abstract). In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2004), pages 509–517. IEEE Computer Society, 2004.DOI
  40. [45]Shay Solomon. Fully dynamic maximal matching in constant update time. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pages 325–334. IEEE Computer Society, 2016.arxiv.org/abs/1604.08491
  41. [46]Jan van den Brand and Adam Karczmarz. Deterministic fully dynamic SSSP and more. In Proceedings of the 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023), pages 2312–2321. IEEE, 2023.arxiv.org/abs/2309.16594
  42. [47]Jan van den Brand, Yang P. Liu, and Aaron Sidford. Dynamic maxflow via dynamic interior point methods. In Proceedings of the 55th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2023), pages 1215–1228. ACM, 2023.arxiv.org/abs/2212.06315
  43. [48]David Wajc. Rounding dynamic matchings against an adaptive adversary. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), pages 194–207. ACM, 2020.arxiv.org/abs/1911.05545

Paper details

vlnc:W_nuv5mrbk
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents