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) G = ( V , E ) with n n n vertices that undergoes a sequence of edge insertions and deletions. Throughout, m m m denotes an upper bound on the number of edges ∣ E ∣ |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 M ⊆ V is an independent set if no two vertices in M \mathcal{M} M are adjacent. It is a maximal independent set (MIS) if no proper superset of M \mathcal{M} M is independent; equivalently, every vertex in V ∖ M V \setminus\mathcal{M} V ∖ M has a neighbor in M \mathcal{M} M . A vertex outside M \mathcal{M} M is dominated if it has a neighbor in M \mathcal{M} 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) O ( max v ∈ 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 ( m 3 / 4 ) O(m^{3/4}) O ( m 3/4 ) amortized bound [1 ] . Gupta and Khan subsequently improved this to O ( m 2 / 3 ) O(m^{2/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 ( m 2 / 3 log m ) O(m^{2/3}\sqrt{\log m}) O ( m 2/3 log m ) update time [23 ] . The resulting O ( min { n , m 2 / 3 } ) O(\min\{n, m^{2/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}) O ( 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 ( m 2 / 3 ) O(m^{2/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) Ω ( n ) membership changes in a single edge update [1 Appendix A] . Consequently, o ( n ) 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 n 1 − o ( 1 ) n^{1-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 m 1 / 2 − o ( 1 ) m^{1/2-o(1)} m 1/2 − o ( 1 ) amortized update time for every graph sparsity from m = Θ ( n ) m = \Theta(n) m = Θ ( n ) to m = Θ ( n 2 ) m = \Theta(n^2) m = Θ ( n 2 ) . This leaves a gap between the m 1 / 2 − o ( 1 ) m^{1/2-o(1)} m 1/2 − o ( 1 ) lower bound and the O ( m 2 / 3 ) O(m^{2/3}) O ( m 2/3 ) upper bound. Gupta, Khan, and Surendra recently obtained an alternative deterministic O ( m 2 / 3 ) O(m^{2/3}) O ( m 2/3 ) fully dynamic algorithm and highlighted the goal of improving this bound to match their O ( m ) O(\sqrt{m}) O ( 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 ( m 2 / 3 − ϵ ) O(m^{2/3-\epsilon}) O ( m 2/3 − ϵ ) amortized update time for some constant ϵ > 0 \epsilon> 0 ϵ > 0 ?
Our Result
We answer this question affirmatively by giving the first polynomial improvement over the m 2 / 3 m^{2/3} m 2/3 update-time bound for fully dynamic MIS against adaptive adversaries.
Theorem 1.1. Let G = ( V , E ) G = (V, E) G = ( V , E ) be an initially empty undirected graph on n n n vertices that undergoes a sequence of edge insertions and deletions, with at most m m m edges at any time. There is a randomized algorithm that maintains a maximal independent set of G G G against adaptive adversaries with amortized update time O ~ ( m 5 / 8 ) = O ~ ( m 2 / 3 − 1 / 24 ) \widetilde{O}(m^{5/8}) = \widetilde{O}(m^{2/3-1/24}) O ( m 5/8 ) = O ( m 2/3 − 1/24 ) .
The basic O ( m 2 / 3 ) O(m^{2/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 D D D . 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) 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) O ( m / D ) high degree vertices, so rebuilding costs O ( ( m / D ) 2 ) O((m/D)^2) O (( m / D ) 2 ) . Balancing the two costs with D = m 2 / 3 D = m^{2/3} D = m 2/3 gives the O ( m 2 / 3 ) O(m^{2/3}) O ( m 2/3 ) bound.
Our approach. The main bottleneck is rebuilding the MIS on the high degree subgraph: lowering D D D 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 m 2 / 3 m^{2/3} m 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}) O ( m ) amortized update time [29 ] . Moreover, the conditional m 1 / 2 − o ( 1 ) m^{1/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 ( α 2 log 2 n ) O(\alpha^2 \log^2 n) O ( α 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 u u u fully dynamic updates, their algorithm uses O ( u n ) O(un) O ( u n ) preprocessing time and space and achieves O ( η e + η v ∗ ) O(\eta_e+\eta_v^*) O ( η e + η v ∗ ) worst-case time per update after the first prediction error. In their basic error model, η e \eta_e η e counts the distinct edges updated since the first mismatch. The parameter η v ∗ \eta_v^* η 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) O ( log n ) expected amortized update time [12 ] , which Solomon improved to O ( 1 ) 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}) O ( m ) worst-case update bound [41 ] . This bound is o ( n ) o(n) o ( n ) when m = o ( n 2 ) m=o(n^2) m = o ( n 2 ) , but remains O ( n ) O(n) O ( n ) when m = Θ ( n 2 ) m=\Theta(n^2) m = Θ ( n 2 ) . In 2025, Bernstein, Bhattacharya, Kiss, and Saranurak gave a deterministic algorithm with O ~ ( n 8 / 9 ) \widetilde{O}(n^{8/9}) O ( n 8/9 ) amortized update time and a randomized algorithm with O ~ ( n 3 / 4 ) \widetilde{O}(n^{3/4}) O ( n 3/4 ) amortized update time against adaptive adversaries [5 ] . In 2026, Chuzhoy, Khanna, and Song improved the deterministic bound to n 1 / 2 + o ( 1 ) n^{1/2+o(1)} n 1/2 + o ( 1 ) amortized update time [17 ] .
Vertex coloring. For ( Δ + 1 ) (\Delta+ 1) ( Δ + 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) O ( 1 ) expected amortized update time against oblivious adversaries. In 2025, Behnezhad, Rajaraman, and Wasim obtained an algorithm against adaptive adversaries with O ~ ( n 8 / 9 ) \widetilde{O}(n^{8/9}) O ( n 8/9 ) amortized update time [14 ] , which Flin and Halldórsson improved to O ~ ( n 2 / 3 ) \widetilde{O}(n^{2/3}) O ( n 2/3 ) amortized update time [24 ] . Very recently, two independent concurrent works achieved O ~ ( n 1 / 2 ) \widetilde{O}(n^{1/2}) 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) O ( α ) -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) ( 2Δ − 1 ) -edge coloring in O ( log Δ ) O(\log\Delta) O ( log Δ ) worst-case update time. Duan, He, and Zhang [21 ] reduced the number of colors to ( 1 + ϵ ) Δ (1 + \epsilon)\Delta ( 1 + ϵ ) Δ with poly ( log n , ϵ − 1 ) \operatorname{poly}(\log n,\epsilon^{-1}) poly ( log n , ϵ − 1 ) amortized update time when Δ = Ω ( ϵ − 2 log 2 n ) \Delta= \Omega(\epsilon^{-2}\log^2 n) Δ = Ω ( ϵ − 2 log 2 n ) . Christiansen [15 ] removed this degree restriction and obtained poly ( log n , ϵ − 1 ) \operatorname{poly}(\log n,\epsilon^{-1}) poly ( log n , ϵ − 1 ) worst-case update time against adaptive adversaries. For fixed ϵ > 0 \epsilon> 0 ϵ > 0 and Δ \Delta Δ above an ϵ \epsilon ϵ -dependent polylogarithmic threshold, Bhattacharya, Costa, Panski, and Solomon [BCPS24b] achieved O ( 1 ) O(1) O ( 1 ) expected update time against oblivious adversaries. On the deterministic side, Christiansen [16 ] obtained ( 1 + ϵ ) Δ (1 + \epsilon)\Delta ( 1 + ϵ ) Δ -edge coloring with n o ( 1 ) n^{o(1)} n o ( 1 ) amortized update time for fixed ϵ > 0 \epsilon> 0 ϵ > 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)) ( Δ + O ( α )) -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 ( 1 + ϵ ) Δ -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 n 1 − o ( 1 ) n^{1-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 m m m . 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) G = ( V , E ) on a fixed set of n n n vertices, undergoing edge insertions and deletions. Let m m m be a fixed upper bound on the number of edges throughout the update sequence. Initially, the maintained MIS is M = V \mathcal{M} = V M = V . Write N ( v ) N(v) N ( v ) for the current neighbor set of v v v , deg ( v ) = ∣ N ( v ) ∣ \deg(v) = |N(v)| deg ( v ) = ∣ N ( v ) ∣ , N ( S ) = ⋃ v ∈ S N ( v ) N(S) = \bigcup_{v \in S} N(v) N ( S ) = ⋃ v ∈ S N ( v ) , and G [ S ] G[S] G [ S ] for the subgraph induced by S ⊆ V S \subseteq V S ⊆ V . An independent set M \mathcal{M} M is maximal precisely when every vertex outside M \mathcal{M} M has a neighbor in M \mathcal{M} 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 − c n^{-c} n − c for an arbitrarily large fixed constant c > 0 c > 0 c > 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 ( m 2 / 3 ) O(m^{2/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 D D D . Partition the vertices into V l o V_{\mathrm{lo}} V lo , with degree at most D D D , and V h i V_{\mathrm{hi}} V hi , with degree greater than D D D . Maintain an MIS M l o \mathcal{M}_{\mathrm{lo}} M lo of G [ V l o ] G[V_{\mathrm{lo}}] G [ V lo ] , giving low vertices priority over high vertices, and extend it by an MIS M h i \mathcal{M}_{\mathrm{hi}} M hi of G [ V h i ∖ N ( M l o ) ] G[V_{\mathrm{hi}} \setminus N(\mathcal{M}_{\mathrm{lo}})] G [ V hi ∖ N ( M lo )] . We call M l o \mathcal{M}_{\mathrm{lo}} M lo and M h i \mathcal{M}_{\mathrm{hi}} M 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) O ( D ) amortized time per update. Maintain each vertex’s number of neighbors in M l o \mathcal{M}_{\mathrm{lo}} M lo , and greedily include a low vertex in M l o \mathcal{M}_{\mathrm{lo}} M lo when its count becomes zero. For each such vertex, scan at most D D D edges to update these counts. Although many vertices can join M l o \mathcal{M}_{\mathrm{lo}} M lo during one update, the potential decreases enough to pay for all their scans: assign potential Θ ( D ) \Theta(D) Θ ( D ) to each low vertex outside M l o \mathcal{M}_{\mathrm{lo}} M lo , so that including it in M l o \mathcal{M}_{\mathrm{lo}} M 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) O ( D ) per update, giving the claimed amortized bound.
As illustrated in Figure 1 , including even one vertex in M l o \mathcal{M}_{\mathrm{lo}} M lo can invalidate the current high-layer MIS. After restoring maximality in the low layer, rebuild M h i \mathcal{M}_{\mathrm{hi}} M hi from scratch. The counters identify the high vertices with no neighbor in M l o \mathcal{M}_{\mathrm{lo}} M lo , and ∣ V h i ∣ ≤ 2 m / D |V_{\mathrm{hi}}| \le2m/D ∣ V hi ∣ ≤ 2 m / D , so this costs O ( ( m / D ) 2 ) O((m/D)^2) O (( m / D ) 2 ) time.
Figure 1. The bottleneck in the O ( m 2 / 3 ) O(m^{2/3}) O ( m 2/3 ) amortized algorithm. Before a low degree vertex v v v joins M l o \mathcal{M}_{\mathrm{lo}} M lo , its high-MIS neighbors (crosses) leave M h i \mathcal{M}_{\mathrm{hi}} M hi . The algorithm rebuilds M h i \mathcal{M}_{\mathrm{hi}} M hi on V h i ∖ N ( M l o ) V_{\mathrm{hi}} \setminus N(\mathcal{M}_{\mathrm{lo}}) V hi ∖ N ( M lo ) , costing O ( ∣ V h i ∣ 2 ) = O ( ( m / D ) 2 ) O(|V_{\mathrm{hi}}|^2) = O((m/D)^2) O ( ∣ V hi ∣ 2 ) = O (( m / D ) 2 ) per update.
Consequently, the amortized update time is
O ( D + m 2 D 2 ) , O\left(D+\frac{m^2}{D^2}\right), O ( D + D 2 m 2 ) ,
which is minimized at D = Θ ( m 2 / 3 ) D=\Theta(m^{2/3}) D = Θ ( m 2/3 ) .
Lowering the degree threshold. To bypass the m 2 / 3 m^{2/3} m 2/3 barrier, a natural starting point is to lower the degree threshold from m 2 / 3 m^{2/3} m 2/3 to m 2 / 3 − ϵ m^{2/3-\epsilon} m 2/3 − ϵ , for some constant ϵ > 0 \epsilon> 0 ϵ > 0 . Maintaining the MIS on the low degree part would then cost only O ( m 2 / 3 − ϵ ) O(m^{2/3-\epsilon}) O ( m 2/3 − ϵ ) amortized time. The bottleneck is updating the high degree part: when a vertex v ∈ V l o v \in V_{\mathrm{lo}} v ∈ V lo joins M l o \mathcal{M}_{\mathrm{lo}} M lo , it may be adjacent to many vertices of M h i \mathcal{M}_{\mathrm{hi}} M hi , all of which must leave the MIS. These removals can affect most vertices in V h i V_{\mathrm{hi}} V hi . With the lower threshold, the bound becomes ∣ V h i ∣ = O ( m 1 / 3 + ϵ ) |V_{\mathrm{hi}}| = O(m^{1/3+\epsilon}) ∣ V hi ∣ = O ( m 1/3 + ϵ ) , so rebuilding the high-layer MIS from scratch costs O ( m 2 / 3 + 2 ϵ ) O(m^{2/3+2\epsilon}) O ( m 2/3 + 2 ϵ ) time.
Leaving dominated low vertices outside the MIS. If a low vertex v v v has many neighbors in M h i \mathcal{M}_{\mathrm{hi}} M hi , we can leave it outside M l o \mathcal{M}_{\mathrm{lo}} M lo . Even if v v v has no neighbor in M l o \mathcal{M}_{\mathrm{lo}} M lo , its high-MIS neighbors already certify that it is dominated. We can therefore leave v v v outside the MIS and avoid removing all of these neighbors from M h i \mathcal{M}_{\mathrm{hi}} M hi . This relaxes the requirement that M l o \mathcal{M}_{\mathrm{lo}} M lo be maximal in G [ V l o ] G[V_{\mathrm{lo}}] G [ V lo ] : a low vertex may instead rely on the high layer for domination. We only include such a vertex in the MIS when it has few high-MIS neighbors, limiting the number of high-MIS vertices that must leave the MIS before it joins.
Sampling lets us distinguish vertices that should remain dominated from those that can enter the MIS with few conflicts. To illustrate, suppose every low vertex has either Θ ( m 1 / 3 + ϵ ) \Theta(m^{1/3+\epsilon}) Θ ( m 1/3 + ϵ ) high-MIS neighbors or only O ( 1 ) O(1) O ( 1 ) . In the first case, a constant fraction of V h i V_{\mathrm{hi}} V hi provides witnesses, so O ( log n ) O(\log n) O ( log n ) uniform samples find one with high probability for a fixed graph and MIS. A vertex for which no witness is found therefore has only O ( 1 ) O(1) O ( 1 ) high-MIS neighbors, with high probability.
These few conflicts allow local repair of the high layer in O ( ∣ V h i ∣ ) O(|V_{\mathrm{hi}}|) O ( ∣ V hi ∣ ) amortized time: maintain exact counters within that layer and use the same potential argument as for the low layer to pay for subsequent vertices that join M h i \mathcal{M}_{\mathrm{hi}} M hi greedily. Including the scan that finds the conflicts and the low vertex’s neighborhood scan, including a vertex in M l o \mathcal{M}_{\mathrm{lo}} M lo costs O ( m 1 / 3 + ϵ + m 2 / 3 − ϵ ) O(m^{1/3+\epsilon} + m^{2/3-\epsilon}) O ( m 1/3 + ϵ + m 2/3 − ϵ ) amortized time. Both terms are below m 2 / 3 m^{2/3} m 2/3 for sufficiently small ϵ > 0 \epsilon> 0 ϵ > 0 .
Maintaining domination of candidate vertices. This idea leaves a primary candidate set C 1 ⊆ V l o ∖ M l o C_1 \subseteq V_{\mathrm{lo}} \setminus\mathcal{M}_{\mathrm{lo}} C 1 ⊆ V lo ∖ M lo whose vertices have no neighbor in M l o \mathcal{M}_{\mathrm{lo}} M lo and are dominated solely by M h i \mathcal{M}_{\mathrm{hi}} M hi . The challenge is to preserve this domination guarantee as M h i \mathcal{M}_{\mathrm{hi}} M hi changes. When a high vertex x x x leaves the MIS, a candidate adjacent to x x x may lose its last MIS neighbor and must be reconsidered to restore maximality. Maintaining exact high-MIS-neighbor counters for all candidates would require updating every candidate adjacent to x x x . Even a single high-MIS removal can therefore require scanning a large fraction of C 1 C_1 C 1 , with no bound below m 2 / 3 m^{2/3} m 2/3 ; including a vertex in M h i \mathcal{M}_{\mathrm{hi}} M hi causes the same counter-maintenance problem.
Storing just one high-MIS neighbor as a domination witness for each candidate does not immediately resolve this difficulty. A single high vertex may serve as the witness for many candidates. When it leaves, it no longer serves as an MIS neighbor for any of them, even if the affected candidates still have many other neighbors in M h i \mathcal{M}_{\mathrm{hi}} M hi . Searching for a replacement separately for each candidate can again be expensive. Thus, limiting the number of vertices removed from M h i \mathcal{M}_{\mathrm{hi}} M hi when a low vertex joins the MIS is only part of the problem: we must also limit the work needed to discover which candidates require attention and to maintain their domination witnesses.
Checkpoint: domination edge lists. We maintain a sample of each candidate’s high-MIS neighbors so that losing one witness need not trigger a new search. For each v ∈ C 1 v \in C_1 v ∈ C 1 , sample its edges to M h i \mathcal{M}_{\mathrm{hi}} M hi independently with probability p p p and store them in its high domination edge list A v h i A_v^{\mathrm{hi}} A v hi . As long as this list is nonempty, v v v remains dominated and stays outside the MIS.
To find the candidates affected by a high-MIS removal, also collect the sampled edges incident to each x ∈ M h i x \in\mathcal{M}_{\mathrm{hi}} x ∈ M hi in a reverse list R x h i R^{\mathrm{hi}}_x R x hi . To update the candidates’ sampled lists after x x x leaves M h i \mathcal{M}_{\mathrm{hi}} M hi , traverse R x h i R^{\mathrm{hi}}_x R x hi , remove the entries for its sampled edges from the candidates’ lists, and reconsider candidates whose lists become empty. Such a candidate enters M l o \mathcal{M}_{\mathrm{lo}} M lo after its conflicting high-MIS neighbors are removed from M h i \mathcal{M}_{\mathrm{hi}} M hi . Thus the cost of finding affected candidates depends on the reverse-list size, rather than on all of x x x ’s candidate neighbors.
When a candidate enters C 1 C_1 C 1 , initialize its list by sampling edges to the current high MIS. When a high vertex enters the MIS, sample its edges to the current candidates with the same probability p p p . A newly inserted graph edge is also sampled if it joins a high-MIS vertex to a candidate. Each such sampling decision uses a fresh independent bit. The algorithm does not resample this bit while the edge exists, its high endpoint remains in the MIS, and the candidate’s list remains stored. If any of these conditions stops holding, the bit is discarded. When all three hold again, the edge is sampled with a fresh independent bit. Each selected edge is stored in both lists, as illustrated in Figure 2 .
Figure 2. Domination edges in the two-layer construction. Gray lines show other edges. Arrows orient the sampled edges from C 1 C_1 C 1 toward M h i \mathcal{M}_{\mathrm{hi}} M hi : each edge v → x v \to x v → x is stored in the high domination edge list A v h i A^{\mathrm{hi}}_v A v hi and in the reverse list R x h i R^{\mathrm{hi}}_x R x hi . For example, three high domination edge lists contribute edges to R x 2 h i R^{\mathrm{hi}}_{x_2} R x 2 hi .
An empty list suggests that including the vertex in the MIS requires few high-MIS removals. To quantify this, choose p = m δ − 1 / 3 p = m^{\delta-1/3} p = m δ − 1/3 with ϵ < δ < 1 / 3 \epsilon< \delta< 1/3 ϵ < δ < 1/3 , and write k v = ∣ N ( v ) ∩ M h i ∣ k_v = |N(v) \cap\mathcal{M}_{\mathrm{hi}}| k v = ∣ N ( v ) ∩ M hi ∣ . For a fixed neighborhood and independent sampling,
Pr [ A v h i = ∅ ] = ( 1 − p ) k v ≤ e − p k v . \Pr[A^{\mathrm{hi}}_v = \varnothing] = (1-p)^{k_v} \le e^{-p k_v}. Pr [ A v hi = ∅ ] = ( 1 − p ) k v ≤ e − p k v .
Thus, for any constant c > 0 c > 0 c > 0 , a vertex with k v ≥ c m 1 / 3 − δ log n k_v \ge c m^{1/3-\delta} \log n k v ≥ c m 1/3 − δ log n has an empty list with probability at most n − c n^{-c} n − c . This suggests that whenever we include a candidate with an empty list in the MIS, it has only O ~ ( m 1 / 3 − δ ) \widetilde{O}(m^{1/3-\delta}) O ( m 1/3 − δ ) high-MIS neighbors. Scanning its neighborhood costs O ( m 2 / 3 − ϵ ) O(m^{2/3-\epsilon}) O ( m 2/3 − ϵ ) , and removing these neighbors from M h i \mathcal{M}_{\mathrm{hi}} M hi and restoring maximality in the high layer costs
O ~ ( m 1 / 3 − δ ⋅ ∣ V h i ∣ ) = O ~ ( m 2 / 3 + ϵ − δ ) \widetilde{O}(m^{1/3-\delta} \cdot|V_{\mathrm{hi}}|) = \widetilde{O}(m^{2/3+\epsilon-\delta}) O ( m 1/3 − δ ⋅ ∣ V hi ∣ ) = O ( m 2/3 + ϵ − δ )
amortized time, since each vertex that subsequently joins M h i \mathcal{M}_{\mathrm{hi}} M hi decreases the potential as above. Both exponents are below 2 / 3 2/3 2/3 when δ > ϵ \delta> \epsilon δ > ϵ ; choosing δ ≥ 2 ϵ \delta\ge2\epsilon δ ≥ 2 ϵ makes this high-layer update cost at most O ~ ( m 2 / 3 − ϵ ) \widetilde{O}(m^{2/3-\epsilon}) O ( m 2/3 − ϵ ) .
This preliminary algorithm leaves two challenges: bounding the maintenance cost and justifying the sampling guarantees under adaptive updates. We first address the maintenance cost and then turn to adaptivity.
Controlling the cost of maintaining candidate domination. The preceding time bound accounts only for work within the high layer. For a fixed candidate neighborhood independent of the sample, a high vertex has at most p ∣ C 1 ∣ p|C_1| p ∣ C 1 ∣ sampled candidate edges in expectation. Since ∣ C 1 ∣ |C_1| ∣ C 1 ∣ can be O ( m ) O(m) O ( m ) , this calculation gives only an O ( p m ) = O ( m 2 / 3 + δ ) O(pm)=O(m^{2/3+\delta}) O ( p m ) = O ( m 2/3 + δ ) upper bound on the expected number of sampled candidate edges traversed during a high-MIS removal. This bound is insufficient for the target update time.
Making the sampling argument valid against adaptive updates. The empty-list calculation assumes a fixed neighborhood independent of the sample. Here the sampled lists influence which low vertices enter the MIS, and an adversary can use the reported MIS to choose future updates. Consequently, the current high-MIS neighborhood and the edges stored in the sampled list need not be independent. We must show that an empty list still implies few high-MIS neighbors with sufficiently high probability under this dependence.
Middle Degree Class
Periodic candidate rebuild. Reverse-list maintenance becomes expensive when too many low vertices depend on the high MIS. We therefore try to keep C 1 C_1 C 1 small by periodically eliminating its dependence on that layer. Remove every vertex from the high MIS and process the candidates in C 1 C_1 C 1 , including each in M l o \mathcal{M}_{\mathrm{lo}} M lo if it has no low-MIS neighbor. Whenever a candidate joins M l o \mathcal{M}_{\mathrm{lo}} M lo , update the low counters before processing the next candidate. Every former candidate then belongs to M l o \mathcal{M}_{\mathrm{lo}} M lo or has a neighbor in M l o \mathcal{M}_{\mathrm{lo}} M lo , so C 1 C_1 C 1 is empty. We can now rebuild M h i \mathcal{M}_{\mathrm{hi}} M hi on G [ V h i ∖ N ( M l o ) ] G[V_{\mathrm{hi}}\setminus N(\mathcal{M}_{\mathrm{lo}})] G [ V hi ∖ N ( M lo )] .
Whenever a vertex joins M l o \mathcal{M}_{\mathrm{lo}} M lo , the potential decreases enough to pay for its neighborhood scan, as before. The high-layer reconstruction, however, costs O ( ∣ V h i ∣ ) = O ( m 2 / 3 + 2 ϵ ) O(|V_{\mathrm{hi}}|)=O(m^{2/3+2\epsilon}) O ( ∣ V hi ∣ ) = O ( m 2/3 + 2 ϵ ) , which exceeds our target update time. Thus it is essential to show that these rebuilds are not too frequent. For example, to obtain an amortized contribution of O ~ ( m 2 / 3 − ϵ ) \widetilde{O}(m^{2/3-\epsilon}) O ( m 2/3 − ϵ ) , the number of reconstructions over T T T updates must be at most O ~ ( T / m 3 ϵ ) \widetilde{O}(T/m^{3\epsilon}) O ( T / m 3 ϵ ) . Since each reconstruction empties C 1 C_1 C 1 , a bound on how quickly new candidates enter C 1 C_1 C 1 can give the required bound on the number of reconstructions.
However, C 1 C_1 C 1 can grow substantially within a single update. Consider inserting an edge ( u , v ) (u,v) ( u , v ) with u , v ∈ M l o u,v\in\mathcal{M}_{\mathrm{lo}} u , v ∈ M lo . To restore independence, suppose that u u u leaves the MIS. The vertex u u u can have Θ ( m 2 / 3 − ϵ ) \Theta(m^{2/3-\epsilon}) Θ ( m 2/3 − ϵ ) low degree neighbors for which it was the only low-MIS neighbor. If these vertices remain dominated by the high layer, they can all become candidates in C 1 C_1 C 1 rather than enter M l o \mathcal{M}_{\mathrm{lo}} M lo . Thus a single edge update can create Θ ( m 2 / 3 − ϵ ) \Theta(m^{2/3-\epsilon}) Θ ( m 2/3 − ϵ ) new candidates, even if C 1 C_1 C 1 was empty immediately beforehand. A small candidate threshold can therefore be reached within a single update. To keep reverse lists short while bounding the total rebuilding cost, we need a tighter bound on how quickly candidates are created.
Middle degree class. To limit candidate growth, we lower the low degree threshold to m 3 / 8 m^{3/8} m 3/8 . A low-MIS removal can then create only O ( m 3 / 8 ) O(m^{3/8}) O ( m 3/8 ) new low candidates. We set the high degree threshold to m 5 / 8 m^{5/8} m 5/8 and place the vertices between these thresholds in a new middle degree class:
V l o = { v : deg ( v ) < m 3 / 8 } , V_{\mathrm{lo}}=\{v:\deg(v)<m^{3/8}\}, V lo = { v : deg ( v ) < m 3/8 } ,
V m i d = { v : m 3 / 8 ≤ deg ( v ) < m 5 / 8 } , V_{\mathrm{mid}}=\{v:m^{3/8}\leq\deg(v)<m^{5/8}\}, V mid = { v : m 3/8 ≤ deg ( v ) < m 5/8 } ,
V h i = { v : deg ( v ) ≥ m 5 / 8 } . V_{\mathrm{hi}}=\{v:\deg(v)\geq m^{5/8}\}. V hi = { v : deg ( v ) ≥ m 5/8 } .
As before, write M i = M ∩ V i \mathcal{M}_i=\mathcal{M}\cap V_i M i = M ∩ V i for each MIS layer; their union is independent, although a layer need not be maximal within its own degree class. The degree bounds give
∣ V m i d ∣ = O ( m 5 / 8 ) , ∣ V h i ∣ = O ( m 3 / 8 ) . |V_{\mathrm{mid}}|=O(m^{5/8}),\qquad|V_{\mathrm{hi}}|=O(m^{3/8}). ∣ V mid ∣ = O ( m 5/8 ) , ∣ V hi ∣ = O ( m 3/8 ) .
We still need to avoid expensive middle-MIS removals when a low vertex joins the MIS. Suppose that, whenever a low vertex v v v loses its last low-MIS neighbor, we include it in M l o \mathcal{M}_{\mathrm{lo}} M lo and remove all of its neighbors from M m i d \mathcal{M}_{\mathrm{mid}} M mid . Even though v v v has degree O ( m 3 / 8 ) O(m^{3/8}) O ( m 3/8 ) , each removed middle vertex can have degree Θ ( m 5 / 8 ) \Theta(m^{5/8}) Θ ( m 5/8 ) . Scanning their entire neighborhoods can therefore cost O ( m ) O(m) O ( m ) for one low vertex to join the MIS. We must therefore limit conflicts with the middle MIS or avoid creating them.
Secondary Candidates and Exact Middle Domination
The same principle that motivates C 1 C_1 C 1 applies here: if including a low vertex v v v in the MIS would require removing its neighbors from M m i d \mathcal{M}_{\mathrm{mid}} M mid , those neighbors already dominate v v v , so we leave it outside the MIS. We introduce a secondary candidate set C 2 ⊆ V l o ∖ M C_2 \subseteq V_{\mathrm{lo}} \setminus\mathcal{M} C 2 ⊆ V lo ∖ M for low vertices with no low-MIS neighbor that remain outside the MIS because they are dominated by the middle layer. Thus we allow a low vertex to be dominated by M m i d \mathcal{M}_{\mathrm{mid}} M mid without being dominated by M l o \mathcal{M}_{\mathrm{lo}} M lo .
Maintaining exact middle domination. The maximum degree of a middle vertex is O ( m 5 / 8 ) O(m^{5/8}) O ( m 5/8 ) , which fits our target update bound. We can therefore maintain the exact counter
d m i d ( v ) = ∣ N ( v ) ∩ M m i d ∣ d_{\mathrm{mid}}(v) = \lvert N(v) \cap\mathcal{M}_{\mathrm{mid}} \rvert d mid ( v ) = ∣ N ( v ) ∩ M mid ∣
for every vertex, including low vertices. When a middle vertex v v v joins M m i d \mathcal{M}_{\mathrm{mid}} M mid , increment d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) for every neighbor z ∈ N ( v ) z \in N(v) z ∈ N ( v ) ; when v v v leaves M m i d \mathcal{M}_{\mathrm{mid}} M mid , decrement d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) for every such neighbor.
The exact counters separate candidates according to which higher layer must dominate them. Writing d l o ( v ) = ∣ N ( v ) ∩ M l o ∣ d_{\mathrm{lo}}(v) = \lvert N(v) \cap\mathcal{M}_{\mathrm{lo}} \rvert d lo ( v ) = ∣ N ( v ) ∩ M lo ∣ , we maintain
C 1 = { v ∈ V l o ∖ M : d l o ( v ) = 0 and d m i d ( v ) = 0 } , C 2 = { v ∈ V l o ∖ M : d l o ( v ) = 0 and d m i d ( v ) > 0 } . \begin{aligned}
C_1 &= \{v \in V_{\mathrm{lo}} \setminus\mathcal{M} : d_{\mathrm{lo}}(v) = 0 \text{ and } d_{\mathrm{mid}}(v) = 0\},\\
C_2 &= \{v \in V_{\mathrm{lo}} \setminus\mathcal{M} : d_{\mathrm{lo}}(v) = 0 \text{ and } d_{\mathrm{mid}}(v) > 0\}.
\end{aligned} C 1 C 2 = { v ∈ V lo ∖ M : d lo ( v ) = 0 and d mid ( v ) = 0 } , = { v ∈ V lo ∖ M : d lo ( v ) = 0 and d mid ( v ) > 0 } .
The middle counter already certifies domination for C 2 C_2 C 2 . Vertices in C 1 C_1 C 1 must instead have high-MIS witnesses at the end of each update, which we maintain through sampled high domination edges. Together, C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 is the candidate union : every other low vertex outside the MIS has a low-MIS neighbor.
A vertex in C 2 C_2 C 2 can remain there indefinitely. Its middle counter already certifies domination, so it needs no high domination edge list. We do not impose a size bound on C 2 C_2 C 2 and do not rebuild merely because C 2 C_2 C 2 is large. When its last middle-MIS neighbor disappears, it moves to C 1 C_1 C 1 . This transition changes which layer must dominate the vertex, but it does not create a new member of C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 .
To bound growth of the candidate union, consider both changes in degree class and the loss of a low vertex’s last low-MIS neighbor. We distinguish new entries into the union from work on vertices that are already candidates:
Degree-class changes create few new candidates. Only the updated edge’s endpoints can change class. An endpoint entering the low degree class contributes at most one candidate. When a low-MIS vertex moves to the middle degree class, only its O ( m 3 / 8 ) O(m^{3/8}) O ( m 3/8 ) neighbors can lose a low-MIS neighbor. Other degree-class changes do not enlarge the candidate union.
A single low-MIS removal creates few new candidates. Inserting ( s , t ) (s,t) ( s , t ) with s , t ∈ M l o s,t \in\mathcal{M}_{\mathrm{lo}} s , t ∈ M lo removes one of s , t s,t s , t from the MIS. The removal affects only the removed vertex and its O ( m 3 / 8 ) O(m^{3/8}) O ( m 3/8 ) neighbors. Thus at most O ( m 3 / 8 ) O(m^{3/8}) O ( m 3/8 ) low vertices enter the candidate union. Deleting an edge incident to a low-MIS vertex can directly create only one new candidate.
Middle- and high-MIS removals do not directly enlarge the candidate union. These removals do not change any low-MIS-neighbor counter. A middle-MIS removal can move many vertices from C 2 C_2 C 2 to C 1 C_1 C 1 , but all of them were already candidates. A high-MIS removal can invalidate witnesses of existing vertices in C 1 C_1 C 1 , but again it does not create new candidates.
No vertex leaves M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid during maximality restoration. A low vertex v v v enters the MIS only when d l o ( v ) = d m i d ( v ) = 0 d_{\mathrm{lo}}(v) = d_{\mathrm{mid}}(v) = 0 d lo ( v ) = d mid ( v ) = 0 , so no middle-MIS vertex needs to leave when v v v joins the MIS. Similarly, a middle vertex joins the MIS only when it has no low- or middle-MIS neighbor. In either case, only high-MIS neighbors may need to leave the MIS. Thus restoration creates no further candidates through low-MIS removals.
The number of new entries into C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 per edge update is therefore O ( m 3 / 8 ) O(m^{3/8}) O ( m 3/8 ) . Assigning potential to each member of this union therefore gives a bounded potential increase per update. Transitions from C 2 C_2 C 2 to C 1 C_1 C 1 leave the union unchanged and do not increase this potential.
Checkpoint: the algorithm when C 1 C_1 C 1 is small. Keeping C 1 C_1 C 1 small makes sampled witness maintenance affordable: a high-MIS vertex needs to maintain sampled edges only to the middle vertices and to C 1 C_1 C 1 . For now, assume ∣ C 1 ∣ < B = m 1 / 2 |C_1| < B = m^{1/2} ∣ C 1 ∣ < B = m 1/2 throughout an update. Since ∣ V m i d ∣ = O ( m 5 / 8 ) |V_{\mathrm{mid}}| = O(m^{5/8}) ∣ V mid ∣ = O ( m 5/8 ) , there are only O ( m 5 / 8 ) O(m^{5/8}) O ( m 5/8 ) vertices in V m i d ∪ C 1 V_{\mathrm{mid}} \cup C_1 V mid ∪ C 1 whose lists may store sampled edges to high-MIS vertices. We sample each edge joining M h i \mathcal{M}_{\mathrm{hi}} M hi to V m i d ∪ C 1 V_{\mathrm{mid}} \cup C_1 V mid ∪ C 1 with probability
p h i = Θ ( m − 1 / 4 ) , p_{\mathrm{hi}} = \Theta(m^{-1/4}), p hi = Θ ( m − 1/4 ) ,
so the expected reverse-list size for a fixed sampling universe is O ( m 3 / 8 ) O(m^{3/8}) O ( m 3/8 ) , matching the number of high degree neighbors. An empty list should then imply only O ~ ( m 1 / 4 ) \widetilde{O}(m^{1/4}) O ( m 1/4 ) high-MIS neighbors. These two bounds let us remove all conflicting high-MIS neighbors of a low or middle vertex from M h i \mathcal{M}_{\mathrm{hi}} M hi in O ~ ( m 1 / 4 m 3 / 8 ) = O ~ ( m 5 / 8 ) \widetilde{O}(m^{1/4}m^{3/8}) = \widetilde{O}(m^{5/8}) O ( m 1/4 m 3/8 ) = O ( m 5/8 ) time; the vertex can then join the MIS. The probabilistic analysis below justifies these bounds under adaptive updates.
Requests and the repair queue. Repairs may propagate: including a low or middle vertex in the MIS can require removing its high-MIS neighbors from M h i \mathcal{M}_{\mathrm{hi}} M hi and leave other vertices needing attention. We keep these pending checks, called requests , in a queue Q Q Q , with at most one request per vertex. To check domination, we track low- and middle-MIS neighbors by exact counters at every vertex; high vertices also track their high-MIS neighbors exactly. A vertex outside the MIS is requested when these counters and its sampled witnesses no longer certify domination. Before acting on a request, we check again, since the vertex may have acquired an MIS neighbor while waiting.
Every current member of M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid remains in the MIS during maximality restoration. A low or middle vertex enters the MIS only when it has no low- or middle-MIS neighbor and its sampled high domination edge list is empty. Its remaining conflicts are therefore all in the high MIS, and we remove them from M h i \mathcal{M}_{\mathrm{hi}} M hi before including the vertex in the MIS. A high vertex joins the MIS only when its exact counters show that it has no MIS neighbor at all. Whenever a vertex joins the MIS, update the corresponding counters and witnesses, and the candidate sets follow their definitions above.
To begin repairing an edge update, update the affected counters and stored domination edges to reflect the edge change. If an insertion joins two MIS vertices, keep the endpoint with higher priority, giving priority to low vertices, then middle vertices, then high vertices, with a fixed vertex order within each class. Process the resulting requests in this same order until Q Q Q is empty.
A high-MIS removal finds the vertices needing attention by visiting its high degree neighbors and traversing its reverse list. These two traversals identify every counter and sampled witness that must change, allowing us to issue the resulting requests without scanning all low degree and middle degree neighbors. If a high vertex x x x is removed from M h i \mathcal{M}_{\mathrm{hi}} M hi so that a low degree or middle degree neighbor v v v can join the MIS, then x x x needs no request: v v v joins the MIS before the next request is extracted and then dominates x x x .
Amortized update time. The queue may have many extractions in one update. To bound their total amortized cost, assign potential to each vertex outside the MIS, with weights
W l o = W m i d = Θ ~ ( m 5 / 8 ) , W h i = Θ ~ ( m 3 / 8 ) . W_{\mathrm{lo}} = W_{\mathrm{mid}} = \widetilde{\Theta}(m^{5/8}), \qquad W_{\mathrm{hi}} = \widetilde{\Theta}(m^{3/8}). W lo = W mid = Θ ( m 5/8 ) , W hi = Θ ( m 3/8 ) .
Including a vertex in the MIS decreases the potential by its weight; removing it from the MIS increases the potential by the same weight. Assuming the sampling bounds justified below, the following calculations include both the work of removing conflicting vertices from M h i \mathcal{M}_{\mathrm{hi}} M hi and the potential needed for these vertices to rejoin the MIS later.
O ~ ( p h i ( ∣ V m i d ∣ + ∣ C 1 ∣ ) ) = O ~ ( m 3 / 8 ) , \widetilde{O}\left(p_{\mathrm{hi}}(\lvert V_{\mathrm{mid}}\rvert+ \lvert C_1\rvert)\right) = \widetilde{O}(m^{3/8}), O ( p hi (∣ V mid ∣ + ∣ C 1 ∣) ) = O ( m 3/8 ) ,
so a removal, including its potential increase, costs O ( W h i ) O(W_{\mathrm{hi}}) O ( W hi ) . When a high vertex x x x joins the MIS, independently sample V m i d V_{\mathrm{mid}} V mid and C 1 C_1 C 1 with probability p h i p_{\mathrm{hi}} p hi using Lemma 3.1. Test each sampled vertex z z z for adjacency to x x x and store each selected edge in both R x h i R^{\mathrm{hi}}_x R x hi and A z h i A^{\mathrm{hi}}_z A z hi . This constructs R x h i R^{\mathrm{hi}}_x R x hi within the same time bound, and the decrease of W h i W_{\mathrm{hi}} W hi pays for the work.
O ~ ( m 1 / 4 W h i ) = O ~ ( m 5 / 8 ) . \widetilde{O}(m^{1/4}W_{\mathrm{hi}}) = \widetilde{O}(m^{5/8}). O ( m 1/4 W hi ) = O ( m 5/8 ) .
Its full neighborhood scan is also within O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) . The potential decrease of W l o W_{\mathrm{lo}} W lo or W m i d W_{\mathrm{mid}} W mid offsets both terms.
O ~ ( p h i ∣ V h i ∣ ) = O ~ ( m 1 / 8 ) . \widetilde{O}(p_{\mathrm{hi}}\lvert V_{\mathrm{hi}}\rvert) = \widetilde{O}(m^{1/8}). O ( p hi ∣ V hi ∣) = O ( m 1/8 ) .
Add β = Θ ~ ( m 1 / 8 ) \beta= \widetilde{\Theta}(m^{1/8}) β = Θ ( m 1/8 ) to the potential for each vertex in C 1 C_1 C 1 . When a vertex z z z leaves C 1 C_1 C 1 during queue processing, the potential decreases by β \beta β , paying for deletion of its high domination edge list A z h i A^{\mathrm{hi}}_z A z hi and the entry for every stored edge ( z , x ) (z,x) ( z , x ) in R x h i R^{\mathrm{hi}}_x R x hi . A vertex in C 2 C_2 C 2 has no such list and contributes nothing to this potential term.
Periodic Candidate Rebuild
We now use the slow growth of C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 to pay for a periodic rebuild, called a flush , when C 1 C_1 C 1 becomes large. The flush must remove candidates from the union altogether: merely moving them from C 1 C_1 C 1 to C 2 C_2 C 2 would allow them to return without any new candidate being created. We therefore ensure that every current member of C 1 C_1 C 1 joins M l o \mathcal{M}_{\mathrm{lo}} M lo or has a neighbor in M l o \mathcal{M}_{\mathrm{lo}} M lo .
After applying the edge update and restoring independence, test whether ∣ C 1 ∣ ≥ B = m 1 / 2 \lvert C_1\rvert\ge B = m^{1/2} ∣ C 1 ∣ ≥ B = m 1/2 , before processing any queued request. If so, perform a flush; otherwise, construct the missing high domination edge lists and process the queue. These subsequent repairs can only shrink C 1 C_1 C 1 , so no further threshold test is needed. New low lists are constructed only when ∣ C 1 ∣ < B |C_1| < B ∣ C 1 ∣ < B , after this test, ensuring that fewer than B B B low lists are stored throughout the execution even when C 1 C_1 C 1 temporarily becomes larger. A flush handles the new candidates directly without first building their lists.
Flushing while preserving middle domination. Let C 1 0 C_1^0 C 1 0 be the set C 1 C_1 C 1 at the start of a flush. Remove every current member of M h i \mathcal{M}_{\mathrm{hi}} M hi from the MIS and clear the sampled high domination edge lists. Retain every current member of M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid in the MIS throughout the flush. Process the vertices of C 1 0 C_1^0 C 1 0 in a fixed order. If a vertex has no low-MIS neighbor, include it in M l o \mathcal{M}_{\mathrm{lo}} M lo ; otherwise it has a neighbor in M l o \mathcal{M}_{\mathrm{lo}} M lo and is removed from C 1 C_1 C 1 . Whenever a vertex joins M l o \mathcal{M}_{\mathrm{lo}} M lo , update low counters before processing the next vertex.
Every vertex of C 1 0 C_1^0 C 1 0 had zero middle count, and the middle MIS is unchanged during this pass. Hence including these low vertices in M l o \mathcal{M}_{\mathrm{lo}} M lo creates no conflict with M m i d \mathcal{M}_{\mathrm{mid}} M mid . At the end, every former member of C 1 0 C_1^0 C 1 0 is either in M l o \mathcal{M}_{\mathrm{lo}} M lo or dominated by it, and therefore leaves C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 . No new candidate is created, because no vertex is removed from M l o \mathcal{M}_{\mathrm{lo}} M lo .
Next process the middle degree vertices v v v in fixed order. If v v v is not in the MIS and both its low- and middle-MIS-neighbor counters are zero, include v v v in M m i d \mathcal{M}_{\mathrm{mid}} M mid and increment its neighbors’ middle counters. Complete these changes before processing the next vertex. After this pass, rebuild an MIS of
G [ V h i ∖ N ( M l o ∪ M m i d ) ] . G[V_{\mathrm{hi}} \setminus N(\mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}})]. G [ V hi ∖ N ( M lo ∪ M mid )] .
At this point C 1 C_1 C 1 is empty. No vertex is removed from M m i d \mathcal{M}_{\mathrm{mid}} M mid during the flush, so every vertex left in C 2 C_2 C 2 has a middle-MIS neighbor throughout the flush.
Amortizing a flush through the candidate union. Clearing and rebuilding the high layer costs O ~ ( m 3 / 4 ) \widetilde{O}(m^{3/4}) O ( m 3/4 ) : there are O ( m 3 / 8 ) O(m^{3/8}) O ( m 3/8 ) high vertices, and each vertex leaving or joining M h i \mathcal{M}_{\mathrm{hi}} M hi costs O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) , including witness maintenance. The potential increase from removals fits the same bound, so the total charge is
O ( ∣ V h i ∣ W h i ) = O ~ ( m 3 / 4 ) . O(|V_{\mathrm{hi} }|W_{\mathrm{hi}}) = \widetilde{O}(m^{3/4}). O ( ∣ V hi ∣ W hi ) = O ( m 3/4 ) .
Starting from an empty candidate union, the total number of times vertices join C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 over T T T edge updates is O ( T m 3 / 8 ) O(Tm^{3/8}) O ( T m 3/8 ) , counting a vertex again whenever it rejoins the union. Every flush removes at least B = m 1 / 2 B = m^{1/2} B = m 1/2 vertices from the union and creates no new candidates. Consequently, the total number of flushes is at most
O ( T m 3 / 8 B ) = O ( T m − 1 / 8 ) . O\left(\frac{Tm^{3/8}}{B}\right) = O(Tm^{-1/8}). O ( B T m 3/8 ) = O ( T m − 1/8 ) .
Their high-layer reconstruction cost per update is therefore
O ~ ( m − 1 / 8 ⋅ m 3 / 4 ) = O ~ ( m 5 / 8 ) . \widetilde{O}\left(m^{-1/8} \cdot m^{3/4}\right) = \widetilde{O}(m^{5/8}). O ( m − 1/8 ⋅ m 3/4 ) = O ( m 5/8 ) .
In other words, this bounds the total number of rebuilds; consecutive rebuilds need not be separated by many updates. Large transfers from C 2 C_2 C 2 to C 1 C_1 C 1 do not invalidate the bound because they create no new members of the union.
Equivalently, add α ∣ C 1 ∪ C 2 ∣ \alpha|C_1 \cup C_2| α ∣ C 1 ∪ C 2 ∣ to the potential, where α = Θ ~ ( m 1 / 4 ) \alpha= \widetilde{\Theta}(m^{1/4}) α = Θ ( m 1/4 ) . New entries increase this term by at most O ( m 3 / 8 ) α = O ~ ( m 5 / 8 ) O(m^{3/8})\alpha= \widetilde{O}(m^{5/8}) O ( m 3/8 ) α = O ( m 5/8 ) per update, while each flush decreases it by at least α B = Θ ~ ( m 3 / 4 ) \alpha B = \widetilde{\Theta}(m^{3/4}) α B = Θ ( m 3/4 ) , offsetting the reconstruction cost. Moving vertices between C 1 C_1 C 1 and C 2 C_2 C 2 leaves this potential unchanged.
These estimates explain the choice of B B B : initializing lists for fewer than B B B candidates costs O ~ ( B m 1 / 8 ) \widetilde{O}(Bm^{1/8}) O ( B m 1/8 ) , while charging rebuilds to candidate growth gives O ~ ( m 9 / 8 / B ) \widetilde{O}(m^{9/8}/B) O ( m 9/8 / B ) per update. Setting B = m 1 / 2 B=m^{1/2} B = m 1/2 balances these contributions at O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) .
Checkpoint: the full algorithmic structure. To summarize, the algorithm maintains an independent set across the low, middle, and high degree classes, with boundaries m 3 / 8 m^{3/8} m 3/8 and m 5 / 8 m^{5/8} m 5/8 . Exact counters record low- and middle-MIS neighbors at every vertex, and high-MIS neighbors at high vertices. For middle vertices and primary candidates in C 1 C_1 C 1 , sampled high domination edge lists A z h i A_z^{\mathrm{hi}} A z hi , together with the entry for each sampled edge ( z , x ) (z,x) ( z , x ) in R x h i R_x^{\mathrm{hi}} R x hi , maintain high-MIS witnesses using sampling probability ϕ = Θ ( m − 1 / 4 ) \phi=\Theta(m^{-1/4}) ϕ = Θ ( m − 1/4 ) . The secondary candidates in C 2 C_2 C 2 rely on their exact middle counters instead. After each completed update, a low vertex outside the MIS has a neighbor in M l o \mathcal{M}_{\mathrm{lo}} M lo , belongs to C 2 C_2 C 2 and has a neighbor in M m i d \mathcal{M}_{\mathrm{mid}} M mid , or belongs to C 1 C_1 C 1 and has a neighbor in M h i \mathcal{M}_{\mathrm{hi}} M hi .
Each edge update has a preparation phase followed by one of two ways to restore maximality:
(1) Prepare the update. Apply the edge insertion or deletion, and update the affected counters, membership in C 1 C_1 C 1 and C 2 C_2 C 2 , and stored witnesses. If an insertion joins two MIS vertices, remove the lower-priority endpoint from the MIS. Add requests to Q Q Q for vertices that may no longer be dominated, but initialize new high domination edge lists at low vertices only after the flush test of whether ∣ C 1 ∣ < B |C_1|<B ∣ C 1 ∣ < B .
(2a) Regular mode when ∣ C 1 ∣ < B = m 1 / 2 |C_1|<B=m^{1/2} ∣ C 1 ∣ < B = m 1/2 . Initialize the high domination edge lists of vertices which have newly joined C 1 C_1 C 1 , then process requests in Q Q Q in the fixed low–middle–high priority order. Discard requests for vertices already in the MIS or whose domination is confirmed by the exact counters or a stored domination edge. Include a low vertex in M l o \mathcal{M}_{\mathrm{lo}} M lo or a middle vertex in M m i d \mathcal{M}_{\mathrm{mid}} M mid only when its exact low and middle counters equal zero and its high domination edge list is empty, first removing all of its actual high-MIS neighbors from M h i \mathcal{M}_{\mathrm{hi}} M hi . Include a high vertex in M h i \mathcal{M}_{\mathrm{hi}} M hi only when all its exact counters equal zero. Update counters and witnesses after each change and process the resulting requests until Q Q Q is empty.
(2b) Flush mode when ∣ C 1 ∣ ≥ B |C_1|\ge B ∣ C 1 ∣ ≥ B . Let C 1 0 C_1^0 C 1 0 be the set C 1 C_1 C 1 at the start of the flush. Before initializing any missing high domination edge lists at low vertices or extracting requests, remove every vertex of M h i \mathcal{M}_{\mathrm{hi}} M hi from the MIS. Every current member of M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}}\cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid remains in the MIS throughout the flush. Greedily process C 1 0 C_1^0 C 1 0 so that each vertex joins the low MIS or has a low-MIS neighbor. Next process the middle degree vertices v v v in fixed order: if v v v is not in the MIS and both its low and middle counters are zero, include v v v in M m i d \mathcal{M}_{\mathrm{mid}} M mid , then increment its neighbors’ middle counters before processing the next vertex. Finally, rebuild the high MIS on the high vertices with no low- or middle-MIS neighbor. This branch ends with C 1 = Q = ∅ C_1=Q=\varnothing C 1 = Q = ∅ . No vertex is removed from M m i d \mathcal{M}_{\mathrm{mid}} M mid during the flush, so every vertex remaining in C 2 C_2 C 2 has a middle-MIS neighbor throughout the flush.
The threshold is tested only once, after preparation. Regular mode can only remove vertices from C 1 C_1 C 1 , while flush mode makes C 1 C_1 C 1 empty. Both modes finish with an MIS, whose membership changes are then reported.
The potential function. We analyze the running time of this algorithm using the potential function
Φ = W l o ∣ V l o ∖ M ∣ + W m i d ∣ V m i d ∖ M ∣ + W h i ∣ V h i ∖ M ∣ + α ∣ C 1 ∪ C 2 ∣ + β ∣ C 1 ∣ + Θ ( log n ) ∣ Q ∣ , \Phi= W_{\mathrm{lo}}|V_{\mathrm{lo}}\setminus\mathcal{M}| + W_{\mathrm{mid}}|V_{\mathrm{mid}}\setminus\mathcal{M}| + W_{\mathrm{hi}}|V_{\mathrm{hi}}\setminus\mathcal{M}|
+ \alpha|C_1\cup C_2| + \beta|C_1| + \Theta(\log n)|Q|, Φ = W lo ∣ V lo ∖ M ∣ + W mid ∣ V mid ∖ M ∣ + W hi ∣ V hi ∖ M ∣ + α ∣ C 1 ∪ C 2 ∣ + β ∣ C 1 ∣ + Θ ( log n ) ∣ Q ∣ ,
with
W l o = W m i d = Θ ~ ( m 5 / 8 ) , W h i = Θ ~ ( m 3 / 8 ) , W_{\mathrm{lo}} = W_{\mathrm{mid}} = \widetilde{\Theta}(m^{5/8}), \qquad W_{\mathrm{hi}} = \widetilde{\Theta}(m^{3/8}), W lo = W mid = Θ ( m 5/8 ) , W hi = Θ ( m 3/8 ) ,
α = Θ ~ ( m 1 / 4 ) , β = Θ ~ ( m 1 / 8 ) . \alpha= \widetilde{\Theta}(m^{1/4}), \qquad\beta= \widetilde{\Theta}(m^{1/8}). α = Θ ( m 1/4 ) , β = Θ ( m 1/8 ) .
Including a vertex in the MIS while processing the queue decreases one of the first three terms enough to pay for its neighborhood scan and any conflicting high-MIS removals. If including the vertex in the MIS also removes low vertices from C 1 C_1 C 1 , the resulting decrease in β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ pays for deleting their high domination edge lists. A flush uses the same vertex weights to pay for including low and middle vertices in the MIS, while the decrease in α ∣ C 1 ∪ C 2 ∣ \alpha|C_1 \cup C_2| α ∣ C 1 ∪ C 2 ∣ covers clearing and rebuilding the high layer.
The queue term covers requests discarded without a change in MIS membership. Increasing the potential by Θ ( log n ) \Theta(\log n) Θ ( log n ) when a request is issued pays for its later extraction and domination tests, even when no vertex potential decreases.
The flush test also bounds the cost of vertices entering C 1 C_1 C 1 . If ∣ C 1 ∣ < B |C_1| < B ∣ C 1 ∣ < B , the time to initialize their missing lists plus the increase in β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ is at most O ~ ( B m 1 / 8 ) = O ~ ( m 5 / 8 ) \widetilde{O}(Bm^{1/8}) = \widetilde{O}(m^{5/8}) O ( B m 1/8 ) = O ( m 5/8 ) ; the potential then pays for the queue repairs. Otherwise, the flush empties C 1 C_1 C 1 and cancels any increase in this term earlier in the update, with its other costs covered by the vertex weights and the candidate-union decrease. Thus even when many vertices move from C 2 C_2 C 2 to C 1 C_1 C 1 , their total amortized cost is O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) . Together with the O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) running time and vertex-potential increase for the edge change and any forced MIS removal, these bounds give O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) amortized time for the entire update. Initially M = V \mathcal{M} = V M = V and C 1 = C 2 = Q = ∅ C_1 = C_2 = Q = \varnothing C 1 = C 2 = Q = ∅ , so Φ = 0 \Phi= 0 Φ = 0 . Since Φ \Phi Φ is nonnegative, summing the actual running time plus the potential change over all updates bounds the total running time.
This analysis requires small sampled lists and the guarantee that an empty high domination edge list implies few actual high-MIS neighbors. The reported MISs reveal information about these samples, so ordinary independent-sampling estimates do not yet justify the bounds. We next show why both guarantees hold against an adaptive adversary.
Membership Query Probabilistic Game
How an adversary could enlarge a reverse list. We first show that a high vertex’s reverse list remains small throughout its stay in the MIS. The difficulty is that observations of the MIS may reveal which incident edges were sampled and let the adversary influence which sampled edges remain in the reverse list. Fix a high vertex z z z , and follow R z h i R_z^{\mathrm{hi}} R z hi from its entry into M h i \mathcal{M}_{\mathrm{hi}} M hi until its next departure. To see how too much information could enlarge this list, model the edges from z z z to vertices whose high domination edge lists are stored as a set U U U , with ∣ U ∣ ≤ K |U| \le K ∣ U ∣ ≤ K , and the sampled edges as a subset S ⊆ U S \subseteq U S ⊆ U . Each new element receives an independent Bernoulli bit with success probability p p p . When the fixed universe has the maximum allowed size, the expected value of ∣ S ∣ |S| ∣ S ∣ is p K pK p K .
If the adversary sees every sampling bit, it can delete each element outside S S S and replace it with a fresh element, while keeping every element in S S S . After Θ ( K / p ) \Theta(K/p) Θ ( K / p ) insertion attempts in expectation, it can fill all K K K positions with sampled elements. Thus ∣ S ∣ |S| ∣ S ∣ can reach K K K , a factor 1 / p 1/p 1/ p larger than its fixed-set expectation. Independence of the bits when they are first generated does not prevent this attack: the set U U U has been chosen using those bits.
The attack above relies on a crucial ability: the adversary must identify nonsampled edges while keeping z z z in the MIS, so that it can repeatedly replace them and accumulate sampled edges in R z h i R_z^{\mathrm{hi}} R z hi . This is where observing the MIS differs from seeing the sampling bits directly. Our key observation is that, when the MIS reveals that an edge ( z , v ) (z,v) ( z , v ) was not sampled, the same event can cause v v v to enter the MIS and z z z to leave it. The adversary then loses R z h i R_z^{\mathrm{hi}} R z hi , rather than gaining another opportunity to alter its contents. To turn this observation into a size bound, we must characterize exactly which membership answers the MIS can reveal while z z z remains in M h i \mathcal{M}_{\mathrm{hi}} M hi .
The membership-query game. We formalize the information available to an adaptive player as the following game, played in discrete steps.
Universe and sample. Initially, the universe is empty; thereafter it is a set U U U with ∣ U ∣ ≤ K |U| \le K ∣ U ∣ ≤ K . Each newly inserted element e e e receives a hidden, independent bit X e ∼ Bernoulli ( p ) X_e \sim\operatorname{Bernoulli}(p) X e ∼ Bernoulli ( p ) , where p < 1 / 2 p < 1/2 p < 1/2 , and S = { e ∈ U ∣ X e = 1 } S = \{e \in U \mid X_e = 1\} S = { e ∈ U ∣ X e = 1 } is the sampled subset of U U U . Both U U U and S S S refer to the current step of the game.
Updates. The player may insert a fresh element into U U U or delete an element e ∈ U e \in U e ∈ U from U U U and S S S . A deletion reveals X e X_e X e and discards it; every later insertion, including one with the same name, receives a fresh independent bit.
Membership query. The player may choose an element e ∈ U e \in U e ∈ U and ask whether e ∈ S e \in S e ∈ S . The answer reveals X e X_e X e .
Termination. If a membership query returns yes, the game continues. The first no answer terminates the game immediately. Before termination, the player may choose each operation adaptively from the revealed history.
This restriction prevents the attack above. The player cannot test an element e ∈ U e \in U e ∈ U , discover that e ∉ S e \notin S e ∈ / S , and replace it while continuing the game. For any q q q , the probability that membership queries on q q q distinct elements all return yes before termination is at most p q p^q p q . Consequently, only O ( log n ) O(\log n) O ( log n ) distinct elements have been identified as sampled by membership queries, with high probability. Deletion operations may reveal additional bits equal to one, but their elements immediately leave the sample and cannot return with those bits. Thus, before termination, only O ( log n ) O(\log n) O ( log n ) elements e ∈ U e \in U e ∈ U have revealed bits X e = 1 X_e = 1 X e = 1 . Conditional on the history, the unrevealed bits of elements in U U U are mutually independent Bernoulli-p p p random variables. Concentration therefore gives
∣ S ∣ = O ( p K + log n ) = O ~ ( 1 + p K ) |S| = O(pK + \log n) = \widetilde{O}(1 + pK) ∣ S ∣ = O ( p K + log n ) = O ( 1 + p K )
simultaneously over a polynomial number of operations. The terminating query does not change S S S , so the bound also holds after that query. Lemma 3.2 formalizes this argument.
Why the algorithm removes the high vertex after a no answer. Before including a low or middle vertex v v v in the MIS, the algorithm removes every neighbor of v v v in M h i \mathcal{M}_{\mathrm{hi}} M hi , including z z z , from the MIS. Thus, when the decision to include v v v depends only on whether ( z , v ) (z,v) ( z , v ) was sampled, a no answer establishes that v v v has no sampled witness. The algorithm then removes z z z from M h i \mathcal{M}_{\mathrm{hi}} M hi before including v v v in the MIS, ending the game for R z h i R_z^{\mathrm{hi}} R z hi . A yes answer establishes that v v v is dominated; the algorithm keeps z z z in M h i \mathcal{M}_{\mathrm{hi}} M hi and leaves v v v outside the MIS. This is precisely the stopping rule of the membership game.
To apply the game, let U U U contain the graph edges from z z z to vertices whose high domination edge lists are stored, and let S S S be its reverse list:
U = { ( z , v ) ∈ E ( G ) : A v h i is stored } , S = R z h i . U = \{(z,v) \in E(G) : A_v^{\mathrm{hi}}\text{ is stored}\}, \qquad S = R_z^{\mathrm{hi}}. U = {( z , v ) ∈ E ( G ) : A v hi is stored } , S = R z hi .
Fix the adversary’s internal randomness and all sampling coins except those defining R z h i R_z^{\mathrm{hi}} R z hi . Simulate the algorithm and adversary while keeping these excluded coins hidden. The same coin determines whether ( z , v ) (z,v) ( z , v ) appears in R z h i R^{\mathrm{hi}}_z R z hi and A v h i A^{\mathrm{hi}}_v A v hi , so the simulator cannot inspect the copy in A v h i A^{\mathrm{hi}}_v A v hi separately. The simulator can decide whether to include v v v in the MIS without inspecting ( z , v ) (z,v) ( z , v ) whenever MIS membership, exact counters, or other sampled witnesses already settle that decision. It needs a membership query only when this one bit determines whether v v v enters the MIS. Inserting a graph edge ( z , v ) (z,v) ( z , v ) while A v h i A^{\mathrm{hi}}_v A v hi is stored, or initializing A v h i A^{\mathrm{hi}}_v A v hi at a neighbor of z z z , uses the game’s insertion operation. Deleting that edge or discarding A v h i A^{\mathrm{hi}}_v A v hi uses its reveal-and-delete operation. For an edge ( z , v ) (z,v) ( z , v ) still in U U U , the simulator must defer the membership query until v v v is extracted from the queue.
Querying while issuing a request would be too early: after a no answer, the algorithm would only queue v v v , while z z z could remain in the MIS. The simulator therefore queues v v v without inspecting the hidden bit and postpones the query until extraction. Every vertex outside the MIS with no positive maintained MIS-neighbor counter and no nonempty stored high domination edge list is already in the real queue before extraction. A request present only in the simulation must therefore find its vertex already in the MIS or certified as dominated by a counter or stored witness, so processing it changes only the simulated queue. Using the same fixed priority order therefore preserves all MIS changes and reported outputs. This lets the simulator defer each membership query until a no answer is followed by the algorithm removing z z z from M h i \mathcal{M}_{\mathrm{hi}} M hi . The full simulation is proved in Lemma 4.7; Figure 3 shows its interface.
Figure 3. Simulation interface for the reverse list R z h i R^{\mathrm{hi}}_z R z hi . The simulator runs the adaptive adversary and the MIS data structure with the adversary’s internal randomness and all sampling coins except those defining R z h i R^{\mathrm{hi}}_z R z hi fixed. It changes U U U and learns about S S S only through the membership game’s permitted operations and answers.
The resulting reverse-list bound. The membership game gives the O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) reverse-list bound needed for efficient high-MIS removals, even under adaptive updates. Indeed, a reverse list samples edges to O ( m 5 / 8 ) O(m^{5/8}) O ( m 5/8 ) middle vertices and fewer than B = m 1 / 2 B=m^{1/2} B = m 1/2 low vertices with stored lists. Its universe therefore has capacity K = O ( m 5 / 8 ) K=O(m^{5/8}) K = O ( m 5/8 ) , and the game gives
∣ R z h i ∣ = O ~ ( 1 + p h i K ) = O ~ ( m − 1 / 4 m 5 / 8 ) = O ~ ( m 3 / 8 ) \lvert R^{\mathrm{hi}}_z\rvert=\widetilde{O}(1+p_{\mathrm{hi}}K)=\widetilde{O}(m^{-1/4}m^{5/8})=\widetilde{O}(m^{3/8}) ∣ R z hi ∣ = O ( 1 + p hi K ) = O ( m − 1/4 m 5/8 ) = O ( m 3/8 )
with high probability throughout the execution. Together with the O ( m 3 / 8 ) O(m^{3/8}) O ( m 3/8 ) bound on the number of high degree neighbors, this ensures that removing a vertex from M h i \mathcal{M}_{\mathrm{hi}} M hi and finding the resulting requests takes only O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) time.
Emptiness Query Probabilistic Game
Modeling a high domination edge list. To make including a low vertex in the MIS affordable, an empty sampled list must imply that the vertex has few actual high-MIS neighbors. Fix a low candidate v ∈ C 1 v \in C_1 v ∈ C 1 whose high domination edge list is stored, and follow that list until it is discarded. Let
U = { ( x , v ) : x ∈ N ( v ) ∩ M h i } , S = A v h i ⊆ U . U = \{(x,v): x \in N(v) \cap M_{\mathrm{hi}}\}, \qquad S = A^{\mathrm{hi}}_v \subseteq U. U = {( x , v ) : x ∈ N ( v ) ∩ M hi } , S = A v hi ⊆ U .
Then ∣ U ∣ |U| ∣ U ∣ counts exactly the high-MIS neighbors that must be removed before including v v v in the MIS. With p = p h i = Θ ( m − 1 / 4 ) p = p_{\mathrm{hi}} = \Theta(m^{-1/4}) p = p hi = Θ ( m − 1/4 ) , our goal is
S = ∅ ⟹ ∣ U ∣ = O ~ ( p − 1 ) = O ~ ( m 1 / 4 ) . S = \varnothing\quad\Longrightarrow\quad|U| = \widetilde{O}(p^{-1}) = \widetilde{O}(m^{1/4}). S = ∅ ⟹ ∣ U ∣ = O ( p − 1 ) = O ( m 1/4 ) .
For a fixed universe, the probability of missing every edge is ( 1 − p ) ∣ U ∣ ≤ e − p ∣ U ∣ (1-p)^{|U|} \le e^{-p|U|} ( 1 − p ) ∣ U ∣ ≤ e − p ∣ U ∣ , which gives this implication with high probability. We must prove the same implication when observations of the MIS reveal whether the list is empty and guide the adversary’s later updates.
Why unrestricted emptiness queries are too powerful. Suppose the player may continue after either answer to an emptiness query. Starting from U = S = ∅ U = S = \varnothing U = S = ∅ , it inserts one fresh element e e e and asks whether S S S is empty. If the answer is nonempty, then e e e must be sampled, so the player deletes e e e . If the answer is empty, then e e e is not sampled, so the player keeps it in U U U . In either case S S S is empty again at the end of the round, and every element left in U U U is known to be unsampled. Repeating the procedure therefore reveals the sampling bit of each new element using only emptiness queries. The player can accumulate arbitrarily many unsampled elements while keeping S S S empty after every round. Consequently, unrestricted access to emptiness answers cannot justify the claimed bound on the universe size when the sample is empty.
The emptiness-query game. We will simulate the algorithm so that it queries a list’s emptiness only when its vertex is being processed, is outside the MIS, and has no domination certified by the exact counters. At that point, an empty answer establishes that the vertex has no sampled high-MIS witness. The algorithm then removes all its neighbors in M h i M_{\mathrm{hi}} M hi from the MIS before including the vertex in the MIS. The universe of possible high witnesses becomes empty, ending the current game. This motivates the following stopping rule, which prevents the repeated empty queries used in the attack above.
Universe and sample. The game begins with U = S = ∅ U = S = \varnothing U = S = ∅ . Each newly inserted element receives a hidden, independent Bernoulli-p p p bit, and S S S consists of the elements in U U U whose bits equal one.
Updates. The player may insert a fresh element into U U U or delete an element e ∈ U e \in U e ∈ U from U U U and S S S . Deletion reveals no bit, and every later insertion, including one with the same name, receives a fresh independent bit.
Emptiness query. The player may ask whether S S S is empty. The answer reveals only whether S = ∅ S = \varnothing S = ∅ and is the only information about the hidden bits.
Termination. A nonempty answer allows the game to continue. The first empty answer ends the game immediately. Operations may depend on the preceding answers.
In the attack above, the first query that identifies an unsampled element now ends the game, preventing its repeated use to build a large unsampled universe.
Why the stopping rule gives the required bound. Before the game stops, every query has the same answer: nonempty. Thus, once the player’s randomness is fixed, there is only one continuing sequence of operations, and the set U U U at each step of that sequence is fixed. Reaching a step requires certain earlier sets to contain sampled elements. These requirements favor sampling bits equal to one, whereas an empty current sample requires X e = 0 X_e = 0 X e = 0 for every e ∈ U e \in U e ∈ U . For a step reached with positive probability, the event H H H that it is reached is increasing in the sampling bits, while the event E E E that its sample is empty is decreasing. Harris’s inequality therefore gives
Pr [ E ∣ H ] ≤ Pr [ E ] = ( 1 − p ) ∣ U ∣ ≤ e − p ∣ U ∣ , \Pr[E \mid H] \le\Pr[E] = (1-p)^{|U|} \le e^{-p|U|}, Pr [ E ∣ H ] ≤ Pr [ E ] = ( 1 − p ) ∣ U ∣ ≤ e − p ∣ U ∣ ,
whether or not the player queries S S S at this step. A union bound over polynomially many steps shows that, with high probability, after every update or query, S = ∅ S = \varnothing S = ∅ implies ∣ U ∣ = O ~ ( p − 1 ) |U| = \widetilde{O}(p^{-1}) ∣ U ∣ = O ( p − 1 ) .
The sample-size bound uses the same fixed sequence. For each fixed universe on that sequence, the sampling bits are independent before conditioning on the event that its step is reached. Ordinary Chernoff concentration therefore gives ∣ S ∣ = O ~ ( 1 + p ∣ U ∣ ) |S| = \widetilde{O}(1+p|U|) ∣ S ∣ = O ( 1 + p ∣ U ∣ ) before this conditioning. Reaching the step may bias the bits, but a reached step with an oversized sample is still contained in the corresponding fixed-set failure event. A union bound therefore also bounds the sample size throughout the game. Lemma 3.5 gives the formal argument.
To apply this game, fix the adversary’s internal randomness and all sampling coins except those defining A v h i A_v^{\mathrm{hi}} A v hi . The simulator must reproduce the MIS outputs using only emptiness answers about A v h i A_v^{\mathrm{hi}} A v hi . In particular, deleting a potential witness must not reveal whether its edge was sampled. We keep the entries of A v h i A_v^{\mathrm{hi}} A v hi and the corresponding entries in the lists R x h i R_x^{\mathrm{hi}} R x hi at its high-MIS neighbors hidden and allow extra requests for v v v , so that the simulator can arrange to reconsider v v v without inspecting individual sampling bits. Figure 4 depicts the permitted information.
Figure 4. Simulation interface for the high domination edge list A v h i A_v^{\mathrm{hi}} A v hi . The simulator runs the adaptive adversary and the MIS data structure with the adversary’s internal randomness and all sampling coins except those defining A v h i A_v^{\mathrm{hi}} A v hi fixed. Updates reveal no sampling bits. An emptiness query reveals only whether S S S is empty, and the first empty answer ends the game.
Deferring a query until the request is processed. As in the membership simulation, whenever the real algorithm would test A v h i A_v^{\mathrm{hi}} A v hi before queuing v v v , the simulator checks v ∉ M v \notin\mathcal{M} v ∈ / M and d l o ( v ) = d m i d ( v ) = 0 d_{\mathrm{lo}}(v) = d_{\mathrm{mid}}(v) = 0 d lo ( v ) = d mid ( v ) = 0 . If both conditions hold, it queues v v v without querying the list and postpones the emptiness query until extraction. The same queue argument applies: any request absent from the real queue is rejected by the repair checks, and the fixed priority order preserves the sequence of vertices joining the MIS and hence all reported outputs.
At extraction, the simulator discards the request if v ∈ M v \in\mathcal{M} v ∈ M or d l o ( v ) + d m i d ( v ) > 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) > 0 d lo ( v ) + d mid ( v ) > 0 . Otherwise, it asks whether A v h i A_v^{\mathrm{hi}} A v hi is empty. A nonempty answer establishes that v v v is dominated. On an empty answer, the algorithm removes all of v v v ’s neighbors in M h i \mathcal{M}_{\mathrm{hi}} M hi from the MIS and then includes v v v in the MIS. Thus every queried empty answer ends the game, as required. For a low vertex, discarding its list also ends the game, and a later list starts with fresh samples. Lemma 4.8 gives the full simulation argument.
The high domination edge list of a middle vertex. The same argument applies to middle vertices: including a middle vertex in the MIS removes all its high-MIS neighbors, so both U U U and S S S are empty. The algorithm does not delete the list object A v h i A_{v}^{\mathrm{hi}} A v hi or change its pointer, but the list contains no edges and all its sampling bits have been discarded. A new game therefore starts with an empty universe and an empty sample; every insertion uses a fresh independent bit. A flush creates the same reset by clearing the high MIS. Applying the game bound between successive resets, starting at list initialization, covers the entire period during which the middle vertex’s list is stored.
The emptiness game supplies both remaining estimates needed to include low and middle vertices in the MIS at low cost. Since each list samples edges to at most ∣ V h i ∣ = O ( m 3 / 8 ) |V_{\mathrm{hi}}| = O(m^{3/8}) ∣ V hi ∣ = O ( m 3/8 ) high vertices, the following bounds hold while the list is stored:
∣ A v h i ∣ = O ~ ( 1 + p h i ∣ V h i ∣ ) = O ~ ( m 1 / 8 ) , A v h i = ∅ ⟹ ∣ N ( v ) ∩ M h i ∣ = O ~ ( m 1 / 4 ) . |A_{v}^{\mathrm{hi}}| = \widetilde{O}(1 + p_{\mathrm{hi}}|V_{\mathrm{hi}}|) = \widetilde{O}(m^{1/8}), \qquad A_{v}^{\mathrm{hi}} = \varnothing\implies|N(v) \cap\mathcal{M}_{\mathrm{hi}}| = \widetilde{O}(m^{1/4}). ∣ A v hi ∣ = O ( 1 + p hi ∣ V hi ∣ ) = O ( m 1/8 ) , A v hi = ∅ ⟹ ∣ N ( v ) ∩ M hi ∣ = O ( m 1/4 ) .
The first estimate bounds the cost of deleting a candidate’s stored list. The second ensures that at most O ~ ( m 1 / 4 ) \widetilde{O}(m^{1/4}) O ( m 1/4 ) high-MIS neighbors need to leave before v v v joins the MIS. Each such removal costs O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) by the reverse-list bound, so all conflicts together cost O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) . These are precisely the sampling guarantees used in the amortized analysis above.
Preliminaries
Output-sensitive independent sampling. We repeatedly sample elements of an indexed set independently with probability p p p . Generating one sampling bit per element would make the running time depend on the size of the input set. The following standard geometric-skipping procedure makes the running time depend only on the number of selected elements, up to logarithmic factors.
An indexed set is a set S S S of size at most n n n equipped with an arbitrary order and supporting size ( S ) \operatorname{size}(S) size ( S ) , insertion, deletion, and select ( S , i ) \operatorname{select}(S,i) select ( S , i ) , which returns the i i i -th element in the current order. A balanced binary search tree augmented with subtree sizes supports all these operations in O ( log n ) O(\log n) O ( log n ) time.
For p ∈ ( 0 , 1 ] p \in(0,1] p ∈ ( 0 , 1 ] , let Geo ( p ) \operatorname{Geo}(p) Geo ( p ) denote a geometric random variable counting the number of failures before the next success:
Pr [ Geo ( p ) = k ] = ( 1 − p ) k p , k = 0 , 1 , 2 , … . \Pr[\operatorname{Geo}(p)=k] = (1-p)^k p,\qquad k=0,1,2,\ldots. Pr [ Geo ( p ) = k ] = ( 1 − p ) k p , k = 0 , 1 , 2 , … .
It can be generated in O ~ ( 1 ) \widetilde{O}(1) O ( 1 ) time from independent random bits, for example by inverse transform, to the O ( log n ) O(\log n) O ( log n ) bits of precision needed to distinguish positions in a set of polynomial size.
Algorithm 1: BernoulliSample(S, p)
Input: An indexed set S and a probability p ∈ (0, 1]
Output: A subset T ⊆ S
1 T ← ∅, i ← 0
2 while i < size(S) do
3 g ← Geo(p), i ← i + g + 1
4 if i ≤ size(S) then
5 T ← T ∪ {select(S, i)}
6 return T
Lemma 3.1 (Bernoulli sampling). For any fixed indexed set S S S and p ∈ ( 0 , 1 ] p \in(0,1] p ∈ ( 0 , 1 ] , BernoulliSample( S , p ) (S,p) ( S , p ) includes each element of S S S independently with probability p p p . If the returned set has size s s s , the running time is O ~ ( 1 + s ) \widetilde{O}(1+s) O ( 1 + s ) .
Proof. Consider a sequence of independent zero–one random variables, each equal to one with probability p p p . The number of zeros before its first one has the distribution Geo ( p ) \operatorname{Geo}(p) Geo ( p ) . After that one, the number of zeros before the next one is a fresh independent copy of Geo ( p ) \operatorname{Geo}(p) Geo ( p ) , and so on. Consequently, the successive values
i 1 = g 1 + 1 , i 2 = i 1 + g 2 + 1 , … i_1 = g_1 + 1,\qquad i_2 = i_1 + g_2 + 1,\qquad\ldots i 1 = g 1 + 1 , i 2 = i 1 + g 2 + 1 , …
generated by Algorithm 1 are exactly the positions of the ones in the independent coin sequence. Hence each element is selected independently with probability p p p .
The procedure generates one geometric value and makes at most one call to select ( S , i ) \operatorname{select}(S,i) select ( S , i ) for every returned element, with at most one additional geometric value that jumps beyond the end of S S S . Its time is therefore O ~ ( 1 + s ) \widetilde{O}(1+s) O ( 1 + s ) . □ \square □
Probabilistic games. We use two probabilistic game lemmas to capture robustness against adaptive adversaries. The first bounds the size of a hidden sample under membership queries. The second uses emptiness queries to bound both the sample size throughout the game and the universe size whenever the sample is empty. In either game, one step consists of one permitted update or query. In our applications, a single edge update of the graph may generate several game steps.
Lemma 3.2. Fix p ∈ ( 0 , 1 / 2 ) p \in(0,1/2) p ∈ ( 0 , 1/2 ) , integers k ≥ 2 k \ge2 k ≥ 2 and M ≥ 1 M \ge1 M ≥ 1 , and a failure probability η ∈ ( 0 , 1 ) \eta\in(0,1) η ∈ ( 0 , 1 ) . A player takes at most M M M steps in the following game.
Universe and sample. The set U U U starts empty and always satisfies ∣ U ∣ ≤ k |U| \le k ∣ U ∣ ≤ k . Each new element e e e receives a hidden, independent bit X e ∼ Bernoulli ( p ) X_e \sim\operatorname{Bernoulli}(p) X e ∼ Bernoulli ( p ) , and the sampled subset of U U U is S = { e ∈ U : X e = 1 } S = \{e \in U : X_e = 1\} S = { e ∈ U : X e = 1 } .
Updates. The player may insert a fresh element into U U U or reveal and delete an element e ∈ U e \in U e ∈ U : this reveals X e X_e X e , removes e e e from U U U and S S S , and discards X e X_e X e . Every later insertion, including one with the same name, creates a new element with a fresh independent bit.
Membership query. The player may choose an element e ∈ U e \in U e ∈ U and ask whether it belongs to S S S . The answer reveals X e X_e X e ; repeated queries of the same element are allowed while it belongs to U U U .
Termination. A yes answer lets the game continue; the first no answer ends it immediately. The player may choose each operation adaptively from all preceding query answers and deletion revelations.
Then, with probability at least 1 − η 1-\eta 1 − η , simultaneously after every update or query, including the query that terminates the game,
∣ S ∣ = O ( p k + log M + 1 η ) . |S| = O\left(pk + \log\frac{M+1}{\eta}\right). ∣ S ∣ = O ( p k + log η M + 1 ) . Proof. Fix the player’s internal randomness and assign the independent bit X e X_e X e on insertion of each element e e e . Let R R R be the set of elements for which a membership query has returned yes. Querying an element already in R R R reveals no new bit. A reveal-and-delete operation may reveal a bit, but it immediately deletes the corresponding element from U U U and S S S . The deleted element cannot be queried again, and its bit is never used in a later insertion.
Consider the first membership query to an element outside R R R . Conditional on the entire preceding history, including the outcomes of all reveal-and-delete operations, the queried element has an unrevealed Bernoulli ( p ) \operatorname{Bernoulli}(p) Bernoulli ( p ) bit. Indeed, an element whose bit was revealed by a reveal-and-delete operation is no longer available. It follows inductively that
Pr [ membership queries on at least q distinct elements return yes ] ≤ p q . \Pr[\text{membership queries on at least }q\text{ distinct elements return yes}] \le p^q. Pr [ membership queries on at least q distinct elements return yes ] ≤ p q . Since p < 1 / 2 p < 1/2 p < 1/2 , this bound implies that, except with probability at most η / 2 \eta/2 η /2 , only O ( log ( 1 / η ) ) O(\log(1/\eta)) O ( log ( 1/ η )) distinct elements ever receive a yes answer to their first membership query. In particular, ∣ S ∩ R ∣ ≤ ∣ R ∣ = O ( log ( 1 / η ) ) |S \cap R| \le|R| = O(\log(1/\eta)) ∣ S ∩ R ∣ ≤ ∣ R ∣ = O ( log ( 1/ η )) after every update or query.
Fix a step reached before termination and condition on all preceding operations and revealed answers. This history fixes U U U and R R R . Every revealed bit belongs to an element in R R R or to a deleted element. Consequently, conditional on this history, the bits of the elements in U ∖ R U \setminus R U ∖ R remain mutually independent Bernoulli variables with parameter p p p . Hence
Y : = ∣ S ∩ ( U ∖ R ) ∣ ∼ Bin ( ∣ U ∖ R ∣ , p ) , E [ Y ] ≤ p k . Y := |S \cap(U \setminus R)| \sim\operatorname{Bin}(|U \setminus R|,p), \qquad\mathbb{E}[Y] \le pk. Y := ∣ S ∩ ( U ∖ R ) ∣ ∼ Bin ( ∣ U ∖ R ∣ , p ) , E [ Y ] ≤ p k . For a binomial variable Z Z Z with mean μ \mu μ , we use the Chernoff bound
Pr [ Z > 2 μ + t ] ≤ e − t ( t ≥ 0 ) . \Pr[Z > 2\mu+ t] \le e^{-t} \qquad(t \ge0). Pr [ Z > 2 μ + t ] ≤ e − t ( t ≥ 0 ) .
Put λ = log ( 2 ( M + 1 ) / η ) \lambda= \log(2(M + 1)/\eta) λ = log ( 2 ( M + 1 ) / η ) . Applying this bound conditional on the preceding history gives
Pr [ Y > 2 p k + λ ∣ the preceding history ] ≤ e − λ . \Pr[Y > 2pk + \lambda\mid\text{the preceding history}] \le e^{-\lambda}. Pr [ Y > 2 p k + λ ∣ the preceding history ] ≤ e − λ .
Averaging over the history and taking a union bound over all steps shows that this bound fails before termination with probability at most ( M + 1 ) e − λ = η / 2 (M + 1)e^{-\lambda} = \eta/2 ( M + 1 ) e − λ = η /2 .
When both bounds hold, at every step before termination we have
∣ S ∣ = ∣ S ∩ R ∣ + ∣ S ∩ ( U ∖ R ) ∣ ≤ ∣ R ∣ + Y = O ( p k + log M + 1 η ) . |S| = |S \cap R| + |S \cap(U \setminus R)| \le|R| + Y = O\left(pk + \log\frac{M + 1}{\eta}\right). ∣ S ∣ = ∣ S ∩ R ∣ + ∣ S ∩ ( U ∖ R ) ∣ ≤ ∣ R ∣ + Y = O ( p k + log η M + 1 ) .
A terminating no answer does not change S S S , so the same estimate holds after that query. The union of the two failure events has probability at most η \eta η . Averaging over the fixed internal randomness proves the result for a randomized player as well.
Definition 3.3 (Increasing and decreasing events). For two binary vectors x , y ∈ { 0 , 1 } m x,y \in\{0,1\}^{m} x , y ∈ { 0 , 1 } m , write x ≤ y x \le y x ≤ y if x i ≤ y i x_i \le y_i x i ≤ y i for every i i i . Thus, y y y can be obtained from x x x by changing some zeroes into ones. An event E ⊆ { 0 , 1 } m \mathcal{E} \subseteq\{0,1\}^{m} E ⊆ { 0 , 1 } m is increasing if
x ∈ E and x ≤ y ⟹ y ∈ E ; x \in\mathcal{E} \text{ and } x \le y \quad\Longrightarrow\quad y \in\mathcal{E}; x ∈ E and x ≤ y ⟹ y ∈ E ; once an increasing event holds, changing zeroes into ones cannot make it fail. An event D \mathcal{D} D is decreasing if
x ∈ D and y ≤ x ⟹ y ∈ D ; x \in\mathcal{D} \text{ and } y \le x \quad\Longrightarrow\quad y \in\mathcal{D}; x ∈ D and y ≤ x ⟹ y ∈ D ; once a decreasing event holds, changing ones into zeroes cannot make it fail.
Lemma 3.4 (Harris’s inequality). Let X 1 , … , X m X_1,\ldots,X_m X 1 , … , X m be independent Bernoulli random variables . If E 1 \mathcal{E}_1 E 1 and E 2 \mathcal{E}_2 E 2 are increasing events , then
Pr [ E 1 ∩ E 2 ] ≥ Pr [ E 1 ] Pr [ E 2 ] . \Pr[\mathcal{E}_1 \cap\mathcal{E}_2] \ge\Pr[\mathcal{E}_1]\Pr[\mathcal{E}_2]. Pr [ E 1 ∩ E 2 ] ≥ Pr [ E 1 ] Pr [ E 2 ] . Equivalently, if E \mathcal{E} E is increasing and D \mathcal{D} D is decreasing, then
Pr [ E ∩ D ] ≤ Pr [ E ] Pr [ D ] . \Pr[\mathcal{E} \cap\mathcal{D}] \le\Pr[\mathcal{E}]\Pr[\mathcal{D}]. Pr [ E ∩ D ] ≤ Pr [ E ] Pr [ D ] .
The second game provides two guarantees using only emptiness queries.
Lemma 3.5. Fix p ∈ ( 0 , 1 ] p \in(0,1] p ∈ ( 0 , 1 ] , integers k ≥ 1 k \ge1 k ≥ 1 and M ≥ 1 M \ge1 M ≥ 1 , and a failure probability η ∈ ( 0 , 1 ) \eta\in(0,1) η ∈ ( 0 , 1 ) . A player takes at most M M M steps in the following game.
Universe and sample. The set U U U starts empty and always satisfies ∣ U ∣ ≤ k |U| \le k ∣ U ∣ ≤ k . Each newly inserted element e e e receives a hidden, independent bit X e ∼ Bernoulli ( p ) X_e \sim\operatorname{Bernoulli}(p) X e ∼ Bernoulli ( p ) , and S = { e ∈ U : X e = 1 } S = \{e \in U : X_e = 1\} S = { e ∈ U : X e = 1 } is the sampled subset of U U U .
Updates. The player may insert a fresh element into U U U or delete an element e ∈ U e \in U e ∈ U from U U U and S S S . Deletion discards X e X_e X e without revealing it. Every later insertion, including one with the same name, creates a new element with a fresh independent bit.
Emptiness query. The player may ask whether S S S is empty. This answer is the only information it receives about the hidden bits.
Termination. A nonempty answer lets the game continue; the first empty answer ends it immediately. The player may choose each operation adaptively from all preceding answers, and may also stop voluntarily.
Then, with probability at least 1 − η 1-\eta 1 − η , simultaneously after every update or query, including the query that terminates the game,
∣ S ∣ = O ( p k + log M + 1 η ) , |S| = O\left(pk+\log\frac{M+1}{\eta}\right), ∣ S ∣ = O ( p k + log η M + 1 ) ,
S = ∅ ⟹ ∣ U ∣ = O ( p − 1 log M + 1 η ) . S=\varnothing\quad\Longrightarrow\quad|U|=O\left(p^{-1}\log\frac{M+1}{\eta}\right). S = ∅ ⟹ ∣ U ∣ = O ( p − 1 log η M + 1 ) .
The second implication holds whether or not the player asks an emptiness query at that state.
Proof. Fixing the player’s internal randomness reduces the analysis to a deterministic strategy. Give each freshly inserted element a distinct index i i i , and let X i X_i X i be the independent Bernoulli coin assigned to that element at insertion. An insertion with the same name as a deleted element receives a new index and an independent Bernoulli random variable.
Write U t U_t U t and S t S_t S t for the sets U U U and S S S after step t t t , with U 0 = S 0 = ∅ U_0=S_0=\varnothing U 0 = S 0 = ∅ , and put λ = log ( 2 ( M + 1 ) / η ) \lambda=\log(2(M+1)/\eta) λ = log ( 2 ( M + 1 ) / η ) . Fix t ∈ { 1 , … , M } t\in\{1,\ldots,M\} t ∈ { 1 , … , M } for which the player performs at least t t t steps with positive probability. Every earlier query must have answered nonempty, since an empty answer would have terminated the game. These answers and the fixed strategy determine all operations through step t t t , and hence the sets of element indices U s U_s U s for s ≤ t s\le t s ≤ t . The event that the player performs at least t t t steps is
H t : = ⋂ s < t s is a query step { ∑ i ∈ U s X i ≥ 1 } . H_t:=\bigcap_{\substack{s<t\\s\ \text{is a query step}}}\left\{\sum_{i\in U_s}X_i\ge1\right\}. H t := s < t s is a query step ⋂ { i ∈ U s ∑ X i ≥ 1 } .
This event is increasing: changing any coin from zero to one can only increase each sum in its definition. The event that the sampled set after step t t t is empty is
E t : = { X i = 0 for every i ∈ U t } , E_t:=\{X_i=0\text{ for every }i\in U_t\}, E t := { X i = 0 for every i ∈ U t } ,
which is decreasing, whether or not step t t t is a query. Applying Lemma 3.4 to the increasing event H t H_t H t and the decreasing event E t E_t E t , we obtain
Pr [ E t ∣ H t ] ≤ Pr [ E t ] = ( 1 − p ) ∣ U t ∣ ≤ e − p ∣ U t ∣ . \Pr[E_t\mid H_t]\le\Pr[E_t]=(1-p)^{|U_t|}\le e^{-p|U_t|}. Pr [ E t ∣ H t ] ≤ Pr [ E t ] = ( 1 − p ) ∣ U t ∣ ≤ e − p ∣ U t ∣ .
Thus, if ∣ U t ∣ ≥ λ / p |U_t|\ge\lambda/p ∣ U t ∣ ≥ λ / p , the probability that the player performs step t t t and S t = ∅ S_t=\varnothing S t = ∅ is at most e − λ e^{-\lambda} e − λ . A union bound over the at most M M M steps gives failure probability at most M e − λ ≤ η / 2 Me^{-\lambda}\le\eta/2 M e − λ ≤ η /2 . Before the first step, ∣ U 0 ∣ = 0 |U_0|=0 ∣ U 0 ∣ = 0 . The union bound includes steps at which the player does not query S S S , as well as the query that terminates the game.
For the sample-size bound, let B t B_t B t be the event that the player performs at least t t t steps and ∣ S t ∣ > 2 p k + λ |S_t|>2pk+\lambda ∣ S t ∣ > 2 p k + λ . If no sampling outcome allows the player to perform t t t steps, then B t B_t B t is empty. Otherwise, as above, the fixed strategy and the common preceding nonempty answers determine the same set U t U_t U t on all outcomes that reach this step. Put
Z t : = ∑ i ∈ U t X i . Z_t:=\sum_{i\in U_t}X_i. Z t := i ∈ U t ∑ X i .
For this fixed U t U_t U t , the sampling bits are independent before conditioning on the event that step t t t is reached. Thus, before this conditioning, Z t ∼ Bin ( ∣ U t ∣ , p ) Z_t\sim\operatorname{Bin}(|U_t|,p) Z t ∼ Bin ( ∣ U t ∣ , p ) , with ∣ U t ∣ ≤ k |U_t|\le k ∣ U t ∣ ≤ k . Conditioning on the player performing t t t steps may destroy this independence, but no conditional bound is needed: on B t \mathcal{B}_t B t , we have ∣ S t ∣ = Z t > 2 p k + λ |S_t| = Z_t > 2pk + \lambda ∣ S t ∣ = Z t > 2 p k + λ . Thus, using the Chernoff bound Pr [ Z > 2 E [ Z ] + x ] ≤ e − x \Pr[Z > 2\mathbb{E}[Z] + x] \le e^{-x} Pr [ Z > 2 E [ Z ] + x ] ≤ e − x ,
Pr [ B t ] ≤ Pr [ Z t > 2 p k + λ ] ≤ e − λ . \Pr[\mathcal{B}_t] \le\Pr[Z_t > 2pk + \lambda] \le e^{-\lambda}. Pr [ B t ] ≤ Pr [ Z t > 2 p k + λ ] ≤ e − λ .
A union bound over t = 0 , … , M t = 0,\ldots,M t = 0 , … , M gives failure probability at most ( M + 1 ) e − λ = η / 2 (M+1)e^{-\lambda} = \eta/2 ( M + 1 ) e − λ = η /2 . The two bounds therefore hold simultaneously with probability at least 1 − η 1-\eta 1 − η . Averaging over the player’s initially fixed internal randomness proves the result for a randomized player as well.
Dynamic Maximal Independent Set
Data Structures
We describe the maintained state after a completed update. The next subsection specifies how each update changes these structures. For the current graph G = ( V , E ) G=(V,E) G = ( V , E ) , write N ( v ) N(v) N ( v ) for the neighbors of v v v and deg ( v ) = ∣ N ( v ) ∣ \deg(v)=|N(v)| deg ( v ) = ∣ N ( v ) ∣ for its degree. Since the graph is undirected, ( v , x ) (v,x) ( v , x ) and ( x , v ) (x,v) ( x , v ) denote the same edge.
Degree partition. We fix the two degree boundaries
b 0 = m 3 / 8 , b 1 = m 5 / 8 , (1) b_0 = m^{3/8}, \qquad b_1 = m^{5/8}, \tag*{(1)} b 0 = m 3/8 , b 1 = m 5/8 , (1)
and partition the vertex set V V V into the low degree class V l o V_{\mathrm{lo}} V lo , the middle degree class V m i d V_{\mathrm{mid}} V mid , and the high degree class V h i V_{\mathrm{hi}} V hi . These maintained classes are disjoint, although their permitted degree ranges overlap. A vertex remains in its current degree class until a migration condition in § 4.2.1 is met. The ranges satisfy:
For every v ∈ V h i v \in V_{\mathrm{hi}} v ∈ V hi , we have deg ( v ) ≥ b 1 \deg(v) \ge b_1 deg ( v ) ≥ b 1 .
For every v ∈ V m i d v \in V_{\mathrm{mid}} v ∈ V mid , we have b 0 ≤ deg ( v ) ≤ 2 b 1 b_0 \le\deg(v) \le2b_1 b 0 ≤ deg ( v ) ≤ 2 b 1 .
For every v ∈ V l o v \in V_{\mathrm{lo}} v ∈ V lo , we have deg ( v ) ≤ 2 b 0 \deg(v) \le2b_0 deg ( v ) ≤ 2 b 0 .
The degree sum gives
∣ V m i d ∣ = O ( m 5 / 8 ) , ∣ V h i ∣ = O ( m 3 / 8 ) . (2) |V_{\mathrm{mid}}| = O(m^{5/8}), \qquad|V_{\mathrm{hi}}| = O(m^{3/8}). \tag*{(2)} ∣ V mid ∣ = O ( m 5/8 ) , ∣ V hi ∣ = O ( m 3/8 ) . (2)
Maximal independent set. We maintain a maximal independent set M ⊆ V \mathcal{M} \subseteq V M ⊆ V as the output, with M i = M ∩ V i \mathcal{M}_i = \mathcal{M} \cap V_i M i = M ∩ V i for i ∈ { l o , m i d , h i } i \in\{\mathrm{lo},\mathrm{mid},\mathrm{hi}\} i ∈ { lo , mid , hi } . We call M i \mathcal{M}_i M i an MIS layer ; the shorthand low, middle, and high MIS refers to these intersections. An MIS layer need not be maximal in G [ V i ] G[V_i] G [ V i ] . For every v ∈ V v \in V v ∈ V , maintain a bit indicating whether v ∈ M v \in\mathcal{M} v ∈ M .
Exact MIS-neighbor counters. We maintain the following exact counters:
d l o ( v ) : = ∣ N ( v ) ∩ M l o ∣ for every v ∈ V , d m i d ( v ) : = ∣ N ( v ) ∩ M m i d ∣ for every v ∈ V , d h i ( v ) : = ∣ N ( v ) ∩ M h i ∣ for every v ∈ V h i . \begin{aligned}
d_{\mathrm{lo}}(v) &:= |N(v) \cap\mathcal{M}_{\mathrm{lo}}| && \text{for every } v \in V,\\
d_{\mathrm{mid}}(v) &:= |N(v) \cap\mathcal{M}_{\mathrm{mid}}| && \text{for every } v \in V,\\
d_{\mathrm{hi}}(v) &:= |N(v) \cap\mathcal{M}_{\mathrm{hi}}| && \text{for every } v \in V_{\mathrm{hi}}.
\end{aligned} d lo ( v ) d mid ( v ) d hi ( v ) := ∣ N ( v ) ∩ M lo ∣ := ∣ N ( v ) ∩ M mid ∣ := ∣ N ( v ) ∩ M hi ∣ for every v ∈ V , for every v ∈ V , for every v ∈ V hi .
Thus d l o d_{\mathrm{lo}} d lo and d m i d d_{\mathrm{mid}} d mid count low- and middle-MIS neighbors at every vertex, while d h i d_{\mathrm{hi}} d hi counts high-MIS neighbors only at high vertices.
Definition 4.1 (Candidate sets). The primary candidate set C 1 C_1 C 1 consists of low vertices outside M \mathcal{M} M with no low- or middle-MIS neighbor. The secondary candidate set C 2 C_2 C 2 consists of low vertices outside M \mathcal{M} M with no low-MIS neighbor but at least one middle-MIS neighbor. Equivalently,
C 1 = { v ∈ V l o ∖ M : d l o ( v ) = d m i d ( v ) = 0 } , (3) C_1 = \{v \in V_{\mathrm{lo}} \setminus\mathcal{M} : d_{\mathrm{lo}}(v) = d_{\mathrm{mid}}(v) = 0\}, \tag*{(3)} C 1 = { v ∈ V lo ∖ M : d lo ( v ) = d mid ( v ) = 0 } , (3) C 2 = { v ∈ V l o ∖ M : d l o ( v ) = 0 , d m i d ( v ) > 0 } . (4) C_2 = \{v \in V_{\mathrm{lo}} \setminus\mathcal{M} : d_{\mathrm{lo}}(v) = 0, d_{\mathrm{mid}}(v) > 0\}. \tag*{(4)} C 2 = { v ∈ V lo ∖ M : d lo ( v ) = 0 , d mid ( v ) > 0 } . (4) Members of C 1 C_1 C 1 are primary candidates , and members of C 2 C_2 C 2 are secondary candidates . The sets are disjoint; we use candidates for members of either set. Their candidate union C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 consists exactly of the low vertices outside M \mathcal{M} M with no low-MIS neighbor. The candidate label of a low vertex specifies whether it belongs to C 1 C_1 C 1 , to C 2 C_2 C 2 , or to neither set.
After each update, the following properties hold:
M l o \mathcal{M}_{\mathrm{lo}} M lo is a maximal independent set of G [ V l o ∖ ( C 1 ∪ C 2 ) ] G[V_{\mathrm{lo}} \setminus(C_1 \cup C_2)] G [ V lo ∖ ( C 1 ∪ C 2 )] .
Each vertex of C 1 C_1 C 1 has no low- or middle-MIS neighbor and has a high-MIS neighbor.
Each vertex of C 2 C_2 C 2 has no low-MIS neighbor and has a middle-MIS neighbor.
Every middle vertex outside M \mathcal{M} M is dominated by one of the three MIS layers; high vertices have the same guarantee.
The sets C 1 , C 2 , V m i d , V h i C_1, C_2, V_{\mathrm{mid}}, V_{\mathrm{hi}} C 1 , C 2 , V mid , V hi , and M h i \mathcal{M}_{\mathrm{hi}} M hi are stored as dynamic sets supporting membership, insertion, deletion, cardinality, and traversal. The sets used for sampling also support the indexed selection operation defined in Section 3.
Adjacency lists. For each vertex v v v , maintain three separate adjacency lists containing N ( v ) ∩ V l o N(v) \cap V_{\mathrm{lo}} N ( v ) ∩ V lo , N ( v ) ∩ V m i d N(v) \cap V_{\mathrm{mid}} N ( v ) ∩ V mid , and N ( v ) ∩ V h i N(v) \cap V_{\mathrm{hi}} N ( v ) ∩ V hi , respectively. The lists group the neighbors of v v v by their degree classes, regardless of the class of v v v itself. When a neighbor z z z changes class, move its entry to the corresponding list at v v v . An adjacency dictionary supports edge tests. Each edge has one adjacency-list entry at each endpoint, and each entry stores a pointer to the other entry. Write
E v h i : = { ( v , z ) ∈ E : z ∈ V h i } \mathcal{E}^{\mathrm{hi}}_v := \{(v,z) \in E : z \in V_{\mathrm{hi}}\} E v hi := {( v , z ) ∈ E : z ∈ V hi }
for the list of edges from v v v to its high degree neighbors. Traversing this list examines exactly the edges from v v v to vertices in V h i V_{\mathrm{hi}} V hi .
Domination edges and sampled lists. A domination edge for a vertex z ∉ M z \notin\mathcal{M} z ∈ / M is an edge ( z , x ) ∈ E ( G ) (z,x) \in E(G) ( z , x ) ∈ E ( G ) with x ∈ M x \in\mathcal{M} x ∈ M ; the MIS neighbor x x x is its domination witness . In figures, we draw the edge with an arrow from z z z to x x x solely to indicate which vertex dominates the other. Such an edge certifies that z z z is dominated by the MIS layer containing x x x . The algorithm stores a sample of the high domination edges. A nonempty stored list certifies domination only because every entry represents a current graph edge to a current high-MIS vertex.
Set the sampling probability to
p h i = 1 2 m − 1 / 4 . (5) p_{\mathrm{hi}} = \frac{1}{2}m^{-1/4}. \tag*{(5)} p hi = 2 1 m − 1/4 . (5)
For every z ∈ V m i d ∪ C 1 z \in V_{\mathrm{mid}} \cup C_1 z ∈ V mid ∪ C 1 , maintain the high domination edge list A z h i A_z^{\mathrm{hi}} A z hi consisting of sampled edges from z z z to M h i \mathcal{M}_{\mathrm{hi}} M hi . For each x ∈ M h i x \in\mathcal{M}_{\mathrm{hi}} x ∈ M hi , define its reverse high domination edge list , or reverse list , by
R x h i : = { ( z , x ) : z ∈ V m i d ∪ C 1 , ( z , x ) ∈ A z h i } . R_x^{\mathrm{hi}} := \{(z,x) : z \in V_{\mathrm{mid}} \cup C_1,\ (z,x) \in A_z^{\mathrm{hi}}\}. R x hi := {( z , x ) : z ∈ V mid ∪ C 1 , ( z , x ) ∈ A z hi } .
Each sampled edge ( z , x ) (z,x) ( z , x ) has a forward copy in A z h i A^{\mathrm{hi}}_z A z hi and a reverse copy in R x h i R^{\mathrm{hi}}_x R x hi . Each copy stores a pointer to the other copy. The two copies represent one edge selected by one sampling coin. The adjacency-list entries for an edge point to its sampled copies, if present, so a graph-edge deletion can locate them without searching either list.
A domination certificate is either a positive exact MIS-neighbor counter or a nonempty high domination edge list. Either certifies that the vertex has a current MIS neighbor. A zero counter certifies the absence of neighbors in the layer it counts, whereas an empty sampled list does not rule out unsampled high-MIS neighbors.
The high domination edge lists at low vertices are stored in an indexed collection, including empty lists; each entry identifies the corresponding low vertex. There are no high domination edge lists at vertices of C 2 C_2 C 2 . Every middle vertex has a high domination edge list, including middle MIS vertices, whose lists are empty by independence.
Figure 5. The maintained domination data structures. Only selected vertices and edges are shown. Filled vertices belong to MIS M \mathcal{M} M . Arrows point toward MIS witnesses. (i) Candidates in C 1 C_1 C 1 have d l o = d m i d = 0 d_{\mathrm{lo}} = d_{\mathrm{mid}} = 0 d lo = d mid = 0 ; those in C 2 C_2 C 2 have d l o = 0 d_{\mathrm{lo}} = 0 d lo = 0 and d m i d > 0 d_{\mathrm{mid}} > 0 d mid > 0 . Blue arrows highlight middle-MIS domination edges counted by d m i d d_{\mathrm{mid}} d mid . (ii) Orange arrows show sampled high domination edges from V m i d ∪ C 1 V_{\mathrm{mid}} \cup C_1 V mid ∪ C 1 to M h i \mathcal{M}_{\mathrm{hi}} M hi . Each sampled edge ( u , x ) (u,x) ( u , x ) has a forward copy in A u h i A^{\mathrm{hi}}_u A u hi and a reverse copy in R x h i R^{\mathrm{hi}}_x R x hi , determined by the same sampling bit. (iii) Gray lines show other graph edges, including the unsampled high domination edges ( v 2 , x 3 ) (v_2,x_3) ( v 2 , x 3 ) and ( v 3 , x 3 ) (v_3,x_3) ( v 3 , x 3 ) . No high domination edge list is stored at a vertex of C 2 C_2 C 2 .
Algorithm Description
Throughout the update algorithm, maximality repairs are organized by a priority queue Q Q Q . At the beginning of each edge update, Q = ∅ Q = \emptyset Q = ∅ . Order vertices first by degree class V l o , V m i d , V h i V_{\mathrm{lo}}, V_{\mathrm{mid}}, V_{\mathrm{hi}} V lo , V mid , V hi , then by a fixed vertex order. Write v ≺ w v \prec w v ≺ w when v v v comes before w w w . During preparation, update the position of any vertex in Q Q Q that changes degree class. Classes and priorities remain fixed during maximality restoration. A request for v v v is a pending instruction, represented by v ∈ Q v \in Q v ∈ Q , to check from the counters and domination edge lists whether v v v should be included in its current MIS layer. Whenever we say to request a vertex v v v , first check that v ∉ M v \notin\mathcal{M} v ∈ / M and that the following condition holds:
if v ∈ V l o ∪ V m i d v \in V_{\mathrm{lo}} \cup V_{\mathrm{mid}} v ∈ V lo ∪ V mid , then d l o ( v ) + d m i d ( v ) = 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) = 0 d lo ( v ) + d mid ( v ) = 0 and its high domination edge list A v h i A_v^{\mathrm{hi}} A v hi is stored and empty;
if v ∈ V h i v \in V_{\mathrm{hi}} v ∈ V hi , then d l o ( v ) + d m i d ( v ) + d h i ( v ) = 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) + d_{\mathrm{hi}}(v) = 0 d lo ( v ) + d mid ( v ) + d hi ( v ) = 0 .
Place v v v in Q Q Q only if these tests pass and v v v is not already present. If a vertex of C 1 C_1 C 1 has no stored high domination edge list during preparation, defer this test until its list is initialized after the flush test. If a flush starts, its low pass processes C 1 C_1 C 1 directly.
Issuing a request changes no other data structure. In particular, a queued low vertex stays in whichever candidate set its exact counts specify. A low or middle vertex with an empty high domination edge list may still have unsampled high-MIS neighbors; these are removed from M h i \mathcal{M}_{\mathrm{hi}} M hi before it enters the MIS. A queued vertex may also acquire domination before extraction, so the algorithm repeats the tests when it processes the request.
Each update has two phases. Preparation handles degree migrations of the two endpoints of the updated edge, applies the edge update, and restores independence. To restore maximality, we test once whether ∣ C 1 ∣ ≥ B |C_1| \ge B ∣ C 1 ∣ ≥ B , with B B B defined in § 4.2.2 . If so, a flush operation rebuilds the high MIS after processing the low candidates and middle vertices. Otherwise, we initialize the missing high domination edge lists at vertices of C 1 C_1 C 1 and process requests in queue order, including vertices in the appropriate MIS layer and making the resulting repairs. These repairs may issue further requests. When the queue becomes empty, the update ends.
Preparation
The input is an insertion or deletion e = ( s , t ) e = (s,t) e = ( s , t ) . This edge update changes vertex degrees, so we may have to update the degree partition V l o , V m i d , V h i V_{\mathrm{lo}}, V_{\mathrm{mid}}, V_{\mathrm{hi}} V lo , V mid , V hi ; we call this process degree migration . We first deal with degree migration, then process the edge insertion or deletion. Before changing the graph, compute, for w ∈ { s , t } w \in\{s,t\} w ∈ { s , t } ,
deg ^ ( w ) = { deg ( w ) + 1 , e is an insertion , deg ( w ) − 1 , e is a deletion . \widehat{\deg}(w) =
\begin{cases}
\deg(w) + 1, & e\text{ is an insertion},\\
\deg(w) - 1, & e\text{ is a deletion}.
\end{cases} deg ( w ) = { deg ( w ) + 1 , deg ( w ) − 1 , e is an insertion , e is a deletion .
The migration routine uses deg ^ \widehat{\deg} deg only to choose the degree class for w w w after the edge update. All neighbor scans, counter changes, and sampling during migration use the current graph. Thus an edge being deleted is still present during migration, while an edge being inserted is not yet present. All preparation operations finish before the flush test or any queue extraction.
Overview of degree migration. Some maintained data structures are defined only for vertices in a particular degree class. When w ∈ { s , t } w \in\{s,t\} w ∈ { s , t } changes degree class, we delete the data structures required only by w w w ’s old class and initialize those required by its new class. If w ∈ M w \in\mathcal{M} w ∈ M , we also remove w w w from its old MIS layer and include it in its new MIS layer, then update the exact counters, candidate membership, and domination edge lists at its neighbors. The case analysis below spells out these changes for every data structure. Using the boundaries in (1), the transitions are
V l o → deg ^ > 2 b 0 V m i d , V m i d → deg ^ < b 0 V l o , V_{\mathrm{lo}} \xrightarrow{\widehat{\deg}>2b_0} V_{\mathrm{mid}}, \qquad V_{\mathrm{mid}} \xrightarrow{\widehat{\deg}<b_0} V_{\mathrm{lo}}, V lo d e g > 2 b 0 V mid , V mid d e g < b 0 V lo ,
V m i d → deg ^ > 2 b 1 V h i , V h i → deg ^ < b 1 V m i d . V_{\mathrm{mid}} \xrightarrow{\widehat{\deg}>2b_1} V_{\mathrm{hi}}, \qquad V_{\mathrm{hi}} \xrightarrow{\widehat{\deg}<b_1} V_{\mathrm{mid}}. V mid d e g > 2 b 1 V hi , V hi d e g < b 1 V mid .
Process s s s and t t t in fixed order, completing one migration before starting the next. The separation of the boundaries implies at most one migration for each of s , t s,t s , t per update. Since deg ( w ) \deg(w) deg ( w ) and deg ^ ( w ) \widehat{\deg}(w) deg ( w ) differ by one, all degree bounds used during preparation allow this additive difference.
Every case below follows the same three steps.
(1) Delete objects belonging to the old class. Delete any high domination edge list A z h i A_z^{\mathrm{hi}} A z hi or reverse list R x h i R_x^{\mathrm{hi}} R x hi that is no longer maintained in the new class. When deleting A z h i A_z^{\mathrm{hi}} A z hi , remove the entry for every edge ( z , x ) (z,x) ( z , x ) from R x h i R_x^{\mathrm{hi}} R x hi as well. When deleting R x h i R_x^{\mathrm{hi}} R x hi , remove the entry for every edge ( z , x ) (z,x) ( z , x ) from A z h i A_z^{\mathrm{hi}} A z hi as well.
(2) Change the degree class and, if necessary, the MIS layer. Move the vertex between degree classes and update its entries in its neighbors’ adjacency lists. A migrating MIS vertex remains in M \mathcal{M} M , but moves between M l o , M m i d \mathcal{M}_{\mathrm{lo}},\mathcal{M}_{\mathrm{mid}} M lo , M mid , and M h i \mathcal{M}_{\mathrm{hi}} M hi . If w ∈ M w \in\mathcal{M} w ∈ M , then for each neighbor z z z , decrease the counter for w w w ’s old MIS layer by one and increase the counter for its new MIS layer by one, whenever those counters are maintained at z z z . Apply both changes before updating a low degree neighbor’s membership in C 1 C_1 C 1 and C 2 C_2 C 2 .
(3) Initialize new objects and issue requests. Initialize any newly required counter, high domination edge list at a middle vertex, or reverse high domination edge list. Update the migrated vertex’s priority in Q Q Q , if it is already queued, and request that vertex and the affected neighbors. Construction of high domination edge lists at low vertices waits until after the flush test.
Throughout preparation, whenever the MIS membership of a low vertex z z z or either counter d l o ( z ) , d m i d ( z ) d_{\mathrm{lo}}(z),d_{\mathrm{mid}}(z) d lo ( z ) , d mid ( z ) changes, use its MIS-membership bit and updated counters to determine whether z z z belongs to C 1 C_1 C 1 , C 2 C_2 C 2 , or neither set, according to (3)–(4). If z z z leaves C 1 C_1 C 1 , delete A z h i A_z^{\mathrm{hi}} A z hi , if stored, and remove the entry for every stored edge ( z , x ) (z,x) ( z , x ) from R x h i R_x^{\mathrm{hi}} R x hi . Leaving the low degree class also removes the vertex from the candidate sets. For each vertex z z z entering or reentering C 1 C_1 C 1 , construct its high domination edge list A z h i A_z^{\mathrm{hi}} A z hi using fresh independent samples after the flush test, provided that the update enters regular mode. Thus membership in the candidate sets satisfies Definition 4.1 during preparation, but a new member of C 1 C_1 C 1 need not yet have a list or a high-MIS neighbor.
To distinguish a missing list from a stored empty list, each vertex z z z has a pointer to A z h i A_z^{\mathrm{hi}} A z hi , which is null exactly when no list is stored. Whenever A z h i A_z^{\mathrm{hi}} A z hi is deleted, remove the entry for each edge ( z , x ) (z,x) ( z , x ) from R x h i R_x^{\mathrm{hi}} R x hi as well and set this pointer to null; if z z z is low, also remove the entry for A z h i A_z^{\mathrm{hi}} A z hi from the indexed collection. Preparation only deletes lists from this collection.
To initialize the high domination edge list A z h i A_z^{\mathrm{hi}} A z hi of a middle vertex z z z , sample the indexed set M h i \mathcal{M}_{\mathrm{hi}} M hi with probability p h i p_{\mathrm{hi}} p hi using Lemma 3.1. Test adjacency for each returned vertex x x x , store each edge that passes the adjacency test in both A z h i A_z^{\mathrm{hi}} A z hi and R x h i R_x^{\mathrm{hi}} R x hi , and set z z z ’s list pointer. To initialize a reverse high domination edge list R x h i R_x^{\mathrm{hi}} R x hi , independently sample V m i d V_{\mathrm{mid}} V mid and the indexed collection of high domination edge lists stored at low vertices with probability p h i p_{\mathrm{hi}} p hi . For each sampled middle vertex z z z or sampled list A z h i A_z^{\mathrm{hi}} A z hi at a low vertex z z z , test adjacency to x x x and store both copies of each edge that passes the test. This does not scan all of N ( x ) N(x) N ( x ) or enumerate low vertices whose lists have not yet been initialized. The cost includes every sampled middle vertex, every sampled list at a low vertex, and the corresponding adjacency tests, including tests that fail. We use the same reverse-list initialization whenever a vertex enters M h i \mathcal{M}_{\mathrm{hi}} M hi during maximality restoration.
For all sampled lists, use the following sampling rule. Each edge ( z , x ) (z,x) ( z , x ) with x ∈ M h i x \in\mathcal{M}_{\mathrm{hi}} x ∈ M hi and a stored list A z h i A^{\mathrm{hi}}_z A z hi receives a fresh independent Bernoulli-ρ h i \rho_{\mathrm{hi}} ρ hi bit. Use the same bit without resampling as long as the graph edge is present, x x x remains continuously in M h i \mathcal{M}_{\mathrm{hi}} M hi , and the same list A z h i A^{\mathrm{hi}}_z A z hi remains stored. If any condition ceases to hold, discard the bit; when all conditions hold again, use a fresh independent bit, even within the same update. Changes to exact counters alone do not resample edges. This rule applies to zero bits as well, although only edges whose sampling bits equal one are stored. Because degree migrations finish one at a time and delete old lists before initializing new ones, an edge whose two lists are newly created is sampled when the later list is initialized.
Specific case analysis. The following four cases specify the counter and list updates required by the three steps above. Let w ∈ { s , t } w \in\{s,t\} w ∈ { s , t } be the vertex being migrated.
(a) V l o → V m i d V_{\mathrm{lo}} \to V_{\mathrm{mid}} V lo → V mid . Move w w w when deg ^ ( w ) > 2 b 0 \widehat{\deg}(w) > 2b_0 deg ( w ) > 2 b 0 . Delete any stored A w h i A^{\mathrm{hi}}_w A w hi , removing the entry for every stored edge ( w , x ) (w,x) ( w , x ) from R x h i R^{\mathrm{hi}}_x R x hi , and remove w w w from C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 . For every neighbor z z z of w w w , move the entry for w w w from z z z ’s list of low degree neighbors to z z z ’s list of middle degree neighbors. The counters d l o ( w ) d_{\mathrm{lo}}(w) d lo ( w ) and d m i d ( w ) d_{\mathrm{mid}}(w) d mid ( w ) remain defined and require no reinitialization merely because its class changed.
If w ∉ M w \notin\mathcal{M} w ∈ / M . Changing w w w ’s degree class does not change any neighbor’s MIS-neighbor counter, because w w w is outside the MIS. Initialize the high domination edge list A w h i A^{\mathrm{hi}}_w A w hi by sampling the current M h i \mathcal{M}_{\mathrm{hi}} M hi , and request w w w .
If w ∈ M w \in\mathcal{M} w ∈ M . Remove w w w from M l o \mathcal{M}_{\mathrm{lo}} M lo and include it in M m i d \mathcal{M}_{\mathrm{mid}} M mid . For every z ∈ N ( w ) z \in N(w) z ∈ N ( w ) , decrease d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) by one and increase d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) by one. After both changes, update the candidate membership of z z z if it is low, and request z z z . Initialize the high domination edge list A w h i A^{\mathrm{hi}}_w A w hi and request w w w . This scan visits all deg ( w ) = O ( b 0 ) \deg(w) = O(b_0) deg ( w ) = O ( b 0 ) neighbors of w w w .
(b) V m i d → V l o V_{\mathrm{mid}} \to V_{\mathrm{lo}} V mid → V lo . Move w w w when deg ^ ( w ) < b 0 \widehat{\deg}(w) < b_0 deg ( w ) < b 0 . Delete A w h i A^{\mathrm{hi}}_w A w hi and remove the entry for every stored edge ( w , x ) (w,x) ( w , x ) from R x h i R^{\mathrm{hi}}_x R x hi . For every neighbor z z z of w w w , move the entry for w w w from z z z ’s list of middle degree neighbors to z z z ’s list of low degree neighbors.
If w ∉ M w \notin\mathcal{M} w ∈ / M . If d l o ( w ) > 0 d_{\mathrm{lo}}(w) > 0 d lo ( w ) > 0 , leave it outside the candidate union. If d l o ( w ) = 0 d_{\mathrm{lo}}(w) = 0 d lo ( w ) = 0 and d m i d ( w ) > 0 d_{\mathrm{mid}}(w) > 0 d mid ( w ) > 0 , put it in C 2 C_2 C 2 . Otherwise put it in C 1 C_1 C 1 , with its high domination edge list still uninitialized. Request w w w .
If w ∈ M w \in\mathcal{M} w ∈ M . Remove w w w from M m i d \mathcal{M}_{\mathrm{mid}} M mid and include it in M l o \mathcal{M}_{\mathrm{lo}} M lo . For every neighbor z z z , increase d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) by one and decrease d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) by one. Apply both changes before updating the candidate membership of z z z if it is low. Every low candidate adjacent to w w w leaves the union and deletes its high domination edge list if present. Request every neighbor z z z and w w w . This scan visits all deg ( w ) = O ( b 0 ) \deg(w) = O(b_0) deg ( w ) = O ( b 0 ) neighbors of w w w .
(c) V m i d → V h i V_{\mathrm{mid}} \to V_{\mathrm{hi}} V mid → V hi . Move w w w when deg ^ ( w ) > 2 b 1 \widehat{\deg}(w) > 2b_1 deg ( w ) > 2 b 1 . Delete its high domination edge list A w h i A^{\mathrm{hi}}_w A w hi and remove the entry for every stored edge ( w , x ) (w,x) ( w , x ) from R x h i R^{\mathrm{hi}}_x R x hi . For every neighbor z z z of w w w , move the entry for w w w from z z z ’s list of middle degree neighbors to z z z ’s list of high degree neighbors. Initialize d h i ( w ) = ∣ N ( w ) ∩ M h i ∣ d_{\mathrm{hi}}(w) = |N(w) \cap\mathcal{M}_{\mathrm{hi}}| d hi ( w ) = ∣ N ( w ) ∩ M hi ∣ by scanning its high degree neighbors.
If w ∉ M w \notin\mathcal{M} w ∈ / M . Changing w w w ’s degree class does not change any neighbor’s MIS-neighbor counter, because w w w is outside the MIS. Request w w w with the priority assigned to its new degree class V h i V_{\mathrm{hi}} V hi .
If w ∈ M w \in\mathcal{M} w ∈ M . Remove w w w from M m i d \mathcal{M}_{\mathrm{mid}} M mid and include it in M h i \mathcal{M}_{\mathrm{hi}} M hi . For every neighbor z z z , decrease d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) by one; if z ∈ V h i z \in V_{\mathrm{hi}} z ∈ V hi , also increase d h i ( z ) d_{\mathrm{hi}}(z) d hi ( z ) by one. Then update the candidate membership of z z z if it is low, and request z z z . Initialize the new R w h i R^{\mathrm{hi}}_w R w hi by sampling V m i d V_{\mathrm{mid}} V mid and the indexed collection of high domination edge lists stored at low vertices. Vertices moved from C 2 C_2 C 2 to C 1 C_1 C 1 by this migration have no stored high domination edge list, so they are not in the collection sampled to initialize R w h i R^{\mathrm{hi}}_w R w hi at this step. Request w w w . This scan visits all deg ( w ) = O ( b 1 ) \deg(w)=O(b_1) deg ( w ) = O ( b 1 ) neighbors of w w w .
(d) V h i → V m i d V_{\mathrm{hi}}\to V_{\mathrm{mid}} V hi → V mid . Move w w w when deg ^ ( w ) < b 1 \widehat{\deg}(w)<b_1 deg ( w ) < b 1 . For every neighbor z z z of w w w , move the entry for w w w from z z z ’s list of high degree neighbors to z z z ’s list of middle degree neighbors. Discard d h i ( w ) d_{\mathrm{hi}}(w) d hi ( w ) after completing the applicable case below.
If w ∉ M w\notin\mathcal{M} w ∈ / M . Initialize its high domination edge list A w h i A^{\mathrm{hi}}_w A w hi by sampling M h i \mathcal{M}_{\mathrm{hi}} M hi and request w w w .
If w ∈ M w\in\mathcal{M} w ∈ M . For every edge ( z , w ) (z,w) ( z , w ) stored in R w h i R^{\mathrm{hi}}_w R w hi , remove its entries from R w h i R^{\mathrm{hi}}_w R w hi and A z h i A^{\mathrm{hi}}_z A z hi , and request z z z . For every z ∈ N ( w ) ∩ V h i z\in N(w)\cap V_{\mathrm{hi}} z ∈ N ( w ) ∩ V hi , decrease d h i ( z ) d_{\mathrm{hi}}(z) d hi ( z ) by one. Remove w w w from M h i \mathcal{M}_{\mathrm{hi}} M hi and include it in M m i d \mathcal{M}_{\mathrm{mid}} M mid . For every neighbor z z z , increase d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) by one, update the candidate membership of z z z if it is low, and request z z z . Candidates thereby moving from C 1 C_1 C 1 to C 2 C_2 C 2 delete their high domination edge lists. Initialize the high domination edge list A w h i A^{\mathrm{hi}}_w A w hi of w w w and request it. This scan visits all deg ( w ) = O ( b 1 ) \deg(w)=O(b_1) deg ( w ) = O ( b 1 ) neighbors of w w w , even though a general high vertex can have much larger degree.
All list deletions and initializations use the sampling rule above. Class migration itself changes no graph edge or MIS membership, so it preserves independence.
Edge insertion. After migrating s s s and t t t as needed, insert e = ( s , t ) e=(s,t) e = ( s , t ) into G G G and perform the following steps, using the updated degree classes.
Class-indexed adjacency lists. Store an entry for t t t in the appropriate adjacency list at s s s , and an entry for s s s in the appropriate adjacency list at t t t . Update the adjacency dictionaries and store in each entry a pointer to the other entry.
Exact MIS-neighbor counters. If s ∈ M s\in\mathcal{M} s ∈ M , update the counter at t t t corresponding to the layer of s s s : increment d l o ( t ) d_{\mathrm{lo}}(t) d lo ( t ) if s ∈ M l o s\in\mathcal{M}_{\mathrm{lo}} s ∈ M lo ; increment d m i d ( t ) d_{\mathrm{mid}}(t) d mid ( t ) if s ∈ M m i d s\in\mathcal{M}_{\mathrm{mid}} s ∈ M mid ; and increment d h i ( t ) d_{\mathrm{hi}}(t) d hi ( t ) if s ∈ M h i s\in\mathcal{M}_{\mathrm{hi}} s ∈ M hi and t ∈ V h i t\in V_{\mathrm{hi}} t ∈ V hi . Apply the symmetric rules at s s s if t ∈ M t\in\mathcal{M} t ∈ M . These are precisely the counters whose definitions include the new edge.
Restoring independence. If both s s s and t t t belong to the MIS, remove t t t from M \mathcal{M} M when s ≺ t s\prec t s ≺ t , and remove s s s from M \mathcal{M} M when t ≺ s t\prec s t ≺ s . Thus the order ≺ \prec ≺ gives priority to V l o V_{\mathrm{lo}} V lo before V m i d V_{\mathrm{mid}} V mid before V h i V_{\mathrm{hi}} V hi , using the fixed vertex order when both vertices belong to the same degree class. The complete removal rules are given immediately below. If at most one of s , t s,t s , t belongs to the MIS, no vertex needs to be removed from it.
Candidate membership and sampling the inserted edge. For each low degree endpoint, recompute membership in C 1 C_1 C 1 and C 2 C_2 C 2 from its MIS-membership bit and updated counters, according to Definition 4.1. If the edge now joins x ∈ M h i x\in\mathcal{M}_{\mathrm{hi}} x ∈ M hi to z z z with a stored list A z h i A^{\mathrm{hi}}_z A z hi , sample it once with probability p h i p_{\mathrm{hi}} p hi and, if the sampling bit equals one, store the edge in both A z h i A^{\mathrm{hi}}_z A z hi and R x h i R^{\mathrm{hi}}_x R x hi . The eligibility of the edge for sampling is determined using the endpoints’ MIS memberships after Step (3). A low vertex whose list has not yet been initialized waits for the flush test.
If neither s s s nor t t t belongs to the MIS, the insertion changes only adjacency lists, adjacency dictionaries, and degrees. When Step (3) removes t t t from M \mathcal{M} M , the vertex s s s stays in the MIS and dominates t t t , so t t t is not placed in Q Q Q ; the case of removing s s s from M \mathcal{M} M is symmetric. All steps of the edge insertion finish before any request is extracted or any MIS is reported.
Removing the conflicting MIS vertex. Let w ∈ { s , t } w\in\{s,t\} w ∈ { s , t } be the vertex removed from M \mathcal{M} M in Step (3). Clear its MIS-membership bit and perform the following updates for its degree class. (a) w ∈ V l o w \in V_{\mathrm{lo}} w ∈ V lo . Scan every z ∈ N ( w ) z \in N(w) z ∈ N ( w ) and decrement d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) . Recompute each low degree neighbor’s membership in C 1 C_1 C 1 and C 2 C_2 C 2 using the updated counters and its MIS-membership bit, and request each affected neighbor. Then recompute w w w ’s membership in C 1 C_1 C 1 and C 2 C_2 C 2 in the same way. For every vertex newly entering C 1 C_1 C 1 , initialize its high domination edge list after the flush test if the update enters regular mode.
(b) w ∈ V m i d w \in V_{\mathrm{mid}} w ∈ V mid . Scan every z ∈ N ( w ) z \in N(w) z ∈ N ( w ) , including low degree neighbors, and decrement d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) . Update each low degree neighbor’s membership in C 1 , C 2 C_1,C_2 C 1 , C 2 according to Definition 4.1, and request a neighbor only if the counter and list tests above pass. For each vertex z z z moving from C 2 C_2 C 2 to C 1 C_1 C 1 , initialize its high domination edge list A z h i A^{\mathrm{hi}}_z A z hi using new independent samples after the flush test if the update enters regular mode (see § 4.2.2 ). Keep the high domination edge list A w h i A^{\mathrm{hi}}_w A w hi of w w w stored.
(c) w ∈ V h i w \in V_{\mathrm{hi}} w ∈ V hi . Scan E w h i E^{\mathrm{hi}}_w E w hi and decrement d h i ( z ) d_{\mathrm{hi}}(z) d hi ( z ) at each high degree neighbor, requesting it. Traverse R w h i R^{\mathrm{hi}}_w R w hi and, for each stored edge ( z , w ) (z,w) ( z , w ) , remove its entries from R w h i R^{\mathrm{hi}}_w R w hi and A z h i A^{\mathrm{hi}}_z A z hi , and request z z z . Remove w w w from the indexed high MIS. Its low degree and middle degree neighbors are not scanned in full.
Edge deletion. After migrating s s s and t t t as needed, process the deletion of e = ( s , t ) e=(s,t) e = ( s , t ) using the updated degree classes. The edge-deletion step preserves independence and leaves MIS membership unchanged, but it may remove a domination witness. The subsequent maximality-restoration procedure may change MIS membership. Perform the following steps.
If the edge has stored sampled copies, let z ∈ { s , t } z \in\{s,t\} z ∈ { s , t } be the vertex whose high domination edge list A z h i A^{\mathrm{hi}}_z A z hi contains the edge. Remove the entry for the edge from A z h i A^{\mathrm{hi}}_z A z hi and from R x h i R^{\mathrm{hi}}_x R x hi , where x x x is the other endpoint, and request z z z .
Remove the edge from both endpoints’ adjacency lists and adjacency dictionaries. If t ∈ M l o t \in M_{\mathrm{lo}} t ∈ M lo , decrement d l o ( s ) d_{\mathrm{lo}}(s) d lo ( s ) ; if t ∈ M m i d t \in M_{\mathrm{mid}} t ∈ M mid , decrement d m i d ( s ) d_{\mathrm{mid}}(s) d mid ( s ) ; and if t ∈ M h i t \in M_{\mathrm{hi}} t ∈ M hi and s ∈ V h i s \in V_{\mathrm{hi}} s ∈ V hi , decrement d h i ( s ) d_{\mathrm{hi}}(s) d hi ( s ) . Apply the symmetric rules at t t t using the MIS layer of s s s .
Recompute membership in C 1 C_1 C 1 and C 2 C_2 C 2 for each w ∈ { s , t } ∩ V l o w \in\{s,t\} \cap V_{\mathrm{lo}} w ∈ { s , t } ∩ V lo using its MIS-membership bit and updated counters, and request both s s s and t t t , whether or not the deleted edge was sampled. If a low vertex w ∈ { s , t } w \in\{s,t\} w ∈ { s , t } enters C 1 C_1 C 1 , initialize its high domination edge list after the flush test if the update enters regular mode.
Restoring Maximality
To restore maximality of M \mathcal{M} M , the algorithm uses either regular mode or flush mode . Define the flush threshold
B : = m 1 / 2 . B := m^{1/2}. B := m 1/2 .
After preparation, check whether ∣ C 1 ∣ ≥ B |C_1| \ge B ∣ C 1 ∣ ≥ B . If this condition holds, enter flush mode. Otherwise, initialize the missing high domination edge lists of vertices in C 1 C_1 C 1 as described below, and enter regular mode. The flush test is performed before these initializations, since flush mode removes every vertex of M h i \mathcal{M}_{\mathrm{hi}} M hi from the MIS and handles the vertices of C 1 C_1 C 1 directly.
For each z ∈ C 1 z \in C_1 z ∈ C 1 whose list pointer is null, call Initializehigh( z ) (z) ( z ) . This procedure independently samples M h i \mathcal{M}_{\mathrm{hi}} M hi with probability p h i p_{\mathrm{hi}} p hi using Lemma 3.1. For each returned vertex x x x , test whether ( z , x ) ∈ E ( G ) (z,x) \in E(G) ( z , x ) ∈ E ( G ) and, if so, store an entry for the edge in both A z h i A^{\mathrm{hi}}_z A z hi and R x h i R^{\mathrm{hi}}_x R x hi . Place A z h i A^{\mathrm{hi}}_z A z hi in the indexed collection of high domination edge lists at low vertices and set z z z ’s list pointer. Place z z z in Q Q Q only if A h i A^{\mathrm{hi}} A hi is empty; d l o ( z ) = d m i d ( z ) = 0 d_{\mathrm{lo}}(z)=d_{\mathrm{mid}}(z)=0 d lo ( z ) = d mid ( z ) = 0 because z ∈ C 1 z \in C_1 z ∈ C 1 . Every initialization uses fresh independent coins, and its cost includes adjacency tests for returned vertices that are not neighbors of z z z . Thus every vertex of C 1 C_1 C 1 has its high domination edge list before regular mode begins. Figure 6 summarizes the two modes and their termination conditions.
Figure 6. The two modes of maximality restoration, with B = m 1 / 2 B=m^{1/2} B = m 1/2 . After preparation, the threshold is checked once; missing high domination edge lists at low vertices are initialized only on the regular branch. In regular mode, C 1 C_1 C 1 can only shrink, so there is no further flush test. The flush processes C 1 0 C_1^0 C 1 0 (the set C 1 C_1 C 1 at its start), then V m i d V_{\mathrm{mid}} V mid , and finally V h i V_{\mathrm{hi}} V hi . The double circle marks termination of the update.
Regular mode. Regular mode repeatedly removes the highest-priority vertex v v v from Q Q Q and processes its request. We call this removal from Q Q Q an extraction . If v ∈ M v \in\mathcal{M} v ∈ M , one of its maintained exact MIS-neighbor counters is positive, or its stored high domination edge list is nonempty, stop processing this request without changing MIS membership or any maintained list or resampling any edge, and continue with the next request in Q Q Q , if any. Otherwise, include v v v in the MIS according to its degree class as follows. The steps below spell out the domination tests and the subsequent change in MIS membership. Complete all steps for v v v before extracting the next vertex from Q Q Q .
(1) v ∈ V l o v \in V_{\mathrm{lo}} v ∈ V lo .
First test whether the maintained counters or sampled list certify that v v v has an MIS neighbor.
(a) If d l o ( v ) + d m i d ( v ) > 0 d_{\mathrm{lo}}(v)+d_{\mathrm{mid}}(v)>0 d lo ( v ) + d mid ( v ) > 0 , then v v v is dominated by the low or middle MIS, so stop processing this request and continue with the next request in Q Q Q , if any. Its membership in C 1 C_1 C 1 , C 2 C_2 C 2 and any required list deletion were already updated when these counters changed. (b) We are left with d l o ( v ) = d m i d ( v ) = 0 d_{\mathrm{lo}}(v)=d_{\mathrm{mid}}(v)=0 d lo ( v ) = d mid ( v ) = 0 , so v ∈ C 1 v \in C_1 v ∈ C 1 . Check the list A v h i A^{\mathrm{hi}}_v A v hi . If A v h i ≠ ∅ A^{\mathrm{hi}}_v \ne\varnothing A v hi = ∅ , then it contains a domination edge from v v v to a vertex of M h i \mathcal{M}_{\mathrm{hi}} M hi , so stop processing this request and continue with the next request in Q Q Q , if any.
If neither test ends processing of this request, then d l o ( v ) + d m i d ( v ) = 0 d_{\mathrm{lo}}(v)+d_{\mathrm{mid}}(v)=0 d lo ( v ) + d mid ( v ) = 0 and A v h i = ∅ A^{\mathrm{hi}}_v=\varnothing A v hi = ∅ . Thus v v v has no neighbor in M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}}\cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid , but it may still have neighbors in M h i \mathcal{M}_{\mathrm{hi}} M hi whose edges were not sampled. We remove these neighbors from M h i \mathcal{M}_{\mathrm{hi}} M hi before including v v v in M l o \mathcal{M}_{\mathrm{lo}} M lo , as follows.
(c) Scan N ( v ) N(v) N ( v ) and compute X h i = N ( v ) ∩ M h i X_{\mathrm{hi}}=N(v)\cap\mathcal{M}_{\mathrm{hi}} X hi = N ( v ) ∩ M hi . For every x ∈ X h i x\in X_{\mathrm{hi}} x ∈ X hi , in fixed vertex order, remove x x x from M h i \mathcal{M}_{\mathrm{hi}} M hi and update its neighbors as follows. Scan every high degree neighbor z ∈ N ( x ) ∩ V h i z\in N(x)\cap V_{\mathrm{hi}} z ∈ N ( x ) ∩ V hi and decrement d h i ( z ) d_{\mathrm{hi}}(z) d hi ( z ) . Place z z z in Q Q Q only if z ∉ M z\notin\mathcal{M} z ∈ / M and d l o ( z ) + d m i d ( z ) + d h i ( z ) = 0 d_{\mathrm{lo}}(z)+d_{\mathrm{mid}}(z)+d_{\mathrm{hi}}(z)=0 d lo ( z ) + d mid ( z ) + d hi ( z ) = 0 . Then traverse R x h i R^{\mathrm{hi}}_x R x hi and, for each stored edge ( z , x ) (z,x) ( z , x ) , remove its entries from R x h i R^{\mathrm{hi}}_x R x hi and A z h i A^{\mathrm{hi}}_z A z hi . Place z z z in Q Q Q only if z ∉ M z\notin\mathcal{M} z ∈ / M , d l o ( z ) + d m i d ( z ) = 0 d_{\mathrm{lo}}(z)+d_{\mathrm{mid}}(z)=0 d lo ( z ) + d mid ( z ) = 0 , and A z h i = ∅ A^{\mathrm{hi}}_z=\varnothing A z hi = ∅ . Do not place x x x in Q Q Q : including v v v in M l o \mathcal{M}_{\mathrm{lo}} M lo in the next step dominates x x x , and no request is extracted before that step finishes.
(d) Remove v v v from C 1 C_1 C 1 , delete A v h i A^{\mathrm{hi}}_v A v hi , and include v v v in M l o \mathcal{M}_{\mathrm{lo}} M lo . For every neighbor z ∈ N ( v ) z\in N(v) z ∈ N ( v ) , increment d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) . If z ∈ C 1 ∪ C 2 z\in C_1\cup C_2 z ∈ C 1 ∪ C 2 , remove it from these sets and delete its high domination edge list A z h i A^{\mathrm{hi}}_z A z hi , if present, removing the entry for every stored edge ( z , x ) (z,x) ( z , x ) from R x h i R^{\mathrm{hi}}_x R x hi .
(2) v ∈ V m i d v\in V_{\mathrm{mid}} v ∈ V mid .
We process v v v in the following steps.
(a) First check whether v v v has a neighbor in M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}}\cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid . If d l o ( v ) + d m i d ( v ) > 0 d_{\mathrm{lo}}(v)+d_{\mathrm{mid}}(v)>0 d lo ( v ) + d mid ( v ) > 0 , then v v v is dominated by the low or middle MIS, so stop processing this request and continue with the next request in Q Q Q , if any.
(b) We are left with d l o ( v ) + d m i d ( v ) = 0 d_{\mathrm{lo}}(v)+d_{\mathrm{mid}}(v)=0 d lo ( v ) + d mid ( v ) = 0 . Check the list A v h i A^{\mathrm{hi}}_v A v hi . If A v h i ≠ ∅ A^{\mathrm{hi}}_v\ne\varnothing A v hi = ∅ , then it contains a domination edge from v v v to a vertex of M h i \mathcal{M}_{\mathrm{hi}} M hi , so stop processing this request and continue with the next request in Q Q Q , if any.
If neither test ends processing of this request, then d l o ( v ) + d m i d ( v ) = 0 d_{\mathrm{lo}}(v)+d_{\mathrm{mid}}(v)=0 d lo ( v ) + d mid ( v ) = 0 and A v h i = ∅ A^{\mathrm{hi}}_v=\varnothing A v hi = ∅ . We include v v v in M m i d \mathcal{M}_{\mathrm{mid}} M mid after removing any remaining high-MIS neighbors from M h i \mathcal{M}_{\mathrm{hi}} M hi , in the following steps.
(c) Scan N ( v ) N(v) N ( v ) and compute X h i = N ( v ) ∩ M h i X_{\mathrm{hi}}=N(v)\cap\mathcal{M}_{\mathrm{hi}} X hi = N ( v ) ∩ M hi . Remove every vertex of X h i X_{\mathrm{hi}} X hi from M h i \mathcal{M}_{\mathrm{hi}} M hi in fixed vertex order, updating counters, domination edge lists, and Q Q Q exactly as in the low-vertex case above. Leave the pointer to A v h i A^{\mathrm{hi}}_v A v hi unchanged; the list is empty because all of v v v ’s high-MIS neighbors have been removed from M h i \mathcal{M}_{\mathrm{hi}} M hi .
(d) Include v v v in M m i d \mathcal{M}_{\mathrm{mid}} M mid . Scan every neighbor z ∈ N ( v ) z\in N(v) z ∈ N ( v ) , including low degree neighbors, and increment d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) . If z ∈ C 1 z\in C_1 z ∈ C 1 , move it to C 2 C_2 C 2 and delete A z h i A^{\mathrm{hi}}_z A z hi , removing the entry for every stored edge ( z , x ) (z,x) ( z , x ) from R x h i R^{\mathrm{hi}}_x R x hi .
(3) v ∈ V h i v\in V_{\mathrm{hi}} v ∈ V hi .
We process v v v in the following steps.
(a) First check whether v v v is already dominated by M \mathcal{M} M . If
d l o ( v ) + d m i d ( v ) > 0 or d h i ( v ) > 0 , d_{\mathrm{lo}}(v)+d_{\mathrm{mid}}(v)>0 \qquad\text{or} \qquad d_{\mathrm{hi}}(v)>0, d lo ( v ) + d mid ( v ) > 0 or d hi ( v ) > 0 ,
stop processing this request and continue with the next request in Q Q Q , if any.
(b) Otherwise, include v v v in M h i \mathcal{M}_{\mathrm{hi}} M hi . For each high degree neighbor z ∈ N ( v ) ∩ V h i z\in N(v)\cap V_{\mathrm{hi}} z ∈ N ( v ) ∩ V hi , increment d h i ( z ) d_{\mathrm{hi}}(z) d hi ( z ) . (c) Finally, initialize R v h i R^{\mathrm{hi}}_v R v hi . Independently compute
S v m i d ← BernoulliSample ( V m i d , ϕ h i ) , S v l o ← BernoulliSample ( C 1 , ϕ h i ) . S^{\mathrm{mid}}_v \gets\operatorname{BernoulliSample}(V_{\mathrm{mid}},\phi_{\mathrm{hi}}), \qquad S^{\mathrm{lo}}_v \gets\operatorname{BernoulliSample}(C_1,\phi_{\mathrm{hi}}). S v mid ← BernoulliSample ( V mid , ϕ hi ) , S v lo ← BernoulliSample ( C 1 , ϕ hi ) .
For each returned z z z , test whether ( z , v ) ∈ E ( G ) (z,v) \in E(G) ( z , v ) ∈ E ( G ) and, if so, store an entry for the edge in both R v h i R^{\mathrm{hi}}_v R v hi and A z h i A^{\mathrm{hi}}_z A z hi .
No vertex is removed from M l o \mathcal{M}_{\mathrm{lo}} M lo or M m i d \mathcal{M}_{\mathrm{mid}} M mid during regular mode. Consequently, C 1 C_1 C 1 can only shrink, every vertex remaining in C 1 C_1 C 1 keeps its high domination edge list, and ∣ C 1 ∣ < B |C_1| < B ∣ C 1 ∣ < B holds throughout. When a vertex joins the MIS, it only increases domination at its neighbors and therefore creates no queue requests. Requests arise only from the high-MIS removals described above. There is no further flush test. When Q Q Q becomes empty, terminate the update.
Flush mode. The purpose of a flush is to empty the primary candidate set C 1 C_1 C 1 . To do so, the algorithm removes every vertex of M h i \mathcal{M}_{\mathrm{hi}} M hi from the MIS, extends the low and middle MISs, and then reconstructs the high MIS. Every vertex currently in M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid remains in the MIS throughout the flush. The algorithm performs the following steps.
(1) Make a copy C 1 0 C^0_1 C 1 0 of C 1 C_1 C 1 at the start of the flush and set Q ← ∅ Q \gets\varnothing Q ← ∅ . Keep C 1 0 C^0_1 C 1 0 unchanged throughout the flush. The following steps examine the vertices of C 1 0 C^0_1 C 1 0 , V m i d V_{\mathrm{mid}} V mid , and V h i V_{\mathrm{hi}} V hi directly; no vertex is placed in Q Q Q during flush mode. Remove every vertex x ∈ M h i x \in\mathcal{M}_{\mathrm{hi}} x ∈ M hi from the MIS. For each such x x x , scan its high degree neighbors and decrement their d h i d_{\mathrm{hi}} d hi counters, then traverse R x h i R^{\mathrm{hi}}_x R x hi and, for each stored edge ( z , x ) (z,x) ( z , x ) , remove its entries from R x h i R^{\mathrm{hi}}_x R x hi and A z h i A^{\mathrm{hi}}_z A z hi . Thus M h i = ∅ \mathcal{M}_{\mathrm{hi}} = \varnothing M hi = ∅ and all high domination edge lists are empty. Delete the high domination edge lists stored at low vertices, set their list pointers to null, and clear the indexed collection. Keep the empty lists A z h i A^{\mathrm{hi}}_z A z hi for z ∈ V m i d z \in V_{\mathrm{mid}} z ∈ V mid .
(2) Process all vertices v ∈ C 1 0 v \in C^0_1 v ∈ C 1 0 in fixed vertex order. If d l o ( v ) > 0 d_{\mathrm{lo}}(v) > 0 d lo ( v ) > 0 , then v v v is already dominated by M l o \mathcal{M}_{\mathrm{lo}} M lo and nothing needs to be done. Otherwise, remove v v v from C 1 C_1 C 1 and include it in M l o \mathcal{M}_{\mathrm{lo}} M lo . Scan every neighbor z ∈ N ( v ) z \in N(v) z ∈ N ( v ) , increment d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) , and remove z z z from C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 if it belongs there. Every vertex of C 1 0 C^0_1 C 1 0 has no neighbor in M m i d \mathcal{M}_{\mathrm{mid}} M mid , and this MIS does not change during the step, so including v v v in M l o \mathcal{M}_{\mathrm{lo}} M lo preserves independence. At the end of this step, C 1 = ∅ C_1 = \varnothing C 1 = ∅ .
(3) Process all vertices v ∈ V m i d v \in V_{\mathrm{mid}} v ∈ V mid in fixed vertex order. If v ∈ M v \in\mathcal{M} v ∈ M or d l o ( v ) + d m i d ( v ) > 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) > 0 d lo ( v ) + d mid ( v ) > 0 , nothing needs to be done. Otherwise, include v v v in M m i d \mathcal{M}_{\mathrm{mid}} M mid . Scan every neighbor z ∈ N ( v ) z \in N(v) z ∈ N ( v ) , including low degree neighbors, and increment d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) . This extends M m i d \mathcal{M}_{\mathrm{mid}} M mid to a maximal independent set of
G [ V m i d ∖ N ( M l o ) ] . G[V_{\mathrm{mid}} \setminus N(\mathcal{M}_{\mathrm{lo}})]. G [ V mid ∖ N ( M lo )] .
The high MIS is still empty. Since C 1 = ∅ C_1 = \varnothing C 1 = ∅ and no vertex leaves M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid , the candidate sets remain unchanged.
(4) Rebuild M h i \mathcal{M}_{\mathrm{hi}} M hi from scratch as a maximal independent set of
G [ V h i ∖ N ( M l o ∪ M m i d ) ] . G[V_{\mathrm{hi}} \setminus N(\mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}})]. G [ V hi ∖ N ( M lo ∪ M mid )] .
To do so, process all vertices v ∈ V h i v \in V_{\mathrm{hi}} v ∈ V hi in fixed vertex order. If d l o ( v ) + d m i d ( v ) + d h i ( v ) = 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) + d_{\mathrm{hi}}(v) = 0 d lo ( v ) + d mid ( v ) + d hi ( v ) = 0 , include v v v in M h i \mathcal{M}_{\mathrm{hi}} M hi and increment d h i ( z ) d_{\mathrm{hi}}(z) d hi ( z ) for every high degree neighbor z z z of v v v . For every vertex v v v included in M h i \mathcal{M}_{\mathrm{hi}} M hi , initialize R v h i R^{\mathrm{hi}}_v R v hi by independently sampling V m i d V_{\mathrm{mid}} V mid with probability ϕ h i \phi_{\mathrm{hi}} ϕ hi . For each returned vertex z z z , test whether ( z , v ) ∈ E ( G ) (z,v) \in E(G) ( z , v ) ∈ E ( G ) and, if so, store an entry for the edge in both R v h i R^{\mathrm{hi}}_v R v hi and A z h i A^{\mathrm{hi}}_z A z hi . Since C 1 = ∅ C_1 = \varnothing C 1 = ∅ , no high domination edge list at a low vertex needs initialization.
No vertex is removed from M m i d \mathcal{M}_{\mathrm{mid}} M mid during the flush, so every vertex remaining in C 2 C_2 C 2 has a middle-MIS neighbor throughout the flush. The flush therefore does not enumerate C 2 C_2 C 2 . The update terminates after this reconstruction, with C 1 = Q = ∅ C_1 = Q = \varnothing C 1 = Q = ∅ .
Initialization and reporting. The graph starts empty. Set M = M l o = V l o = V \mathcal{M} = \mathcal{M}_{\mathrm{lo}} = V_{\mathrm{lo}} = V M = M lo = V lo = V , all other sets and lists to empty, all counters to zero, and all list pointers to null. This initialization takes O ( n ) O(n) O ( n ) time using the fixed order of vertex identifiers. Each update reports the final changes in MIS membership; returning a complete explicit listing incurs an additional cost proportional to its output size. The adversary observes reported MISs, but not private lists, coin outcomes, traversal orders, or running times.
Proof of Correctness
Fix an arbitrary realization of the algorithm’s random choices, and let e = ( s , t ) e = (s,t) e = ( s , t ) be the updated edge. We prove that M \mathcal{M} M is independent and maximal when the update terminates. We follow the algorithm’s order: first complete any degree migrations of s s s and t t t one at a time on the graph before the edge update, then process the edge insertion or deletion using the resulting degree classes and MIS-layer labels, and finally restore maximality. During queue processing, the exact counters rule out low- and middle-MIS neighbors of a low or middle vertex. The algorithm then finds and removes all of its neighbors from M h i \mathcal{M}_{\mathrm{hi}} M hi before including the vertex in the MIS. A high vertex joins the MIS only when all three exact counters equal zero. These checks and removals establish independence, regardless of which domination edges were sampled.
For maximality, we show that every vertex outside M \mathcal{M} M is dominated when the update terminates. The exact counters and domination edge lists provide domination certificates: for z ∈ V m i d ∪ C 1 z \in V_{\mathrm{mid}} \cup C_1 z ∈ V mid ∪ C 1 , every stored edge in A z h i A_z^{\mathrm{hi}} A z hi joins z z z to a current vertex of M h i \mathcal{M}_{\mathrm{hi}} M hi . A nonempty list therefore certifies an MIS neighbor, whereas an empty list does not imply that no such neighbor exists. We verify that these certificates remain valid and that, in regular mode, every vertex outside M \mathcal{M} M without a maintained domination certificate belongs to Q Q Q immediately before each queue extraction and when the update terminates. In flush mode, the low and middle passes establish domination by M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid , and high vertices are handled by the final reconstruction of M h i \mathcal{M}_{\mathrm{hi}} M hi .
The restoration invariant. A vertex z ∉ M z \notin\mathcal{M} z ∈ / M has a domination certificate in regular mode if one of the following conditions holds:
d l o ( z ) > 0 or d m i d ( z ) > 0 or ( z ∈ C 1 and A z h i ≠ ∅ ) ; d_{\mathrm{lo}}(z) > 0 \quad\text{or} \quad d_{\mathrm{mid}}(z) > 0 \quad\text{or} \quad(z \in C_1 \text{ and } A_z^{\mathrm{hi}} \ne\varnothing); d lo ( z ) > 0 or d mid ( z ) > 0 or ( z ∈ C 1 and A z hi = ∅ ) ;
d l o ( z ) + d m i d ( z ) > 0 or A z h i ≠ ∅ ; d_{\mathrm{lo}}(z) + d_{\mathrm{mid}}(z) > 0 \quad\text{or} \quad A_z^{\mathrm{hi}} \ne\varnothing; d lo ( z ) + d mid ( z ) > 0 or A z hi = ∅ ;
d l o ( z ) + d m i d ( z ) + d h i ( z ) > 0. d_{\mathrm{lo}}(z) + d_{\mathrm{mid}}(z) + d_{\mathrm{hi}}(z) > 0. d lo ( z ) + d mid ( z ) + d hi ( z ) > 0.
Every vertex with a domination certificate has an actual neighbor in M \mathcal{M} M : each exact counter counts current MIS neighbors, and each sampled list entry corresponds to a current graph edge to a vertex in M h i \mathcal{M}_{\mathrm{hi}} M hi .
Throughout regular mode, we maintain the following invariants at the beginning of every queue-extraction iteration and at the termination of the update.
(I) Independence. The set M = M l o ∪ M m i d ∪ M h i \mathcal{M} = \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} \cup\mathcal{M}_{\mathrm{hi}} M = M lo ∪ M mid ∪ M hi is an independent set, not necessarily maximal. (II) Correctness of the data structures. The exact counters, adjacency lists, indexed sets, and domination edge lists satisfy their definitions in Section 4.1. In particular, every domination edge used to certify domination joins a vertex to a current MIS neighbor.
(III) Candidate membership. The sets C 1 C_1 C 1 and C 2 C_2 C 2 satisfy Definition 4.1. Every vertex of C 1 C_1 C 1 has a high domination edge list, and ∣ C 1 ∣ < B |C_1| < B ∣ C 1 ∣ < B .
(IV) Queue coverage of vertices without domination certificates. Every vertex outside M \mathcal{M} M without a domination certificate belongs to Q Q Q . A vertex in Q Q Q might acquire a domination certificate before its request is processed.
A vertex without a domination certificate may have actual high-MIS neighbors whose edges were not sampled. Requiring it to belong to Q Q Q ensures that losing such an edge cannot leave an undominated vertex unnoticed.
In flush mode, the high MIS is empty during the passes over C 1 0 C_1^0 C 1 0 and V m i d V_{\mathrm{mid}} V mid . These passes handle low and middle vertices directly; high vertices are deliberately postponed until M h i \mathcal{M}_{\mathrm{hi}} M hi is rebuilt. The exact counters remain correct, but high domination edge lists at low vertices are absent during these passes. The final reconstruction restores (I)–(IV) with C 1 = Q = ∅ C_1 = Q = \varnothing C 1 = Q = ∅ .
During preparation, a new member of C 1 C_1 C 1 may have no stored high domination edge list, and ∣ C 1 ∣ |C_1| ∣ C 1 ∣ may exceed the flush threshold. Thus (II)–(IV) are asserted at the start of regular mode, after the flush test and the required list initializations. A flush performs no queue-extraction iteration; for this mode, the lemmas assert these properties at completion of the final reconstruction.
All four properties hold at initialization. The following four lemmas verify them in order.
Lemma 4.2. Assume that (I)–(IV) hold before an update. The preparation phase, every completed regular iteration, and the flush passes preserve (I).
Proof. Preparation.
(a) Degree migration. A degree migration only transfers an MIS vertex between layer sets, so it changes neither the graph nor M \mathcal{M} M and preserves independence.
(b) Edge insertion. After both migrations, inserting ( s , t ) (s,t) ( s , t ) can create a conflict only between s s s and t t t . If both belong to M \mathcal{M} M , the algorithm removes t t t from M \mathcal{M} M when s ≺ t s \prec t s ≺ t and removes s s s from M \mathcal{M} M otherwise, using the degree classes after migration. The earlier vertex under ≺ \prec ≺ stays in the MIS, and independence is restored.
(c) Edge deletion. After both migrations, deleting the edge changes no MIS membership and cannot violate independence.
Thus preparation preserves (I).
Regular mode. Let v v v be the extracted vertex. Consider the degree class of v v v .
If v ∈ V l o v \in V_{\mathrm{lo}} v ∈ V lo , Item (1) permits including v v v in M l o \mathcal{M}_{\mathrm{lo}} M lo only when d l o ( v ) = d m i d ( v ) = 0 d_{\mathrm{lo}}(v) = d_{\mathrm{mid}}(v) = 0 d lo ( v ) = d mid ( v ) = 0 and removes every vertex of N ( v ) ∩ M h i N(v) \cap\mathcal{M}_{\mathrm{hi}} N ( v ) ∩ M hi from M h i \mathcal{M}_{\mathrm{hi}} M hi before v v v joins M l o \mathcal{M}_{\mathrm{lo}} M lo . Hence no conflict involving v v v remains.
If v ∈ V m i d v \in V_{\mathrm{mid}} v ∈ V mid , Item (2) permits including v v v in M m i d \mathcal{M}_{\mathrm{mid}} M mid only when d l o ( v ) + d m i d ( v ) = 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) = 0 d lo ( v ) + d mid ( v ) = 0 and removes every high-MIS neighbor of v v v from M h i \mathcal{M}_{\mathrm{hi}} M hi before v v v joins M m i d \mathcal{M}_{\mathrm{mid}} M mid .
If v v v already belongs to M \mathcal{M} M , has a positive maintained MIS-neighbor counter, or has a nonempty stored high domination edge list, the iteration ends without changing M \mathcal{M} M . Thus every completed regular iteration preserves (I).
Flush mode. Step (1) removes every vertex from M h i \mathcal{M}_{\mathrm{hi}} M hi and therefore preserves independence of M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid . Every vertex of C 1 0 C_1^0 C 1 0 has no middle-MIS neighbor, and M m i d \mathcal{M}_{\mathrm{mid}} M mid is unchanged during Step (2). A vertex joins M l o \mathcal{M}_{\mathrm{lo}} M lo in this step only when its low counter is zero, so this change creates no conflict. Step (3) next extends M m i d \mathcal{M}_{\mathrm{mid}} M mid inside V m i d ∖ N ( M l o ) V_{\mathrm{mid}} \setminus N(\mathcal{M}_{\mathrm{lo}}) V mid ∖ N ( M lo ) . Finally, Step (4) constructs an independent set inside V h i ∖ N ( M l o ∪ M m i d ) V_{\mathrm{hi}} \setminus N(\mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}}) V hi ∖ N ( M lo ∪ M mid ) . Each construction excludes every conflict with M l o \mathcal{M}_{\mathrm{lo}} M lo in the middle pass and with M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid in the high pass. Consequently their union satisfies (I) after the flush.
Lemma 4.3 (Correctness of the data structures). Assume that (I)–(IV) *hold before an update. The preparation phase together with the list initializations preceding regular mode, every completed regular iteration, and the completed flush preserve (II).
Proof. Preparation.
(a) Degree migration. For each w ∈ { s , t } w \in\{s,t\} w ∈ { s , t } that changes degree class, the algorithm first deletes lists that are no longer maintained. For every edge ( z , x ) (z,x) ( z , x ) in a deleted list A z h i A_z^{\mathrm{hi}} A z hi or R x h i R_x^{\mathrm{hi}} R x hi , it also removes the entry for that edge from the other list. It then changes the degree class, moves the entries for w w w in its neighbors’ adjacency lists, and updates the indexed class sets. If w ∈ M w \in\mathcal{M} w ∈ M , the algorithm moves w w w to the corresponding MIS layer, updates the indexed high MIS when necessary. In that case, at each neighbor it decreases the counter for w w w ’s old MIS layer by one and increases the counter for its new MIS layer by one, whenever those counters are maintained there. The counters d l o d_{\mathrm{lo}} d lo and d m i d d_{\mathrm{mid}} d mid remain defined at every vertex; d h i d_{\mathrm{hi}} d hi is initialized when a vertex enters V h i V_{\mathrm{hi}} V hi and discarded when it leaves. All scans use the graph before the edge update, so the maintained counters equal the numbers of neighbors in the resulting MIS layers of that graph.
Finally, migration initializes each newly required high domination edge list at a middle vertex or reverse high domination edge list at a high-MIS vertex, using Lemma 3.1 with probability p h i p_{\mathrm{hi}} p hi . For each sampled vertex that passes the adjacency test, the edge ( z , x ) (z,x) ( z , x ) is stored in both A z h i A_z^{\mathrm{hi}} A z hi and R x h i R_x^{\mathrm{hi}} R x hi . The second degree migration uses the classes and lists resulting from the first. Thus an edge whose two lists are newly created is sampled when the later list is initialized. The edge being inserted is still absent, and the edge being deleted is still present. Lists at low vertices leaving C 1 C_1 C 1 are deleted together with the entry for each stored edge ( z , x ) (z,x) ( z , x ) in R x h i R_x^{\mathrm{hi}} R x hi and the entry for each list in the indexed collection; lists at new members of C 1 C_1 C 1 remain uninitialized until after the flush test.
(b) Edge insertion. With the degree migrations complete, the algorithm inserts the edge into the adjacency lists and adjacency dictionaries using the resulting degree classes and increments precisely the counters at s s s and t t t whose definitions include the new edge. If both s , t ∈ M s,t \in\mathcal{M} s , t ∈ M , the algorithm then removes from M \mathcal{M} M whichever of s , t s,t s , t comes later under ≺ \prec ≺ . Removing a vertex from the low or middle MIS decrements the corresponding counter at every neighbor. Removing a vertex from the high MIS decrements the high counters at its high degree neighbors and deletes both copies of every edge in its reverse list. The indexed high MIS is updated with its membership. After recomputing membership in C 1 C_1 C 1 and C 2 C_2 C 2 from the updated counters and MIS-membership bits, the algorithm samples the new edge only if it joins a current high-MIS vertex to a vertex with a stored high domination edge list. Hence it stores no edge incident to the vertex that has just left the high MIS. (c) Edge deletion. The algorithm first deletes both sampled copies of the edge, if present. It then removes the edge from the adjacency lists and adjacency dictionaries, decrements the counters at s s s and t t t using the degree classes after migration, and recomputes the endpoints’ membership in C 1 C_1 C 1 and C 2 C_2 C 2 from their updated counters and MIS-membership bits. Thus the counters and adjacency lists now describe the graph after deletion, and no domination edge list contains the deleted edge.
Regular mode. When ∣ C 1 ∣ < B |C_1| < B ∣ C 1 ∣ < B after preparation, the algorithm initializes the missing high domination edge lists at vertices of C 1 C_1 C 1 by sampling their current high-MIS neighbors. It sets the list pointer and places the list in the indexed collection even if the list is empty. This establishes (II) before the first queue extraction.
Consider a completed regular iteration. If the extracted vertex already belongs to the MIS, has a positive maintained MIS-neighbor counter, or has a nonempty stored high domination edge list, the iteration ends without changing any of these data structures. To include a low or middle vertex in the MIS, the algorithm first removes each conflicting vertex x x x from M h i \mathcal{M}_{\mathrm{hi}} M hi and its indexed set. For each such x x x , it decrements d h i ( z ) d_{\mathrm{hi}}(z) d hi ( z ) at every neighbor z ∈ V h i z \in V_{\mathrm{hi}} z ∈ V hi and removes both stored entries of every edge ( z , x ) (z,x) ( z , x ) in R h i R^{\mathrm{hi}} R hi , one from R x h i R^{\mathrm{hi}}_x R x hi and one from A z h i A^{\mathrm{hi}}_z A z hi . It then includes the extracted vertex in M l o \mathcal{M}_{\mathrm{lo}} M lo or M m i d \mathcal{M}_{\mathrm{mid}} M mid , according to its degree class, and increments the corresponding counter at every neighbor. For each low vertex z z z leaving C 1 C_1 C 1 , the algorithm deletes A z h i A^{\mathrm{hi}}_z A z hi and removes the entry for every stored edge ( z , x ) (z,x) ( z , x ) from R x h i R^{\mathrm{hi}}_x R x hi . At every middle vertex v v v , the high domination edge list A v h i A^{\mathrm{hi}}_v A v hi remains stored, including when v v v joins M m i d \mathcal{M}_{\mathrm{mid}} M mid . When a vertex joins the high MIS, the algorithm first updates the indexed high MIS and the counters at high degree neighbors, then initializes the new reverse high domination edge list R x h i R^{\mathrm{hi}}_x R x hi of the new high-MIS member x x x . For each sampled edge ( z , x ) (z,x) ( z , x ) , it stores an entry in both R x h i R^{\mathrm{hi}}_x R x hi and A z h i A^{\mathrm{hi}}_z A z hi .
In all these operations, a stored edge ( z , x ) ∈ A z h i (z,x) \in A^{\mathrm{hi}}_z ( z , x ) ∈ A z hi joins z z z to a current vertex x ∈ M h i x \in\mathcal{M}_{\mathrm{hi}} x ∈ M hi and is stored in A z h i A^{\mathrm{hi}}_z A z hi if and only if it is stored in R x h i R^{\mathrm{hi}}_x R x hi . Whenever a low vertex’s high domination edge list is deleted, its pointer is set to null and its entry in the indexed collection is removed. Each edge ( z , x ) (z,x) ( z , x ) receives one fresh sampling bit when the conditions ( z , x ) ∈ E ( G ) (z,x) \in E(G) ( z , x ) ∈ E ( G ) , x ∈ M h i x \in\mathcal{M}_{\mathrm{hi}} x ∈ M hi , and A z h i A^{\mathrm{hi}}_z A z hi being stored first hold simultaneously; the bit remains unchanged until one of these conditions ceases to hold. Thus the sampling rule and all maintained data structures satisfy (II) after every completed iteration.
Flush mode. Step (1) empties M h i \mathcal{M}_{\mathrm{hi}} M hi , removes both stored entries of every sampled edge by traversing the reverse lists, and discards the high domination edge lists at low vertices. The low and middle passes use the same counter updates verified above. Finally, Step (4) rebuilds M h i \mathcal{M}_{\mathrm{hi}} M hi , updates its indexed set and the counters d h i d_{\mathrm{hi}} d hi , and initializes the reverse high domination edge lists R x h i R^{\mathrm{hi}}_x R x hi , storing each sampled edge ( z , x ) (z,x) ( z , x ) in both R x h i R^{\mathrm{hi}}_x R x hi and the middle vertex’s list A z h i A^{\mathrm{hi}}_z A z hi . At this point C 1 = ∅ C_1 = \varnothing C 1 = ∅ , so no high domination edge list at a low vertex is required. The graph and degree classes do not change during a flush, so the adjacency lists remain correct. Hence (II) holds when the flush terminates. □
Lemma 4.4 (Candidate membership). Assume that (I)–(IV) hold before an update. The preparation phase together with the list initializations preceding regular mode, every completed regular iteration, and the completed flush preserve (III). Moreover, fewer than B B B high domination edge lists are stored at low vertices at any time, and a flush finishes with C 1 = ∅ C_1 = \varnothing C 1 = ∅ and no such stored lists.
Proof. We consider each phase separately.
Preparation.
(a) Degree migration. A vertex leaving the low degree class is removed from C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 . A vertex v v v entering the low degree class is assigned to C 1 C_1 C 1 , C 2 C_2 C 2 , or neither according to whether v ∈ M v \in\mathcal{M} v ∈ M and the values of d l o ( v ) d_{\mathrm{lo}}(v) d lo ( v ) and d m i d ( v ) d_{\mathrm{mid}}(v) d mid ( v ) . If an MIS vertex changes class, the algorithm completes both counter changes at each neighbor before updating that neighbor’s candidate membership. Thus the candidate sets satisfy Definition 4.1 after each degree migration on the graph before the edge update.
(b) Edge insertion. After updating the counters at s s s and t t t and removing s s s or t t t from the MIS if necessary, the algorithm recomputes membership in C 1 C_1 C 1 and C 2 C_2 C 2 for each low degree endpoint and every low degree neighbor z z z whose d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) or d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) changes, using the updated counters and MIS-membership bits. Thus candidate membership uses the updated graph and MIS.
(c) Edge deletion. After deleting the edge and decrementing the counters at s s s and t t t , the algorithm recomputes membership in C 1 C_1 C 1 and C 2 C_2 C 2 for each w ∈ { s , t } ∩ V l o w \in\{s,t\} \cap V_{\mathrm{lo}} w ∈ { s , t } ∩ V lo using its updated counters and MIS-membership bit. For every z ∉ { s , t } z \notin\{s,t\} z ∈ / { s , t } , MIS membership, degree class, d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) , and d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) remain unchanged at this step. Hence the candidate sets again satisfy their definitions.
Preparation deletes a low vertex’s high domination edge list when the vertex leaves C 1 C_1 C 1 and never initializes a new one. It therefore preserves the list-count bound from the previous update.
Regular mode. When ∣ C 1 ∣ < B |C_1| < B ∣ C 1 ∣ < B after preparation, the algorithm initializes exactly the missing high domination edge lists at vertices in C 1 C_1 C 1 . Thus (III) holds when regular mode begins.
When a low vertex v v v joins M l o \mathcal{M}_{\mathrm{lo}} M lo , the algorithm removes v v v and its low degree neighbors from the candidate union. When a middle vertex joins M m i d \mathcal{M}_{\mathrm{mid}} M mid , the algorithm moves each of its neighbors in C 1 C_1 C 1 to C 2 C_2 C 2 . A high-MIS change affects neither d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) nor d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) at any vertex z z z . These are all possible candidate-set changes during regular mode, and the algorithm performs each one explicitly. No vertex leaves M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid , so neither d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) nor d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) decreases at any vertex z z z . Thus C 1 C_1 C 1 can only shrink, and the lists of vertices leaving it are deleted. This proves (III) throughout regular mode.
Flush mode. Every vertex of C 1 0 C_1^0 C 1 0 , the set C 1 C_1 C 1 at the start of the flush, enters M l o \mathcal{M}_{\mathrm{lo}} M lo or acquires a neighbor in M l o \mathcal{M}_{\mathrm{lo}} M lo . Every low vertex outside C 1 0 C_1^0 C 1 0 already belongs to the MIS or has a neighbor in M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid that remains in the MIS throughout the flush. Thus C 1 C_1 C 1 becomes empty after the low pass and cannot grow during the later passes. Membership in C 1 C_1 C 1 and C 2 C_2 C 2 is recomputed whenever d l o d_{\mathrm{lo}} d lo or d m i d d_{\mathrm{mid}} d mid changes, all high domination edge lists at low vertices are deleted, and no new one is initialized. Hence (III) holds after the flush.
Lemma 4.5 (Queue coverage of vertices without domination certificates). Assume that (I)–(IV) hold before an update. The preparation phase together with the list initializations preceding regular mode, every completed regular iteration, and the completed flush preserve (IV).
Proof. At the end of the previous update, every vertex outside the MIS has a domination certificate. We check every operation that can change this fact.
Preparation.
(a) Degree migration. A migration changes neither the graph nor MIS membership, but it can change which counters or sampled edges certify domination. When an MIS vertex changes layer, the algorithm scans the neighbors whose exact counters change and, if it leaves M h i \mathcal{M}_{\mathrm{hi}} M hi , traverses its reverse high domination edge list. It tests the affected vertices and places a vertex in Q Q Q only when its counters and stored list no longer certify domination. After initializing the structures for the migrated vertex’s new class, it applies the same tests to that vertex. If the vertex is already in Q Q Q , its position is updated according to its new degree class. A new member of C 1 C_1 C 1 without a stored list is tested after list initialization, as described below. These operations are completed for both s s s and t t t before the graph edge is changed. (b) Edge insertion. Write the inserted edge as e = ( s , t ) e=(s,t) e = ( s , t ) , with s ≺ t s\prec t s ≺ t in the order after degree migration. Inserting e e e updates the counters at s s s and t t t . If at most one of s , t s,t s , t belongs to M \mathcal{M} M , no vertex is removed from the MIS and no vertex loses a domination certificate.
If both s s s and t t t belong to M \mathcal{M} M , the algorithm keeps s s s in M \mathcal{M} M and removes t t t from M \mathcal{M} M . Since s ≺ t s\prec t s ≺ t , a low or middle vertex t t t has s ∈ M l o ∪ M m i d s\in\mathcal{M}_{\mathrm{lo}}\cup\mathcal{M}_{\mathrm{mid}} s ∈ M lo ∪ M mid as a neighbor, so d l o ( t ) + d m i d ( t ) > 0 d_{\mathrm{lo}}(t)+d_{\mathrm{mid}}(t)>0 d lo ( t ) + d mid ( t ) > 0 . If t t t is high, the neighbor s s s contributes to one of the three exact counters at t t t , so d l o ( t ) + d m i d ( t ) + d h i ( t ) > 0 d_{\mathrm{lo}}(t)+d_{\mathrm{mid}}(t)+d_{\mathrm{hi}}(t)>0 d lo ( t ) + d mid ( t ) + d hi ( t ) > 0 . Thus t t t has a domination certificate and need not be placed in Q Q Q .
Removing t t t from M \mathcal{M} M may leave a neighbor z z z without a domination certificate. If t t t is low or middle, the algorithm scans N ( t ) N(t) N ( t ) and decrements the corresponding counter at each neighbor z z z . If t t t is high, the algorithm decrements d h i ( z ) d_{\mathrm{hi}}(z) d hi ( z ) at every high degree neighbor z z z and, for each edge ( z , t ) (z,t) ( z , t ) stored in R t h i R_t^{\mathrm{hi}} R t hi , removes its entries from R t h i R_t^{\mathrm{hi}} R t hi and A z h i A_z^{\mathrm{hi}} A z hi . After each change, the algorithm requests the affected vertex z z z only if z ∉ M z\notin\mathcal{M} z ∈ / M and the counter and list tests for a request pass. Low vertices without a stored high domination edge list are checked after list initialization. Finally, sampling the inserted edge ( s , t ) (s,t) ( s , t ) can only add a domination certificate.
(c) Edge deletion. The algorithm first deletes the sampled copies, removes the edge from the adjacency lists and adjacency dictionaries, and decrements d l o ( s ) d_{\mathrm{lo}}(s) d lo ( s ) if t ∈ M l o t\in\mathcal{M}_{\mathrm{lo}} t ∈ M lo , d m i d ( s ) d_{\mathrm{mid}}(s) d mid ( s ) if t ∈ M m i d t\in\mathcal{M}_{\mathrm{mid}} t ∈ M mid , or d h i ( s ) d_{\mathrm{hi}}(s) d hi ( s ) if t ∈ M h i t\in\mathcal{M}_{\mathrm{hi}} t ∈ M hi and s ∈ V h i s\in V_{\mathrm{hi}} s ∈ V hi , with the symmetric rules at t t t . It tests s s s and t t t after these changes. Only s s s and t t t can lose a domination certificate because of the deleted edge. For an endpoint with a stored high domination edge list or a maintained high-MIS-neighbor counter, these tests determine whether it has lost all maintained domination certificates. A low endpoint newly entering C 1 C_1 C 1 without a stored list is checked after list initialization if regular mode is used.
Regular mode. When ∣ C 1 ∣ < B |C_1|<B ∣ C 1 ∣ < B after preparation, a low vertex whose high domination edge list is missing is checked after that list is initialized: if the list is empty, the vertex is put in Q Q Q before regular mode begins. These checks establish queue coverage at the start of regular mode, proving (IV) there.
During regular mode, only high-MIS vertices are removed from the MIS. Suppose that x x x is removed from M h i \mathcal{M}_{\mathrm{hi}} M hi . The algorithm checks every high degree neighbor of x x x and every vertex z z z for which ( z , x ) (z,x) ( z , x ) is stored in R x h i R_x^{\mathrm{hi}} R x hi : it scans N ( x ) ∩ V h i N(x)\cap V_{\mathrm{hi}} N ( x ) ∩ V hi and traverses R x h i R_x^{\mathrm{hi}} R x hi . Every affected vertex is tested, and it is put in Q Q Q if its remaining counters and high domination edge list no longer certify domination. These operations are performed for every neighbor removed from M h i \mathcal{M}_{\mathrm{hi}} M hi before a low or middle vertex joins the MIS. The removed vertex x x x itself is dominated by that new MIS member before the next extraction and needs no request. When a high vertex joins the MIS, no vertex is removed from the MIS, and all other branches either add domination or leave the MIS unchanged.
For a low degree or middle degree neighbor z z z of the removed high-MIS vertex x x x , an edge ( z , x ) (z,x) ( z , x ) that was not stored requires no separate check. Either z z z already had no domination certificate and belonged to Q Q Q , or it had a domination certificate from d l o ( z ) + d m i d ( z ) > 0 d_{\mathrm{lo}}(z)+d_{\mathrm{mid}}(z)>0 d lo ( z ) + d mid ( z ) > 0 or a different sampled edge in A z h i A_z^{\mathrm{hi}} A z hi . Removing x x x from M h i \mathcal{M}_{\mathrm{hi}} M hi changes neither condition. This observation applies to high-MIS removals in preparation as well.
A request is discarded without changing MIS membership only when its vertex already belongs to the MIS, has a positive maintained MIS-neighbor counter, or has a nonempty stored high domination edge list. Otherwise, the iteration includes the vertex in the MIS and makes all resulting requests before the next extraction. No other pending request is removed, and duplicate requests leave the original one present. Therefore every completed regular iteration preserves (IV).
Flush mode. Step (1) empties Q Q Q and removes every vertex of M h i \mathcal{M}_{\mathrm{hi}} M hi from the MIS. The subsequent passes process the affected vertices directly, so (IV) is not asserted until the high layer has been reconstructed. Every low vertex outside M \mathcal{M} M with no low- or middle-MIS neighbor at the start of the flush belongs to C 1 0 C_1^0 C 1 0 . Step (2) includes each such vertex in M l o \mathcal{M}_{\mathrm{lo}} M lo or gives it a low-MIS neighbor. All other low vertices either stay in the MIS or remain adjacent to a vertex in M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid , since the flush removes no vertex from these two MIS layers. Step (3) then extends M m i d \mathcal{M}_{\mathrm{mid}} M mid to a maximal independent set on the middle vertices not dominated by M l o \mathcal{M}_{\mathrm{lo}} M lo . Consequently, every low or middle vertex v ∉ M v \notin\mathcal{M} v ∈ / M satisfies d l o ( v ) + d m i d ( v ) > 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) > 0 d lo ( v ) + d mid ( v ) > 0 after these two passes. No later step removes a vertex from M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid .
Finally, Step (4) constructs a maximal independent set on the high vertices not dominated by M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid . Every remaining high vertex outside M \mathcal{M} M therefore has a positive exact counter. Thus every vertex outside M \mathcal{M} M has a domination certificate, and (IV) holds with Q = ∅ Q = \emptyset Q = ∅ after the flush.
The four invariants imply correctness at the end of each update.
Lemma 4.6. When the update algorithm terminates, M = M l o ∪ M m i d ∪ M h i \mathcal{M} = \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} \cup\mathcal{M}_{\mathrm{hi}} M = M lo ∪ M mid ∪ M hi is a maximal independent set of the current graph G G G .
Proof. There are two possible termination cases. In regular mode, the update terminates only after all requests have been extracted. By Lemmas 4.2 to 4.5, (I)–(IV) hold with Q = ∅ Q = \emptyset Q = ∅ . In flush mode, the update terminates only after the low and middle passes and the final high-layer reconstruction. The flush cases of the same four lemmas again give (I)–(IV) with Q = ∅ Q = \emptyset Q = ∅ . Thus, in every termination case, (I) gives independence and (IV) ensures that every vertex outside M \mathcal{M} M has a domination certificate. By (II)–(III), each such vertex has an actual MIS neighbor. Hence M \mathcal{M} M is maximal.
Probabilistic Properties against Adaptive Adversaries
We use the two probabilistic games from the preliminaries to prove the following lemmas. The running-time analysis requires three sampling guarantees: reverse lists remain small, the stored high domination edge lists of low and middle vertices remain small, and an empty high domination edge list implies that its vertex has few neighbors in the high MIS. These properties bound, respectively, the work of removing a vertex from M h i \mathcal{M}_{\mathrm{hi}} M hi , maintaining a low or middle vertex’s high domination edge list, and removing conflicting high-MIS neighbors from M h i \mathcal{M}_{\mathrm{hi}} M hi before a low or middle vertex enters the MIS. For fixed sets, the guarantees follow from standard sampling bounds. The difficulty here is that the reported MIS depends on the sampled lists, and the adversary uses these outputs to choose later updates. Thus the current graph and MIS cannot be treated as independent of the sampling choices.
The membership-query game of Lemma 3.2 gives the reverse-list bound. The emptiness-query game of Lemma 3.5 bounds both the stored high domination edge lists and the number of high-MIS neighbors when such a list is empty. In each proof, a simulator acts as the player in the corresponding game. We fix the adversary’s internal randomness and all sampling coins except those defining the sampled list under consideration. The excluded coins include those shared with copies of the sampled edges in other lists. The simulator uses the fixed coins to simulate the MIS algorithm and the adaptive adversary. The simulator must reproduce the MIS reported after each completed update to ensure that the adversary chooses the same subsequent updates. We verify that it can do so using only the operations allowed by the game, and then apply the game’s probabilistic guarantees to the sampled list.
Throughout this analysis, a time interval is a consecutive portion of the algorithm’s execution, ordered by its individual operations. Its start and end events may occur within a single edge update. Each game step is one permitted update or query in the probabilistic game; one edge update of the graph may generate several game steps.
Lemma 4.7. Against any adaptive adversary generating a polynomial-length update sequence, with high probability, simultaneously throughout the sequence,
∣ R x h i ∣ = O ~ ( m 3 / 8 ) ( x ∈ M h i ) . \left|R^{hi}_x\right| = \widetilde{O}\left(m^{3/8}\right) \qquad(x \in\mathcal{M}_{hi}). R x hi = O ( m 3/8 ) ( x ∈ M hi ) . On the same event, every reverse-list initialization samples O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) vertices, including vertices rejected by the adjacency test.
Proof. We use the simulation argument for the membership-query game of Lemma 3.2 . In this application, U U U represents the adjacency list of one high-MIS vertex restricted to neighbors whose high domination edge lists are stored, including both sampled and unsampled edges. The set S S S represents that vertex’s reverse high domination edge list. For each application, fix all sampling coins except those defining this reverse list. Given these fixed coins, a simulator can reproduce the reported MISs, and hence the adversary’s next updates, while consulting S S S only through the operations allowed by the game. We verify this claim below.
Fix a vertex x x x and consider the maximal time interval from one entry of x x x into M h i \mathcal{M}_{hi} M hi until its next departure. Entry or departure through degree migration is included, and removal by a flush also ends the time interval. A later reentry starts a new time interval, even within the same edge update. Throughout this time interval, define
U : = { ( x , y ) ∈ E ( G ) : A y h i is stored } , S : = R x h i . U := \{(x,y) \in E(G) : A^{hi}_y \text{ is stored}\}, \qquad S := R^{hi}_x. U := {( x , y ) ∈ E ( G ) : A y hi is stored } , S := R x hi .
Thus U U U is the adjacency list of x x x restricted to middle vertices and low candidates whose high domination edge lists have been initialized, and S S S consists of its sampled edges. An edge ( x , y ) ∈ U (x,y) \in U ( x , y ) ∈ U belongs to S S S exactly when it is stored in A y h i A^{hi}_y A y hi .
Condition on the history before x x x enters M h i \mathcal{M}_{hi} M hi . The game starts with U = S = ∅ U = S = \varnothing U = S = ∅ . When R x h i R^{hi}_x R x hi is initialized, place every graph edge ( x , y ) (x,y) ( x , y ) for which A y h i A^{hi}_y A y hi is stored into U U U . Assign each such edge an independent Bernoulli-ϕ h i \phi_{hi} ϕ hi bit, where ϕ h i = 1 2 m − 1 / 4 \phi_{hi} = \frac{1}{2}m^{-1/4} ϕ hi = 2 1 m − 1/4 , and include it in S = R x h i S = R^{hi}_x S = R x hi exactly when its bit is one. The simulator knows the graph, MIS, exact counters, and all sampling bits not used to define S S S . For ( x , y ) ∈ U (x,y) \in U ( x , y ) ∈ U , the same hidden bit determines whether the edge appears in S S S and in A y h i A^{hi}_y A y hi , so the simulator cannot inspect that copy separately. Fixing the adversary’s internal randomness, the simulator supplies each reported MIS to the adversary and obtains the next graph update.
We first explain how updates to the adjacency list and reverse high domination edge list correspond to the game’s insertion and reveal-and-delete operations. This correspondence specifies the lifetime of each sampling bit and when the game ends. Inserting an edge ( x , y ) (x,y) ( x , y ) for which A y h i A^{hi}_y A y hi is stored, or initializing a list at an existing neighbor y y y , inserts a fresh element into U U U with an independent sampling bit. This bit is kept as long as the edge is present, x x x stays in M h i \mathcal{M}_{hi} M hi , and the same list A y h i A^{hi}_y A y hi remains stored. Deleting the edge or discarding A y h i A^{hi}_y A y hi removes the entry from U U U and S S S and discards its sampling bit. Every later insertion of the same graph edge creates a new game element with a fresh independent bit. In particular, a low vertex leaving C 1 C_1 C 1 discards its high domination edge list; a later return initializes that list using new independent samples. A middle vertex keeps its list while it remains in the middle degree class. The departure of x x x from M h i \mathcal{M}_{hi} M hi , including its removal by a flush, ends the game.
We represent deletion of an entry from U U U by the game’s reveal-and-delete operation. This gives the simulator the entry’s sampling bit so that it can reproduce the removal of any stored copies and the resulting domination checks. This disclosure occurs only within the simulation; the graph adversary observes only the reported MISs. The game operation simultaneously removes the entry from U U U and S S S , so the revealed bit can no longer contribute to the sample or be used in a later insertion.
We now show that the data structure’s decisions and reported MISs can be simulated using only the query rules of Lemma 3.2. It remains to verify that whenever the simulator makes an ordinary membership query about an edge still in U U U , a no answer ends the game. For an edge ( x , y ) ∈ U (x,y) \in U ( x , y ) ∈ U , put
B y : = A y h i ∖ { ( x , y ) } . B_y := A_y^{\mathrm{hi}} \setminus\{(x,y)\}. B y := A y hi ∖ {( x , y )} .
The simulator knows B y B_y B y , since its sampling coins are among those fixed. While B y ≠ ∅ B_y \ne\emptyset B y = ∅ , the list A y h i A_y^{\mathrm{hi}} A y hi is nonempty under either value of the sampling bit for ( x , y ) (x,y) ( x , y ) . No query is needed if y ∈ M y \in\mathcal{M} y ∈ M or d l o ( y ) + d m i d ( y ) > 0 d_{\mathrm{lo}}(y)+d_{\mathrm{mid}}(y)>0 d lo ( y ) + d mid ( y ) > 0 , either. We defer querying this bit until y y y is extracted from the simulated queue with d l o ( y ) = d m i d ( y ) = 0 d_{\mathrm{lo}}(y)=d_{\mathrm{mid}}(y)=0 d lo ( y ) = d mid ( y ) = 0 and B y = ∅ B_y=\emptyset B y = ∅ . At that point the simulator asks whether ( x , y ) ∈ S (x,y) \in S ( x , y ) ∈ S . A yes answer establishes that y y y is dominated and lets the game continue. A no answer establishes that A y h i A_y^{\mathrm{hi}} A y hi is empty. The algorithm then removes every high-MIS neighbor of y y y , including x x x , from M h i \mathcal{M}_{\mathrm{hi}} M hi and includes y y y in M l o \mathcal{M}_{\mathrm{lo}} M lo if y ∈ V l o y \in V_{\mathrm{lo}} y ∈ V lo , or in M m i d \mathcal{M}_{\mathrm{mid}} M mid if y ∈ V m i d y \in V_{\mathrm{mid}} y ∈ V mid . The current game therefore terminates, exactly as required by Lemma 3.2.
It remains to justify deferring the query, since the real algorithm tests list emptiness before placing a vertex in Q Q Q . Whenever a change to a vertex y y y ’s counters or domination edge list requires such a test, the simulator first checks whether y ∉ M y \notin\mathcal{M} y ∈ / M and d l o ( y ) = d m i d ( y ) = 0 d_{\mathrm{lo}}(y)=d_{\mathrm{mid}}(y)=0 d lo ( y ) = d mid ( y ) = 0 . If these conditions hold but the list test depends on the hidden bit of ( x , y ) (x,y) ( x , y ) , the simulator puts y y y in its queue without querying that bit. The same rule applies when A y h i A_y^{\mathrm{hi}} A y hi is initialized. All other list tests use known coins. Deleting an entry from U U U uses reveal-and-delete, but the simulator does not query the sampling bits of edges still in U U U to decide whether to issue a request. Membership in C 1 C_1 C 1 and C 2 C_2 C 2 , the flush test, and decisions to include vertices in the high MIS use exact counters and are reproduced directly.
The simulated queue contains every real request and may contain additional ones. By Lemma 4.5, every vertex outside the MIS with neither a positive maintained MIS-neighbor counter nor a nonempty stored high domination edge list is already in the real queue before an extraction. A vertex y y y extracted only from the simulated queue must therefore belong to the MIS, satisfy d l o ( y ) + d m i d ( y ) > 0 d_{\mathrm{lo}}(y)+d_{\mathrm{mid}}(y)>0 d lo ( y ) + d mid ( y ) > 0 , or have a nonempty stored list A y h i A_y^{\mathrm{hi}} A y hi . Its extraction changes only the simulated queue, leaving MIS membership, counters, candidate sets, and domination edge lists unchanged. Both queues use the same fixed priority order. After omitting these additional extractions, both executions extract the same next vertex and make the same changes to the MIS and data structures. Induction therefore gives the same reported MISs and subsequent adversarial updates. In particular, a no answer to the membership query above occurs only when the real algorithm also includes y y y in the MIS and removes x x x from it. Thus it ends the game, and no other membership query about an edge still in U U U is needed.
We can now apply the game lemma. By Lemma 4.4, fewer than B B B high domination edge lists are stored at low vertices at every instant, even during preparation when C 1 C_1 C 1 itself may be larger. Hence
∣ U ∣ ≤ ∣ V m i d ∣ + B = O ( m 5 / 8 + m 1 / 2 ) = O ( m 5 / 8 ) , |U| \le|V_{\mathrm{mid}}|+B=O(m^{5/8}+m^{1/2})=O(m^{5/8}), ∣ U ∣ ≤ ∣ V mid ∣ + B = O ( m 5/8 + m 1/2 ) = O ( m 5/8 ) ,
and the lemma gives
∣ R x h i ∣ = ∣ S ∣ = O ~ ( p h i m 5 / 8 ) = O ~ ( m 3 / 8 ) . |R_x^{\mathrm{hi}}|=|S|=\widetilde{O}(p_{\mathrm{hi}}m^{5/8})=\widetilde{O}(m^{3/8}). ∣ R x hi ∣ = ∣ S ∣ = O ( p hi m 5/8 ) = O ( m 3/8 ) .
This includes the state immediately before x x x is removed from M h i \mathcal{M}_{\mathrm{hi}} M hi ; subsequent cleanup only shortens its reverse list. There are polynomially many operations and entries into M h i \mathcal{M}_{\mathrm{hi}} M hi , regardless of the sampling outcomes. Choosing a sufficiently small inverse-polynomial failure probability and taking a union bound proves the simultaneous reverse-list bound.
To bound the number of vertices sampled during initialization, condition on the history before a fresh sampling call. The set V m i d V_{\mathrm{mid}} V mid and the indexed collection of high domination edge lists stored at low vertices are then fixed, and the number of sampled vertices is binomial with mean at most ϕ h i ( ∣ V m i d ∣ + B ) = O ( m 3 / 8 ) \phi_{\mathrm{hi}}(|V_{\mathrm{mid}}| + B) = O(m^{3/8}) ϕ hi ( ∣ V mid ∣ + B ) = O ( m 3/8 ) . A Chernoff bound and a union bound over all calls give O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) sampled vertices, including those that fail the adjacency test.
Lemma 4.8. Against any polynomial-length adaptive update sequence, with high probability, the following two bounds hold simultaneously for every stored high domination edge list at a low or middle vertex, after initialization and after every completed update to that list:
∣ A v h i ∣ = O ~ ( m 1 / 8 ) , |A_v^{hi}| = \widetilde{O}(m^{1/8}), ∣ A v hi ∣ = O ( m 1/8 ) , and
A v h i = ∅ ⟹ ∣ N ( v ) ∩ M h i ∣ = O ~ ( m 1 / 4 ) . (6) A_v^{hi} = \varnothing\quad\Longrightarrow\quad|N(v) \cap\mathcal{M}_{hi}| = \widetilde{O}(m^{1/4}). \tag*{(6)} A v hi = ∅ ⟹ ∣ N ( v ) ∩ M hi ∣ = O ( m 1/4 ) . (6) On the same event, every initialization of a list A v h i A_v^{hi} A v hi samples O ~ ( m 1 / 8 ) \widetilde{O}(m^{1/8}) O ( m 1/8 ) vertices, including vertices rejected by the adjacency test.
Proof. We apply the emptiness-query game of Lemma 3.5 separately to each high domination edge list, with p = ϕ h i = 1 2 m − 1 / 4 p = \phi_{\mathrm{hi}} = \frac{1}{2}m^{-1/4} p = ϕ hi = 2 1 m − 1/4 . For each type of list, we specify the game, identify the corresponding list updates, and show how the simulator defers emptiness queries by queuing v v v without testing the list. We then apply the game bounds. The simulation must preserve the MIS reported after each completed update, so the adaptive adversary chooses the same subsequent updates.
The high domination edge list of a low vertex.
Game specification. Fix a low vertex v v v and follow one stored list A v h i A_v^{hi} A v hi over the time interval from its initialization until it is discarded. Define
U : = { ( x , v ) ∈ E ( G ) : x ∈ M h i } , S : = A v h i = { e ∈ U : X e = 1 } , U := \{(x,v) \in E(G) : x \in\mathcal{M}_{hi}\}, \qquad S := A_v^{hi} = \{e \in U : X_e = 1\}, U := {( x , v ) ∈ E ( G ) : x ∈ M hi } , S := A v hi = { e ∈ U : X e = 1 } ,
where each edge e e e newly placed in U U U receives an independent X e ∼ Bernoulli ( p ) X_e \sim\operatorname{Bernoulli}(p) X e ∼ Bernoulli ( p ) . Start with U = S = ∅ U = S = \varnothing U = S = ∅ immediately before initialization. Place every current graph edge ( x , v ) (x,v) ( x , v ) with x ∈ M h i x \in\mathcal{M}_{hi} x ∈ M hi into U U U , and include it in S S S exactly when X e = 1 X_e = 1 X e = 1 . Condition on the preceding history, fix the adversary’s internal randomness, and fix all sampling coins except those defining A v h i A_v^{hi} A v hi in this game. The simulator acts as the game player: it runs the MIS data structure and the adaptive adversary, supplying each reported MIS to obtain the next graph update. It knows the graph, MIS, exact counters, and all sampling bits not used to define S S S , but can learn about S S S only through the permitted emptiness queries. The game ends when A v h i A_v^{hi} A v hi is discarded, including when v v v leaves C 1 C_1 C 1 , changes degree class, or enters M l o \mathcal{M}_{lo} M l o . Any later initialization starts a new game with fresh coins. A flush also discards the list and ends the game.
Data-structure changes and game operations. Initialization inserts every edge from v v v to M h i \mathcal{M}_{hi} M hi into U U U . Inserting ( x , v ) (x,v) ( x , v ) with x ∈ M h i x \in\mathcal{M}_{hi} x ∈ M hi , or including a neighbor x x x of v v v in M h i \mathcal{M}_{hi} M hi , inserts ( x , v ) (x,v) ( x , v ) into U U U with a fresh coin. Deleting ( x , v ) (x,v) ( x , v ) or removing x x x from M h i \mathcal{M}_{hi} M hi deletes the entry from U U U and S S S without revealing its sampling bit. This bit is discarded; a later insertion of the same graph edge uses a fresh independent bit. For each ( x , v ) ∈ U (x,v) \in U ( x , v ) ∈ U , the simulator does not determine whether an entry for that edge is stored in R x h i R_x^{hi} R x hi . When x x x leaves the high MIS, the simulator deletes ( x , v ) (x,v) ( x , v ) from the game’s sets without learning its sampling bit. Outside flush mode, it queues v v v if v ∉ M v \notin\mathcal{M} v ∈ / M and d l o ( v ) = d m i d ( v ) = 0 d_{lo}(v) = d_{mid}(v) = 0 d l o ( v ) = d mi d ( v ) = 0 , regardless of whether the edge was sampled.
Deferring queries until v v v is processed. The real execution checks whether A v h i A_v^{hi} A v hi is empty before issuing certain requests for v v v , for example after initialization or removal of a domination edge. The simulator instead puts v v v in its queue without querying S S S , provided v ∉ M v \notin\mathcal{M} v ∈ / M and d l o ( v ) = d m i d ( v ) = 0 d_{lo}(v) = d_{mid}(v) = 0 d l o ( v ) = d mi d ( v ) = 0 , suppressing duplicate requests. While the request is pending, changes to the graph or MIS induce permitted updates to the game sets U U U and S S S . These updates reveal no sampling bits; any emptiness
query is deferred until v v v is processed. Queuing v v v does not end the game. In any other vertex’s reverse high domination edge list, the only potentially hidden entry is the edge to v v v . When that edge is deleted from U U U , the simulator uses the same rule without asking whether the edge was sampled. It also uses this rule when the graph or exact counters at v v v change. All other vertices’ high domination edge lists use known coins, and high-MIS decisions, membership in C 1 C_1 C 1 and C 2 C_2 C 2 , and the flush test use exact counters.
When v v v is extracted, the simulator first checks whether v ∈ M v \in\mathcal{M} v ∈ M or d l o ( v ) + d m i d ( v ) > 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) > 0 d lo ( v ) + d mid ( v ) > 0 . If either condition holds, it discards the request without changing MIS membership or any maintained list and without querying S S S . Otherwise, it asks whether S S S is empty. On a nonempty answer, the simulator discards the request without changing the MIS or any maintained list and continues the simulation. An empty answer establishes that A v h i A_v^{\mathrm{hi}} A v hi is empty. The algorithm then removes all high-MIS neighbors of v v v from M h i \mathcal{M}_{\mathrm{hi}} M hi , includes v v v in M l o \mathcal{M}_{\mathrm{lo}} M lo , and discards its list. This ends the game. Thus every queried empty answer terminates the game, as required.
The additional requests preserve the reported MISs. By Lemma 4.5, every vertex outside the MIS with neither a positive maintained MIS-neighbor counter nor a nonempty stored high domination edge list is already in the real queue before an extraction. Any additional request is for v v v , so if v v v is absent from the real queue, then v ∈ M v \in\mathcal{M} v ∈ M , d l o ( v ) + d m i d ( v ) > 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) > 0 d lo ( v ) + d mid ( v ) > 0 , or its stored list A v h i A_v^{\mathrm{hi}} A v hi is nonempty. Its extraction changes only the simulated queue, leaving MIS membership, counters, candidate sets, and domination edge lists unchanged. Both queues use the same fixed priority order. After omitting these additional extractions, their next extracted vertex is the same, and its processing makes the same MIS changes and issues the same requests, except possibly for additional requests for v v v . Induction over the extractions therefore gives the same reported MISs and subsequent adversarial updates. In particular, an empty answer after which the algorithm includes v v v in the MIS can occur only when v v v also belongs to the real queue. The simulator may enumerate U U U to issue these additional requests; the simulation’s running time does not contribute to the algorithm’s update bound.
During a flush no high domination edge list is tested for emptiness. The simulator deletes each entry of U U U and S S S and discards its sampling bit without revealing it. Discarding the high domination edge list A v h i A_v^{\mathrm{hi}} A v hi then ends the game.
At every state, ∣ U ∣ ≤ ∣ V h i ∣ = O ( m 3 / 8 ) |U| \le|V_{\mathrm{hi}}| = O(m^{3/8}) ∣ U ∣ ≤ ∣ V hi ∣ = O ( m 3/8 ) . The two conclusions of Lemma 3.5 therefore give
∣ A v h i ∣ = O ~ ( p m 3 / 8 ) = O ~ ( m 1 / 8 ) , |A_v^{\mathrm{hi}}| = \widetilde{O}(pm^{3/8}) = \widetilde{O}(m^{1/8}), ∣ A v hi ∣ = O ( p m 3/8 ) = O ( m 1/8 ) ,
and
A v h i = ∅ ⟹ ∣ N ( v ) ∩ M h i ∣ = O ~ ( p − 1 ) = O ~ ( m 1 / 4 ) . A_v^{\mathrm{hi}} = \emptyset\quad\Longrightarrow\quad|N(v) \cap\mathcal{M}_{\mathrm{hi}}| = \widetilde{O}(p^{-1}) = \widetilde{O}(m^{1/4}). A v hi = ∅ ⟹ ∣ N ( v ) ∩ M hi ∣ = O ( p − 1 ) = O ( m 1/4 ) .
The second bound holds whether or not the list is queried at that state, and includes the time immediately before v v v joins M l o \mathcal{M}_{\mathrm{lo}} M lo .
The high domination edge list of a middle vertex.
Game specification. Fix v ∈ V m i d v \in V_{\mathrm{mid}} v ∈ V mid and define
U : = { ( x , v ) ∈ E ( G ) : x ∈ M h i } , S : = A v h i = { e ∈ U : X e = 1 } . U := \{(x,v) \in E(G) : x \in\mathcal{M}_{\mathrm{hi}}\}, \qquad S := A_v^{\mathrm{hi}} = \{e \in U : X_e = 1\}. U := {( x , v ) ∈ E ( G ) : x ∈ M hi } , S := A v hi = { e ∈ U : X e = 1 } .
Each new entry receives an independent X e ∼ Bernoulli ( p ) X_e \sim\operatorname{Bernoulli}(p) X e ∼ Bernoulli ( p ) . Condition on the history before each game, fix the adversary’s internal randomness, and fix all sampling coins except those defining A v h i A_v^{\mathrm{hi}} A v hi in this game. As in the low-vertex case, the simulator runs the MIS data structure and the adaptive adversary, and accesses S S S only through the game’s emptiness queries. The first game starts with U = S = ∅ U = S = \emptyset U = S = ∅ immediately before list initialization. Each game ends at the next of the following events: v v v leaves V m i d V_{\mathrm{mid}} V mid , v v v enters M m i d \mathcal{M}_{\mathrm{mid}} M mid , or a flush finishes clearing the high MIS.
A middle vertex keeps its list throughout its time in V m i d V_{\mathrm{mid}} V mid , including after joining the MIS. We start a new game immediately after v v v joins M m i d \mathcal{M}_{\mathrm{mid}} M mid . At that point U = S = ∅ U=S=\emptyset U = S = ∅ , since all high-MIS neighbors were removed from M h i \mathcal{M}_{\mathrm{hi}} M hi before v v v joined M m i d \mathcal{M}_{\mathrm{mid}} M mid , including those whose edges were not sampled. These deletions discard their sampling bits; every later insertion uses a fresh independent bit. Likewise, a flush removes all high-MIS neighbors of v v v from M h i \mathcal{M}_{\mathrm{hi}} M hi , deletes their entries from U U U and S S S , and discards their sampling bits without an emptiness query. A new game starts with empty sets immediately after this clearing, before the high MIS is reconstructed. Thus each game corresponds to a time interval beginning at list initialization or one of these restarts and ending at the next specified event. These successive game time intervals cover the entire period during which the list is stored.
2. Data-structure changes and game operations. Initialization inserts every edge from v v v to M h i \mathcal{M}_{\mathrm{hi}} M hi into U U U . An edge insertion or entry of a neighbor into M h i \mathcal{M}_{\mathrm{hi}} M hi inserts the corresponding entry with a fresh independent value of X e X_e X e . An edge deletion or departure of the neighbor from M h i \mathcal{M}_{\mathrm{hi}} M hi deletes that entry from U U U and S S S without revealing X e X_e X e . Its old bit is discarded; any later insertion uses a fresh independent bit. As in the low-vertex case, the simulator does not determine whether an entry for ( x , v ) (x,v) ( x , v ) is stored in R x h i R_x^{\mathrm{hi}} R x hi . When x x x leaves the high MIS, it deletes ( x , v ) (x,v) ( x , v ) from the game’s sets without learning the sampling bit. Outside flush mode, it queues v v v if v ∉ M v\notin\mathcal{M} v ∈ / M and d l o ( v ) = d m i d ( v ) = 0 d_{\mathrm{lo}}(v)=d_{\mathrm{mid}}(v)=0 d lo ( v ) = d mid ( v ) = 0 , regardless of whether the edge was sampled. Thus ∣ U ∣ = ∣ N ( v ) ∩ M h i ∣ |U|=|N(v)\cap\mathcal{M}_{\mathrm{hi}}| ∣ U ∣ = ∣ N ( v ) ∩ M hi ∣ after every completed list update.
3. Deferring queries until v v v is processed. Whenever the real execution would check whether A v h i A_v^{\mathrm{hi}} A v hi is empty to decide whether to queue v v v , the simulator puts v v v in its queue without querying S S S , provided v ∉ M v\notin\mathcal{M} v ∈ / M and d l o ( v ) = d m i d ( v ) = 0 d_{\mathrm{lo}}(v)=d_{\mathrm{mid}}(v)=0 d lo ( v ) = d mid ( v ) = 0 . This applies both at initialization and after later changes to the counters or list. Duplicate requests are suppressed. At extraction, if v ∈ M m i d v\in\mathcal{M}_{\mathrm{mid}} v ∈ M mid or d l o ( v ) + d m i d ( v ) > 0 d_{\mathrm{lo}}(v)+d_{\mathrm{mid}}(v)>0 d lo ( v ) + d mid ( v ) > 0 , the simulator discards the request without changing MIS membership or any maintained list and without a query. Otherwise it queries S S S . On a nonempty answer, the simulator discards the request without changing the MIS or any maintained list and continues the game. An empty answer establishes that A v h i A_v^{\mathrm{hi}} A v hi is empty. The algorithm then removes all high-MIS neighbors of v v v from M h i \mathcal{M}_{\mathrm{hi}} M hi and includes v v v in M m i d \mathcal{M}_{\mathrm{mid}} M mid , ending the game.
The two executions can differ only by an extra request for v v v . Processing this request changes neither a maintained list nor MIS membership unless the real execution also needs to process v v v . The queue-coverage and fixed-order argument from the low-vertex case therefore gives the same MIS changes. Since v v v never belongs to C 1 ∪ C 2 C_1\cup C_2 C 1 ∪ C 2 during this game, candidate sets are identical as well. Both executions make the same flush decisions and report the same MISs. If a flush begins, the simulator deletes all entries of U U U and S S S without a query, as described above.
Applying Lemma 3.5 with ∣ U ∣ ≤ ∣ V h i ∣ = O ( m 3 / 8 ) |U|\leq|V_{\mathrm{hi}}|=O(m^{3/8}) ∣ U ∣ ≤ ∣ V hi ∣ = O ( m 3/8 ) gives
∣ A v h i ∣ = O ~ ( p m 3 / 8 ) = O ~ ( m 1 / 8 ) , A v h i = ∅ ⟹ ∣ N ( v ) ∩ M h i ∣ = O ~ ( p − 1 ) = O ~ ( m 1 / 4 ) . |A_v^{\mathrm{hi}}|=\widetilde{O}(pm^{3/8})=\widetilde{O}(m^{1/8}),\qquad A_v^{\mathrm{hi}}=\emptyset\ \Longrightarrow\ |N(v)\cap\mathcal{M}_{\mathrm{hi}}|=\widetilde{O}(p^{-1})=\widetilde{O}(m^{1/4}). ∣ A v hi ∣ = O ( p m 3/8 ) = O ( m 1/8 ) , A v hi = ∅ ⟹ ∣ N ( v ) ∩ M hi ∣ = O ( p − 1 ) = O ( m 1/4 ) .
As for low vertices, these estimates hold after initialization and every completed list update, including immediately before v v v joins M m i d \mathcal{M}_{\mathrm{mid}} M mid .
In both cases, there are polynomially many game operations and initializations. Choosing sufficiently small failure probabilities and taking a union bound over all vertices and all these games proves the simultaneous list-size and empty-list assertions.
Finally, conditional on the history before an initialization, the number of sampled vertices has distribution Bin ( ∣ M h i ∣ , p ) \operatorname{Bin}(|\mathcal{M}_{\mathrm{hi}}|,p) Bin ( ∣ M hi ∣ , p ) , with mean at most p ∣ V h i ∣ = O ( m 1 / 8 ) p|V_{\mathrm{hi}}|=O(m^{1/8}) p ∣ V hi ∣ = O ( m 1/8 ) . A Chernoff bound and a union bound over all calls give O ~ ( m 1 / 8 ) \widetilde{O}(m^{1/8}) O ( m 1/8 ) sampled vertices per initialization, including those rejected by the adjacency test.
Runtime Analysis
We prove the O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) amortized update bound using a potential function. For each completed edge update, we bound the actual running time plus the change in potential. The analysis follows the algorithm’s order: degree migration, edge insertion or deletion, and then maximality restoration in regular mode or flush mode. Throughout the cost analysis, we work on the event that the simultaneous guarantees of Lemmas 4.7 and 4.8 hold. Recall the parameters
b 0 = m 3 / 8 , b 1 = m 5 / 8 , p h i = 1 2 m − 1 / 4 , B = m 1 / 2 . b_0 = m^{3/8}, \qquad b_1 = m^{5/8}, \qquad p_{\mathrm{hi}} = \frac{1}{2}m^{-1/4}, \qquad B = m^{1/2}. b 0 = m 3/8 , b 1 = m 5/8 , p hi = 2 1 m − 1/4 , B = m 1/2 .
The potential and the purpose of its terms. Define
Φ : = W l o ∣ V l o ∖ M ∣ + W m i d ∣ V m i d ∖ M ∣ + W h i ∣ V h i ∖ M ∣ \Phi:= W_{\mathrm{lo}}|V_{\mathrm{lo}} \setminus\mathcal{M}| + W_{\mathrm{mid}}|V_{\mathrm{mid}} \setminus\mathcal{M}| + W_{\mathrm{hi}}|V_{\mathrm{hi}} \setminus\mathcal{M}| Φ := W lo ∣ V lo ∖ M ∣ + W mid ∣ V mid ∖ M ∣ + W hi ∣ V hi ∖ M ∣
+ α ∣ C 1 ∪ C 2 ∣ + β ∣ C 1 ∣ + Θ ( log n ) ∣ Q ∣ , (7) {}+ \alpha|C_1 \cup C_2| + \beta|C_1| + \Theta(\log n)|Q|, \tag*{(7)} + α ∣ C 1 ∪ C 2 ∣ + β ∣ C 1 ∣ + Θ ( log n ) ∣ Q ∣ , (7)
where
W l o = W m i d = Θ ~ ( m 5 / 8 ) , W h i = Θ ~ ( m 3 / 8 ) , W_{\mathrm{lo}} = W_{\mathrm{mid}} = \widetilde{\Theta}(m^{5/8}), \qquad W_{\mathrm{hi}} = \widetilde{\Theta}(m^{3/8}), W lo = W mid = Θ ( m 5/8 ) , W hi = Θ ( m 3/8 ) ,
α = Θ ~ ( m 1 / 4 ) , β = Θ ~ ( m 1 / 8 ) . \alpha= \widetilde{\Theta}(m^{1/4}), \qquad\beta= \widetilde{\Theta}(m^{1/8}). α = Θ ( m 1/4 ) , β = Θ ( m 1/8 ) .
The constants and logarithmic factors will be chosen to cover the costs described below. Each term has a specific purpose:
The first three terms pay for vertices joining the MIS in regular mode. Including a low, middle, or high vertex in the MIS decreases the corresponding term by W l o W_{\mathrm{lo}} W lo , W m i d W_{\mathrm{mid}} W mid , or W h i W_{\mathrm{hi}} W hi , respectively. This decrease pays for its neighborhood scans and any high-MIS removals needed before the vertex joins the MIS.
The term α ∣ C 1 ∪ C 2 ∣ \alpha|C_1 \cup C_2| α ∣ C 1 ∪ C 2 ∣ pays for flushes. We will show that at most O ( m 3 / 8 ) O(m^{3/8}) O ( m 3/8 ) vertices join this union per update. A vertex is counted again if it rejoins during a later update. Each flush removes at least B B B vertices from the union. Transfers between C 1 C_1 C 1 and C 2 C_2 C 2 leave this term unchanged.
The term β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ pays for deleting high domination edge lists when low vertices leave C 1 C_1 C 1 during regular mode.
The term Θ ( log n ) ∣ Q ∣ \Theta(\log n)|Q| Θ ( log n ) ∣ Q ∣ pays for extracting requests and checking whether the requested vertices should join the MIS.
Initially M = V \mathcal{M} = V M = V and C 1 = C 2 = Q = ∅ C_1 = C_2 = Q = \varnothing C 1 = C 2 = Q = ∅ , so Φ = 0 \Phi= 0 Φ = 0 . The potential is always nonnegative. Thus the sum of the amortized costs over all updates upper-bounds their total actual running time.
Accounting for queue operations. We include the cost of issuing a request in the operation that examines the vertex. Testing its counters and domination edge list takes O ( 1 ) O(1) O ( 1 ) time. If the vertex is placed in Q Q Q , the O ( log n ) O(\log n) O ( log n ) cost of placing it there and the Θ ( log n ) \Theta(\log n) Θ ( log n ) potential increase are both included. Each scanned vertex or edge causes only O ( 1 ) O(1) O ( 1 ) requests, so this adds at most an O ( log n ) O(\log n) O ( log n ) factor to the scan’s cost. An attempt to issue a duplicate request changes neither Q Q Q nor the potential.
Extracting or deleting a request decreases the queue term by Θ ( log n ) \Theta(\log n) Θ ( log n ) , which pays for the queue operation and its constant-time tests of MIS membership, exact counters, and the stored high domination edge list, if present, when the coefficient is sufficiently large. The same decrease pays for clearing Q Q Q . Updating a vertex’s position in Q Q Q after degree migration does not change ∣ Q ∣ |Q| ∣ Q ∣ ; its cost is included in that migration.
Preparation Phase
For an update to e = ( s , t ) e=(s,t) e = ( s , t ) , we follow the preparation procedure: first complete any degree migrations of s s s and t t t on the graph before the edge update, then process the edge insertion or deletion using the resulting degree classes. We first upper bound the runtime of each degree migration together with the changes in all potential terms other than β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ . The change in β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ is included when we combine preparation with regular mode or flush mode below. During preparation, ∣ C 1 ∣ |C_1| ∣ C 1 ∣ can increase by O ( b 1 ) O(b_1) O ( b 1 ) , increasing this term by O ( β b 1 ) = O ~ ( m 3 / 4 ) O(\beta b_1)=\widetilde{O}(m^{3/4}) O ( β b 1 ) = O ( m 3/4 ) . If the update enters regular mode, its net increase is instead at most β B \beta B β B ; a flush makes C 1 C_1 C 1 empty and cancels any increase during preparation.
We first bound a list-deletion cost shared by the preparation cases. By Lemma 4.4 , fewer than B B B high domination edge lists are stored at low vertices, and no new ones are initialized during preparation. Deleting each list A w h i A_w^{\mathrm{hi}} A w hi , the entry for every stored edge ( z , x ) (z,x) ( z , x ) in R x h i R_x^{\mathrm{hi}} R x hi , and the list’s entry in the indexed collection takes O ~ ( m 1 / 8 ) \widetilde{O}(m^{1/8}) O ( m 1/8 ) time by Lemma 4.8 .
Lemma 4.9. Each degree migration has cost O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) , where this cost is the actual running time plus the changes in all terms of Φ \Phi Φ other than β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ .
Proof. The potential weights satisfy W l o = W m i d ≥ W h i W_{\mathrm{lo}}=W_{\mathrm{mid}}\ge W_{\mathrm{hi}} W lo = W mid ≥ W hi and b 0 α = O ~ ( m 5 / 8 ) b_0\alpha=\widetilde{O}(m^{5/8}) b 0 α = O ( m 5/8 ) . We analyze the four degree migrations specified in Items (a) to (d). Migration is performed before changing the graph. Since ∣ deg ^ ( w ) − deg ( w ) ∣ = 1 |\widehat{\deg}(w)-\deg(w)|=1 ∣ deg ( w ) − deg ( w ) ∣ = 1 , a migration between the low and middle degree classes scans O ( b 0 ) O(b_0) O ( b 0 ) neighbors, and a migration between the middle and high degree classes scans O ( b 1 ) O(b_1) O ( b 1 ) neighbors. Updating the indexed class sets and issuing requests are included in the bounds below. The second migration uses the classes, counters, and lists produced by the first; each cost and potential change is measured from the state immediately before that migration. Throughout this proof, changes in β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ are deferred until the flush test. Deleting high domination edge lists at low vertices costs at most O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) in total, as established above.
(a) V l o → V m i d V_{\mathrm{lo}}\to V_{\mathrm{mid}} V lo → V mid . Deleting the old high domination edge list A w h i A_w^{\mathrm{hi}} A w hi , if stored, takes O ~ ( m 1 / 8 ) \widetilde{O}(m^{1/8}) O ( m 1/8 ) time by Lemma 4.8 . Next, updating the adjacency lists and, if w ∈ M w\in M w ∈ M , decreasing d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) by one and increasing d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) by one at each neighbor z z z takes O ~ ( b 0 ) \widetilde{O}(b_0) O ( b 0 ) time. Finally, initializing A w h i A_w^{\mathrm{hi}} A w hi in the middle degree class takes O ~ ( m 1 / 8 ) \widetilde{O}(m^{1/8}) O ( m 1/8 ) time, also within this bound. If w ∉ M w\notin M w ∈ / M , the migration decreases W l o ∣ V l o ∖ M ∣ W_{\mathrm{lo}}|V_{\mathrm{lo}}\setminus M| W lo ∣ V lo ∖ M ∣ by W l o W_{\mathrm{lo}} W lo and increases W m i d ∣ V m i d ∖ M ∣ W_{\mathrm{mid}}|V_{\mathrm{mid}}\setminus M| W mid ∣ V mid ∖ M ∣ by W m i d W_{\mathrm{mid}} W mid . These changes cancel because W l o = W m i d W_{\mathrm{lo}}=W_{\mathrm{mid}} W lo = W mid , and removing w w w from C 1 ∪ C 2 C_1\cup C_2 C 1 ∪ C 2 can only decrease α ∣ C 1 ∪ C 2 ∣ \alpha|C_1\cup C_2| α ∣ C 1 ∪ C 2 ∣ . If w ∈ M w\in M w ∈ M , it remains in the MIS, so neither of these two potential terms changes. At most O ( b 0 ) O(b_0) O ( b 0 ) low degree neighbors lose their last low-MIS neighbor and enter C 1 ∪ C 2 C_1\cup C_2 C 1 ∪ C 2 , increasing α ∣ C 1 ∪ C 2 ∣ \alpha|C_1\cup C_2| α ∣ C 1 ∪ C 2 ∣ by O ( b 0 α ) O(b_0\alpha) O ( b 0 α ) . These new candidates belong to C 2 C_2 C 2 , since w w w is now their middle-MIS neighbor. Thus ∣ C 1 ∣ |C_1| ∣ C 1 ∣ does not increase in this migration. Together with the cost of deleting high domination edge lists at low vertices, the actual running time plus the changes in the potential terms considered here is at most O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) .
(b) V m i d → V l o V_{\mathrm{mid}}\to V_{\mathrm{lo}} V mid → V lo . Deleting A w h i A_w^{\mathrm{hi}} A w hi , then scanning N ( w ) N(w) N ( w ) to update the adjacency lists and, if w ∈ M w\in M w ∈ M , increase d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) by one and decrease d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) by one at each neighbor z z z take O ~ ( b 0 ) \widetilde{O}(b_0) O ( b 0 ) time. If w ∈ M w\in M w ∈ M , its low degree neighbors gain a low-MIS neighbor and can only leave the candidate union. The cost of deleting their high domination edge lists is included in the bound above. If w ∉ M w\notin M w ∈ / M , the migration decreases W m i d ∣ V m i d ∖ M ∣ W_{\mathrm{mid}}|V_{\mathrm{mid}}\setminus M| W mid ∣ V mid ∖ M ∣ by W m i d W_{\mathrm{mid}} W mid and increases W l o ∣ V l o ∖ M ∣ W_{\mathrm{lo}}|V_{\mathrm{lo}}\setminus M| W lo ∣ V lo ∖ M ∣ by W l o W_{\mathrm{lo}} W lo . These changes cancel because W l o = W m i d W_{\mathrm{lo}}=W_{\mathrm{mid}} W lo = W mid . Placing w w w in C 1 C_1 C 1 or C 2 C_2 C 2 increases α ∣ C 1 ∪ C 2 ∣ \alpha|C_1\cup C_2| α ∣ C 1 ∪ C 2 ∣ by at most α \alpha α . Only w w w itself can enter C 1 C_1 C 1 , so its size increases by at most one and the increase in β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ is at most β \beta β . Including the list deletions, the actual running time plus the changes in the potential terms considered here is at most O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) .
(c) V m i d → V h i V_{mid} \to V_{hi} V mi d → V hi . Deleting A w h i A^{hi}_w A w hi , updating the adjacency lists, and initializing d h i ( w ) d_{hi}(w) d hi ( w ) take O ~ ( b 1 ) \widetilde{O}(b_1) O ( b 1 ) time. If w ∈ M w \in\mathcal{M} w ∈ M , decreasing d m i d ( z ) d_{mid}(z) d mi d ( z ) by one at every neighbor z z z and increasing d h i ( z ) d_{hi}(z) d hi ( z ) by one at every high degree neighbor z z z also takes O ~ ( b 1 ) \widetilde{O}(b_1) O ( b 1 ) time. In this case, initializing R w R_w R w after w w w enters M h i \mathcal{M}_{hi} M hi by sampling middle vertices and high domination edge lists stored at low vertices takes O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) time by Lemma 4.7, also within this bound. If w ∉ M w \notin\mathcal{M} w ∈ / M , the migration decreases W m i d ∣ V m i d ∖ M ∣ W_{mid}|V_{mid} \setminus\mathcal{M}| W mi d ∣ V mi d ∖ M ∣ by W m i d W_{mid} W mi d and increases W h i ∣ V h i ∖ M ∣ W_{hi}|V_{hi} \setminus\mathcal{M}| W hi ∣ V hi ∖ M ∣ by W h i W_{hi} W hi , for a net change of W h i − W m i d ≤ 0 W_{hi}-W_{mid} \le0 W hi − W mi d ≤ 0 . If w ∈ M w \in\mathcal{M} w ∈ M , neither of these two potential terms changes. Its low degree neighbors may move from C 2 C_2 C 2 to C 1 C_1 C 1 , but this leaves α ∣ C 1 ∪ C 2 ∣ \alpha|C_1 \cup C_2| α ∣ C 1 ∪ C 2 ∣ unchanged. At most deg ( w ) = O ( b 1 ) \deg(w) = O(b_1) deg ( w ) = O ( b 1 ) vertices make this move, so the increase in ∣ C 1 ∣ |C_1| ∣ C 1 ∣ is at most O ( b 1 ) O(b_1) O ( b 1 ) and that in β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ is at most O ( β b 1 ) = O ~ ( m 3 / 4 ) O(\beta b_1) = \widetilde{O}(m^{3/4}) O ( β b 1 ) = O ( m 3/4 ) . Hence the actual running time plus the changes in the other potential terms is at most O ~ ( b 1 ) = O ~ ( m 5 / 8 ) \widetilde{O}(b_1) = \widetilde{O}(m^{5/8}) O ( b 1 ) = O ( m 5/8 ) .
(d) V h i → V m i d V_{hi} \to V_{mid} V hi → V mi d . Updating the adjacency lists takes O ~ ( b 1 ) \widetilde{O}(b_1) O ( b 1 ) time. If w ∈ M w \in\mathcal{M} w ∈ M , deleting R w h i R^{hi}_w R w hi , increasing d m i d ( z ) d_{mid}(z) d mi d ( z ) by one at every neighbor z z z , and decreasing d h i ( z ) d_{hi}(z) d hi ( z ) by one at every high degree neighbor z z z also take O ~ ( b 1 ) \widetilde{O}(b_1) O ( b 1 ) time. Discarding d h i ( w ) d_{hi}(w) d hi ( w ) and then initializing A w h i A^{hi}_w A w hi also fit within this bound. If w ∈ M w \in\mathcal{M} w ∈ M , a low degree neighbor that gains middle domination can move from C 1 C_1 C 1 to C 2 C_2 C 2 . This move preserves the candidate union, and ∣ C 1 ∣ |C_1| ∣ C 1 ∣ cannot increase in this migration. If its high domination edge list is stored, its deletion is included in the bound above; an uninitialized list requires no deletion. If w ∉ M w \notin\mathcal{M} w ∈ / M , the migration decreases W h i ∣ V h i ∖ M ∣ W_{hi}|V_{hi} \setminus\mathcal{M}| W hi ∣ V hi ∖ M ∣ by W h i W_{hi} W hi and increases W m i d ∣ V m i d ∖ M ∣ W_{mid}|V_{mid} \setminus\mathcal{M}| W mi d ∣ V mi d ∖ M ∣ by W m i d W_{mid} W mi d , for a net increase of W m i d − W h i W_{mid}-W_{hi} W mi d − W hi ; w w w does not enter either candidate set. Including the list deletions, the runtime and changes in the potential terms considered here are at most O ~ ( b 1 + m 5 / 8 ) + W m i d − W h i = O ~ ( m 5 / 8 ) \widetilde{O}(b_1 + m^{5/8}) + W_{mid} - W_{hi} = \widetilde{O}(m^{5/8}) O ( b 1 + m 5/8 ) + W mi d − W hi = O ( m 5/8 ) .
These cases account for every operation and every potential term except β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ , proving the lemma.
We now combine the migration costs with the costs of the subsequent edge insertion or deletion and any removal needed to restore independence.
Lemma 4.10. For every graph update, the preparation cost is O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) , where this cost includes the actual running time and the changes in all terms of Φ \Phi Φ other than β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ . This includes the degree migrations, updates to the basic data structures and sampled domination edge lists, all changes to Q Q Q , and removal of one MIS vertex when an insertion violates independence.
Proof. Let e = ( s , t ) e = (s,t) e = ( s , t ) be the inserted or deleted edge. We analyze the algorithm’s steps in execution order.
Degree migration. There is at most one degree migration for each of s , t s,t s , t . For each migration, the actual running time plus the changes in the potential terms other than β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ is at most O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) by Lemma 4.9. Both finish before the graph edge is changed. All costs below use the resulting degree classes and data structures.
Edge insertion. Inserting e e e into G G G changes two adjacency-list entries and at most one exact counter at each of s , t s,t s , t . These first two steps take O ~ ( 1 ) \widetilde{O}(1) O ( 1 ) time.
If both s s s and t t t belong to the MIS, the next step removes a vertex w ∈ { s , t } w \in\{s,t\} w ∈ { s , t } from M \mathcal{M} M : w = t w=t w = t if s ≺ t s \prec t s ≺ t , and w = s w=s w = s otherwise. Thus the earlier vertex under ≺ \prec ≺ remains in the MIS. We consider the degree class of w w w .
If w ∈ V l o w \in V_{lo} w ∈ V l o , both s s s and t t t belong to V l o V_{lo} V l o . Scanning the neighbors of w w w and updating their counters and membership in C 1 C_1 C 1 and C 2 C_2 C 2 take O ~ ( b 0 ) \widetilde{O}(b_0) O ( b 0 ) time, apart from the list deletions already bounded above. The removal increases W l o ∣ V l o ∖ M ∣ W_{lo}|V_{lo} \setminus\mathcal{M}| W l o ∣ V l o ∖ M ∣ by W l o W_{lo} W l o and can introduce O ( b 0 ) O(b_0) O ( b 0 ) new candidates, increasing α ∣ C 1 ∪ C 2 ∣ \alpha|C_1 \cup C_2| α ∣ C 1 ∪ C 2 ∣ by O ( b 0 α ) O(b_0\alpha) O ( b 0 α ) . Including the update to the membership of w w w in C 1 C_1 C 1 and C 2 C_2 C 2 gives
O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) in total. The increase in ∣ C 1 ∣ |C_1| ∣ C 1 ∣ is at most O ( b 0 ) O(b_0) O ( b 0 ) , contributing at most O ( β b 0 ) = O ~ ( m 1 / 2 ) O(\beta b_0)=\widetilde{O}(m^{1/2}) O ( β b 0 ) = O ( m 1/2 ) to the potential.
If w ∈ V m i d w \in V_{\mathrm{mid}} w ∈ V mid , the neighborhood scan takes O ~ ( b 1 ) \widetilde{O}(b_1) O ( b 1 ) time and removing w w w from the MIS increases W m i d ∣ V m i d ∖ M ∣ W_{\mathrm{mid}}|V_{\mathrm{mid}} \setminus\mathcal{M}| W mid ∣ V mid ∖ M ∣ by W m i d W_{\mathrm{mid}} W mid . A low candidate losing its last middle-MIS neighbor moves from C 2 C_2 C 2 to C 1 C_1 C 1 , without changing α ∣ C 1 ∪ C 2 ∣ \alpha|C_1 \cup C_2| α ∣ C 1 ∪ C 2 ∣ . At most deg ( w ) = O ( b 1 ) \deg(w)=O(b_1) deg ( w ) = O ( b 1 ) vertices make this move. Thus ∣ C 1 ∣ |C_1| ∣ C 1 ∣ increases by at most O ( b 1 ) O(b_1) O ( b 1 ) , and β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ increases by at most O ( β b 1 ) = O ~ ( m 3 / 4 ) O(\beta b_1)=\widetilde{O}(m^{3/4}) O ( β b 1 ) = O ( m 3/4 ) . The total for the other terms is again O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) .
If w ∈ V h i w \in V_{\mathrm{hi}} w ∈ V hi , scanning its high degree neighbors and traversing R w h i R_w^{\mathrm{hi}} R w hi each take O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) time. Removing w w w from the MIS increases W h i ∣ V h i ∖ M ∣ W_{\mathrm{hi}}|V_{\mathrm{hi}} \setminus\mathcal{M}| W hi ∣ V hi ∖ M ∣ by W h i W_{\mathrm{hi}} W hi , while d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) , d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) , and candidate membership remain unchanged for every vertex z z z . Thus the actual time plus the potential increase is O ( W h i ) O(W_{\mathrm{hi}}) O ( W hi ) , including all requests placed in Q Q Q .
Finally, the algorithm recomputes the membership of each low degree endpoint in C 1 C_1 C 1 and C 2 C_2 C 2 from its updated counters and MIS-membership bit and samples the new edge if it joins a current high-MIS vertex to a vertex with a stored high domination edge list. Apart from the MIS removal already counted, increasing the counters at s s s or t t t can only remove that vertex from C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 or move that vertex from C 1 C_1 C 1 to C 2 C_2 C 2 . The cost of deleting high domination edge lists at low vertices is included in the O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) bound above. Sampling the new edge stores at most two copies and takes O ~ ( 1 ) \widetilde{O}(1) O ( 1 ) time. The sampling decision uses the endpoints’ MIS memberships after independence has been restored.
Edge deletion. If a sampled copy of e e e is stored in A z h i A_z^{\mathrm{hi}} A z hi for z ∈ { s , t } z \in\{s,t\} z ∈ { s , t } , the algorithm first deletes both sampled copies and tests z z z for a request. It then removes e e e from the adjacency lists and adjacency dictionaries and decrements the exact counters at s s s and t t t . Finally, it recomputes the membership of each low degree endpoint in C 1 C_1 C 1 and C 2 C_2 C 2 from its updated counters and MIS-membership bit and tests both vertices for a request. These steps take O ~ ( 1 ) \widetilde{O}(1) O ( 1 ) time. One of s , t s,t s , t may enter the candidate union, increasing α ∣ C 1 ∪ C 2 ∣ \alpha|C_1 \cup C_2| α ∣ C 1 ∪ C 2 ∣ by at most α \alpha α . A move from C 2 C_2 C 2 to C 1 C_1 C 1 leaves the union unchanged. Only the vertex losing an MIS neighbor can enter C 1 C_1 C 1 , so ∣ C 1 ∣ |C_1| ∣ C 1 ∣ increases by at most one and β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ by at most β \beta β . High domination edge lists at vertices entering C 1 C_1 C 1 are initialized only after the flush test, if the update enters regular mode.
Adding the migration costs and the subsequent insertion or deletion cost proves the lemma. The explicit bounds above also show that preparation increases ∣ C 1 ∣ |C_1| ∣ C 1 ∣ by at most O ( b 1 ) = O ( m 5 / 8 ) O(b_1)=O(m^{5/8}) O ( b 1 ) = O ( m 5/8 ) : there are at most two migrations and one edge update.
Maximality Restoration
We begin by bounding how much the candidate sets can grow during one edge update.
Lemma 4.11. During any single edge update, the number of vertices that do not belong to C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 at the beginning of the update but subsequently join C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 is O ( b 0 ) = O ( m 3 / 8 ) O(b_0)=O(m^{3/8}) O ( b 0 ) = O ( m 3/8 ) . Consequently, throughout the update, the size of C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 is at most its size at the beginning of the update plus O ( m 3 / 8 ) O(m^{3/8}) O ( m 3/8 ) .
Proof. Let e = ( s , t ) e=(s,t) e = ( s , t ) be the updated edge. Moving a vertex from C 1 C_1 C 1 to C 2 C_2 C 2 , or from C 2 C_2 C 2 to C 1 C_1 C 1 , does not increase the size of their union. We therefore count only vertices that join C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 from outside the union. We consider all places in the update procedure where a vertex can join the union.
The preparation stage. First consider degree migration. Only s s s and t t t can change degree class, so entry into the low degree class introduces at most two candidates. When a vertex
in { s , t } ∩ M l o \{s,t\} \cap\mathcal{M}_{\mathrm{lo}} { s , t } ∩ M lo migrates to the middle degree class, its scan can additionally make d l o ( z ) = 0 d_{\mathrm{lo}}(z)=0 d lo ( z ) = 0 for O ( b 0 ) O(b_0) O ( b 0 ) low degree neighbors. The other migrations do not introduce any further member of C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 . Next consider the edge update. An insertion can remove at most one vertex from M l o \mathcal{M}_{\mathrm{lo}} M lo , causing at most O ( b 0 ) O(b_0) O ( b 0 ) low degree neighbors to enter the union; the other insertion cases only move or remove candidates. A deletion can introduce a candidate only at s s s or t t t . Thus preparation introduces O ( b 0 ) O(b_0) O ( b 0 ) vertices into the union.
(b) A low vertex extracted from Q Q Q . If the extracted vertex v v v already belongs to M \mathcal{M} M , satisfies d l o ( v ) + d m i d ( v ) > 0 d_{\mathrm{lo}}(v)+d_{\mathrm{mid}}(v)>0 d lo ( v ) + d mid ( v ) > 0 , or has a nonempty stored list A v h i A_v^{\mathrm{hi}} A v hi , the iteration ends without changing the candidate sets. Otherwise, the algorithm includes v v v in M l o \mathcal{M}_{\mathrm{lo}} M lo and removes v v v and its low degree neighbors from the candidate union. Thus a low iteration introduces no new member of C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 .
(c) A middle vertex extracted from Q Q Q . A middle vertex never belongs to either candidate set. When processing its request, the algorithm may include it in M m i d \mathcal{M}_{\mathrm{mid}} M mid , which can only move low candidates from C 1 C_1 C 1 to C 2 C_2 C 2 . Thus a middle iteration creates no candidate.
(d) A high vertex extracted from Q Q Q . This case never causes a vertex to join either candidate set. The algorithm either discards the request or includes the vertex in M h i \mathcal{M}_{\mathrm{hi}} M hi .
(e) Flush mode. The low and middle passes remove candidates or move them between the two sets, and the final reconstruction of the high layer creates no candidate. Thus flush mode creates no additional source of candidates.
Combining the contributions of s , t s,t s , t and the O ( b 0 ) O(b_0) O ( b 0 ) low vertices that can lose their last low-MIS neighbor during preparation proves the lemma.
The distinction between C 1 C_1 C 1 and C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 is essential here. Removing one vertex from M m i d \mathcal{M}_{\mathrm{mid}} M mid can move O ( b 1 ) O(b_1) O ( b 1 ) vertices from C 2 C_2 C 2 to C 1 C_1 C 1 , but these moves do not increase the union or its contribution α ∣ C 1 ∪ C 2 ∣ \alpha|C_1 \cup C_2| α ∣ C 1 ∪ C 2 ∣ to the potential.
After preparation, testing ∣ C 1 ∣ ≥ B |C_1| \ge B ∣ C 1 ∣ ≥ B takes O ( 1 ) O(1) O ( 1 ) time. If the test fails, then ∣ C 1 ∣ < B |C_1| < B ∣ C 1 ∣ < B . Thus the net increase in β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ from the beginning of the update to the start of regular mode is at most β B \beta B β B , regardless of how many vertices moved between C 1 C_1 C 1 and C 2 C_2 C 2 during preparation. The algorithm initializes the missing high domination edge lists at vertices in C 1 C_1 C 1 . There are fewer than B B B such vertices, and each initialization takes O ~ ( m 1 / 8 ) \widetilde{O}(m^{1/8}) O ( m 1/8 ) time without changing either candidate set. Including the change in β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ , enumeration of C 1 C_1 C 1 , and all requests gives
O ~ ( B ( m 1 / 8 + β ) ) = O ~ ( m 5 / 8 ) . (8) \widetilde{O}\bigl(B(m^{1/8}+\beta)\bigr)=\widetilde{O}(m^{5/8}). \tag*{(8)} O ( B ( m 1/8 + β ) ) = O ( m 5/8 ) . (8)
The algorithm makes no such initializations if the test succeeds. During regular mode C 1 C_1 C 1 can only shrink, so there are no further initializations of high domination edge lists at low vertices.
The next three lemmas analyze regular-mode extractions. In each case, we use the following bound for candidate-set changes: a low vertex z z z 's departure from C 1 C_1 C 1 decreases β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ by β \beta β , paying for deleting its list A z h i A_z^{\mathrm{hi}} A z hi , the entry for every stored edge ( z , x ) (z,x) ( z , x ) in R x z h i R_{xz}^{\mathrm{hi}} R x z hi , and the list's entry in the indexed collection in O ~ ( m 1 / 8 ) \widetilde{O}(m^{1/8}) O ( m 1/8 ) time by Lemma 4.8. Apart from these deletions, updating membership in C 1 C_1 C 1 and C 2 C_2 C 2 takes O ( log n ) O(\log n) O ( log n ) time.
Regular mode: extracting a low vertex. We next analyze the amortized runtime of processing a vertex of Q ∩ V l o Q \cap V_{\mathrm{lo}} Q ∩ V lo .
Lemma 4.12. Extracting any v ∈ V l o v \in V_{\mathrm{lo}} v ∈ V lo from Q Q Q and completing its regular-mode iteration has nonpositive amortized cost: the actual running time plus the change in Φ \Phi Φ is nonpositive.
Proof. We follow the low-vertex case of the restoration procedure. Every iteration starts by extracting v v v , which decreases ∣ Q ∣ |Q| ∣ Q ∣ by one and pays for the queue operation and its constant-time MIS-membership, counter, and list tests.
No change to M l o \mathcal{M}_{\mathrm{lo}} M lo . If v ∈ M v \in\mathcal{M} v ∈ M , d l o ( v ) + d m i d ( v ) > 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) > 0 d lo ( v ) + d mid ( v ) > 0 , or A v h i ≠ ∅ A^{\mathrm{hi}}_v \ne\varnothing A v hi = ∅ , the algorithm stops processing this request without changing any candidate set or domination edge list and continues with the next request in Q Q Q , if any. Thus this case creates no positive potential change.
v v v joins M l o \mathcal{M}_{\mathrm{lo}} M lo . It remains to consider d l o ( v ) = d m i d ( v ) = 0 d_{\mathrm{lo}}(v) = d_{\mathrm{mid}}(v) = 0 d lo ( v ) = d mid ( v ) = 0 and A v h i = ∅ A^{\mathrm{hi}}_v = \varnothing A v hi = ∅ . First, scanning N ( v ) N(v) N ( v ) to find X h i = N ( v ) ∩ M h i X_{\mathrm{hi}} = N(v) \cap\mathcal{M}_{\mathrm{hi}} X hi = N ( v ) ∩ M hi takes O ~ ( b 0 ) \widetilde{O}(b_0) O ( b 0 ) time. By (6), ∣ X h i ∣ = O ~ ( m 1 / 4 ) |X_{\mathrm{hi}}| = \widetilde{O}(m^{1/4}) ∣ X hi ∣ = O ( m 1/4 ) . Next, remove each x ∈ X h i x \in X_{\mathrm{hi}} x ∈ X hi from M h i \mathcal{M}_{\mathrm{hi}} M hi . This scans its high degree neighbors and traverses R x h i R^{\mathrm{hi}}_x R x hi . Each examined vertex or sampled edge can cause at most one new request, so removing x x x from M h i \mathcal{M}_{\mathrm{hi}} M hi places at most ∣ N ( x ) ∩ V h i ∣ + ∣ R x h i ∣ = O ~ ( m 3 / 8 ) |N(x) \cap V_{\mathrm{hi}}| + |R^{\mathrm{hi}}_x| = \widetilde{O}(m^{3/8}) ∣ N ( x ) ∩ V hi ∣ + ∣ R x hi ∣ = O ( m 3/8 ) vertices in Q Q Q . Each new request costs O ( log n ) O(\log n) O ( log n ) time and increases the queue term of Φ \Phi Φ by Θ ( log n ) \Theta(\log n) Θ ( log n ) ; duplicate requests do not increase it. Thus the total increase in the queue term is at most
O ( log n ) ∑ x ∈ X h i ( ∣ N ( x ) ∩ V h i ∣ + ∣ R x h i ∣ ) = O ~ ( ∣ X h i ∣ m 3 / 8 ) . O(\log n) \sum_{x \in X_{\mathrm{hi}}} \left(|N(x) \cap V_{\mathrm{hi}}| + |R^{\mathrm{hi}}_x|\right) = \widetilde{O}(|X_{\mathrm{hi}}|m^{3/8}). O ( log n ) x ∈ X hi ∑ ( ∣ N ( x ) ∩ V hi ∣ + ∣ R x hi ∣ ) = O ( ∣ X hi ∣ m 3/8 ) . Including this increase, the queue-operation time, the scans, and the increase of W h i W_{\mathrm{hi}} W hi when x x x leaves the MIS, each removal costs O ( W h i ) O(W_{\mathrm{hi}}) O ( W hi ) .
Finally, including v v v in M l o \mathcal{M}_{\mathrm{lo}} M lo decreases W l o ∣ V l o ∖ M ∣ W_{\mathrm{lo}}|V_{\mathrm{lo}} \setminus\mathcal{M}| W lo ∣ V lo ∖ M ∣ by W l o W_{\mathrm{lo}} W lo , and the subsequent scan of N ( v ) N(v) N ( v ) to increment the exact low counters takes O ~ ( b 0 ) \widetilde{O}(b_0) O ( b 0 ) time. These counter increases and the subsequent candidate removals create no new requests, since including v v v in M l o \mathcal{M}_{\mathrm{lo}} M lo only increases domination. Removing v v v and its low degree neighbors from the candidate union can only decrease α ∣ C 1 ∪ C 2 ∣ \alpha|C_1 \cup C_2| α ∣ C 1 ∪ C 2 ∣ , and the separate decrease of β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ pays for each discarded high domination edge list. No vertex leaves M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid , so no new candidate enters the union. Consequently,
actual time + Δ Φ ≤ − W l o + O ~ ( b 0 ) + O ~ ( m 1 / 4 ) O ( W h i ) ≤ 0 \text{actual time} + \Delta\Phi\le-W_{\mathrm{lo}} + \widetilde{O}(b_0) + \widetilde{O}(m^{1/4})O(W_{\mathrm{hi}}) \le0 actual time + ΔΦ ≤ − W lo + O ( b 0 ) + O ( m 1/4 ) O ( W hi ) ≤ 0 for a sufficiently large coefficient and polylogarithmic factor in W l o = Θ ~ ( m 5 / 8 ) W_{\mathrm{lo}} = \widetilde{\Theta}(m^{5/8}) W lo = Θ ( m 5/8 ) .
Regular mode: extracting a middle vertex. We now analyze the regular-mode iterations in which the extracted vertex belongs to V m i d V_{\mathrm{mid}} V mid .
Lemma 4.13. Extracting any v ∈ V m i d v \in V_{\mathrm{mid}} v ∈ V mid from Q Q Q and completing its regular-mode iteration has nonpositive amortized cost.
Proof. We follow the middle-vertex case of the restoration procedure. Every iteration starts by extracting v v v , which decreases ∣ Q ∣ |Q| ∣ Q ∣ by one and pays for the queue operation.
No change to M m i d \mathcal{M}_{\mathrm{mid}} M mid . The MIS-membership, counter, and list tests take O ~ ( 1 ) \widetilde{O}(1) O ( 1 ) time. If v ∈ M v \in\mathcal{M} v ∈ M , d l o ( v ) + d m i d ( v ) > 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) > 0 d lo ( v ) + d mid ( v ) > 0 , or A v h i ≠ ∅ A^{\mathrm{hi}}_v \ne\varnothing A v hi = ∅ , the algorithm stops processing this request without changing any candidate set or domination edge list and continues with the next request in Q Q Q , if any. The decrease in ∣ Q ∣ |Q| ∣ Q ∣ pays for all tests.
v v v joins M m i d \mathcal{M}_{\mathrm{mid}} M mid . We have d l o ( v ) + d m i d ( v ) = 0 d_{\mathrm{lo}}(v) + d_{\mathrm{mid}}(v) = 0 d lo ( v ) + d mid ( v ) = 0 and A v h i = ∅ A^{\mathrm{hi}}_v = \varnothing A v hi = ∅ . First, scanning N ( v ) N(v) N ( v ) to find X h i = N ( v ) ∩ M h i X_{\mathrm{hi}} = N(v) \cap\mathcal{M}_{\mathrm{hi}} X hi = N ( v ) ∩ M hi takes O ~ ( b 1 ) \widetilde{O}(b_1) O ( b 1 ) time. Next, by (6), the actual runtime of removing every vertex of X h i X_{\mathrm{hi}} X hi from M h i \mathcal{M}_{\mathrm{hi}} M hi , scanning its vertices’ high degree neighbors, and deleting their reverse lists, plus the resulting potential increase, is
O ( ∣ X h i ∣ W h i ) = O ~ ( m 1 / 4 ) O ( W h i ) . O(|X_{\mathrm{hi}}|W_{\mathrm{hi}}) = \widetilde{O}(m^{1/4})O(W_{\mathrm{hi}}). O ( ∣ X hi ∣ W hi ) = O ( m 1/4 ) O ( W hi ) .
This includes the queue-operation time and the potential increase from every new request, as calculated in Lemma 4.12. Finally, including v v v in M m i d \mathcal{M}_{\mathrm{mid}} M mid decreases W m i d ∣ V m i d ∖ M ∣ W_{\mathrm{mid}}|V_{\mathrm{mid}} \setminus\mathcal{M}| W mid ∣ V mid ∖ M ∣ by W m i d W_{\mathrm{mid}} W mid . The algorithm then scans every neighbor z ∈ N ( v ) z \in N(v) z ∈ N ( v ) , including low degree neighbors, and increments d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) . This takes O ~ ( b 1 ) \widetilde{O}(b_1) O ( b 1 ) time. For every low degree neighbor moved from C 1 C_1 C 1 to C 2 C_2 C 2 , the candidate union is unchanged and β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ decreases by β \beta β . This decrease pays for deleting A z h i A_z^{\mathrm{hi}} A z hi and the entry for every stored edge ( z , x ) (z,x) ( z , x ) in R x h i R_x^{\mathrm{hi}} R x hi . Choosing a sufficiently large coefficient and polylogarithmic factor in W m i d W_{\mathrm{mid}} W mid gives
actual time + Δ Φ ≤ − W m i d + O ~ ( b 1 ) + O ~ ( m 1 / 4 ) O ( W h i ) ≤ 0. \text{actual time}+\Delta\Phi\le-W_{\mathrm{mid}}+\widetilde{O}(b_1)+\widetilde{O}(m^{1/4})O(W_{\mathrm{hi}})\le0. actual time + ΔΦ ≤ − W mid + O ( b 1 ) + O ( m 1/4 ) O ( W hi ) ≤ 0.
Regular mode: extracting a high vertex. We finally analyze the regular-mode iterations in which the extracted vertex belongs to V h i V_{\mathrm{hi}} V hi .
Lemma 4.14. Extracting any v ∈ V h i v \in V_{\mathrm{hi}} v ∈ V hi from Q Q Q and completing its regular-mode iteration has non-positive amortized cost.
Proof. We again follow the cases in the restoration procedure. Every iteration starts by extracting v v v , which decreases ∣ Q ∣ |Q| ∣ Q ∣ by one and pays for the queue operation and its constant-time MIS-membership and counter tests.
Vertex v v v is already in the MIS or dominated. The algorithm checks the membership bit and the three exact counters. If v ∈ M v \in\mathcal{M} v ∈ M or d l o ( v ) + d m i d ( v ) + d h i ( v ) > 0 d_{\mathrm{lo}}(v)+d_{\mathrm{mid}}(v)+d_{\mathrm{hi}}(v)>0 d lo ( v ) + d mid ( v ) + d hi ( v ) > 0 , it performs no adjacency scan and changes no counter, candidate set, MIS layer, or domination edge list. The only potential change is the decrease of Θ ( log n ) ∣ Q ∣ \Theta(\log n)|Q| Θ ( log n ) ∣ Q ∣ , which pays for the iteration.
v v v joins M h i \mathcal{M}_{\mathrm{hi}} M hi . Otherwise all three exact counters equal zero, so v v v can be included in M h i \mathcal{M}_{\mathrm{hi}} M hi . This decreases the potential by W h i W_{\mathrm{hi}} W hi . Scanning its high degree neighbors and updating their counters take O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) time. By Lemma 4.7, initializing R v h i R_v^{\mathrm{hi}} R v hi takes O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) time as well. No vertex is removed from the MIS, and neither candidate term increases. With a sufficiently large coefficient in W h i W_{\mathrm{hi}} W hi , its decrease pays for the entire iteration.
Summing these three lemmas shows that regular queue processing has nonpositive amortized cost. Together with Lemma 4.10 and (8), this bounds the entire update, including the change in Φ \Phi Φ , by O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) whenever the update uses regular mode.
Flush mode. We first bound the decrease in the size of the candidate union. We then follow the flush steps in order: copy C 1 C_1 C 1 and clear Q Q Q and M h i \mathcal{M}_{\mathrm{hi}} M hi , process the low and middle vertices, and reconstruct M h i \mathcal{M}_{\mathrm{hi}} M hi .
Lemma 4.15. Let C 1 0 C_1^0 C 1 0 be the set C 1 C_1 C 1 at the start of a flush. Every vertex of C 1 0 C_1^0 C 1 0 leaves C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 during its low pass, and no new vertex enters this union during the flush. Its size decreases by at least ∣ C 1 0 ∣ ≥ B |C_1^0| \ge B ∣ C 1 0 ∣ ≥ B .
Proof. Clearing Q Q Q and M h i \mathcal{M}_{\mathrm{hi}} M hi changes neither candidate set. Every vertex v ∈ C 1 0 v \in C_1^0 v ∈ C 1 0 has d l o ( v ) = d m i d ( v ) = 0 d_{\mathrm{lo}}(v)=d_{\mathrm{mid}}(v)=0 d lo ( v ) = d mid ( v ) = 0 at the start of the flush. The middle MIS remains unchanged during the low pass, so each vertex either already has a low-MIS neighbor when visited or is included in the low MIS. Both outcomes remove it from the candidate union. There are no class changes or removals from M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid during the flush, so these departures persist and no new low vertex can lose its last low-MIS neighbor. The later middle and high passes do not change this conclusion.
Flush mode: copying C 1 0 C_1^0 C 1 0 and clearing Q Q Q and M h i \mathcal{M}_{\mathrm{hi}} M hi .
Lemma 4.16. For Step (1) , the actual running time plus the change in Φ \Phi Φ is at most
O ~ ( ∣ C 1 0 ∣ ) + O ( ∣ V h i ∣ W h i ) = O ~ ( ∣ C 1 0 ∣ + m 3 / 4 ) , \widetilde{O}(|C_1^0|) + O(|V_{\mathrm{hi}}|W_{\mathrm{hi}}) = \widetilde{O}(|C_1^0| + m^{3/4}), O ( ∣ C 1 0 ∣ ) + O ( ∣ V hi ∣ W hi ) = O ( ∣ C 1 0 ∣ + m 3/4 ) , and the step does not change C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 .
Proof. Making the copy C 1 0 C_1^0 C 1 0 of C 1 C_1 C 1 takes O ~ ( ∣ C 1 0 ∣ ) \widetilde{O}(|C_1^0|) O ( ∣ C 1 0 ∣ ) time. Clearing Q Q Q is paid for by the decrease in Θ ( log n ) ∣ Q ∣ \Theta(\log n)|Q| Θ ( log n ) ∣ Q ∣ .
The algorithm then removes every vertex of M h i \mathcal{M}_{\mathrm{hi}} M hi from the MIS. The degree bound for V h i V_{\mathrm{hi}} V hi gives ∣ V h i ∣ = O ( m 3 / 8 ) |V_{\mathrm{hi}}| = O(m^{3/8}) ∣ V hi ∣ = O ( m 3/8 ) . Removing these vertices from M h i \mathcal{M}_{\mathrm{hi}} M hi increases W h i ∣ V h i ∖ M ∣ W_{\mathrm{hi}}|V_{\mathrm{hi}} \setminus\mathcal{M}| W hi ∣ V hi ∖ M ∣ by at most ∣ V h i ∣ W h i |V_{\mathrm{hi}}|W_{\mathrm{hi}} ∣ V hi ∣ W hi . Removing each vertex x x x from M h i \mathcal{M}_{\mathrm{hi}} M hi requires scanning its high degree neighbors and traversing its reverse high domination edge list in O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) time. Thus both stored entries of every sampled edge are removed from the domination edge lists within O ( ∣ V h i ∣ W h i ) O(|V_{\mathrm{hi}}|W_{\mathrm{hi}}) O ( ∣ V hi ∣ W hi ) time. Finally, discarding the empty high domination edge lists at low vertices and their entries in the indexed collection takes O ~ ( ∣ C 1 0 ∣ ) \widetilde{O}(|C_1^0|) O ( ∣ C 1 0 ∣ ) time, since each such list belongs to a vertex of C 1 0 C_1^0 C 1 0 . For every vertex z z z , this step changes neither d l o ( z ) d_{\mathrm{lo}}(z) d lo ( z ) nor d m i d ( z ) d_{\mathrm{mid}}(z) d mid ( z ) nor candidate membership.
Flush mode: processing low and middle vertices. Every existing member of M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid remains in the MIS during the low and middle passes.
Lemma 4.17. After Step (1) , the low and middle passes have amortized cost at most the following quantity, including their changes in Φ \Phi Φ :
− ( α + β ) ∣ C 1 0 ∣ + O ~ ( ∣ C 1 0 ∣ + m 5 / 8 ) . -(\alpha+ \beta)|C_1^0| + \widetilde{O}(|C_1^0| + m^{5/8}). − ( α + β ) ∣ C 1 0 ∣ + O ( ∣ C 1 0 ∣ + m 5/8 ) . Proof. At the start of these passes, the high MIS is empty and no high domination edge list is stored at a low vertex. First, traversing C 1 0 C_1^0 C 1 0 in Step (2) takes O ~ ( ∣ C 1 0 ∣ ) \widetilde{O}(|C_1^0|) O ( ∣ C 1 0 ∣ ) time. For each vertex that joins M l o \mathcal{M}_{\mathrm{lo}} M lo , the algorithm scans O ( b 0 ) O(b_0) O ( b 0 ) neighbors and decreases W l o ∣ V l o ∖ M ∣ W_{\mathrm{lo}}|V_{\mathrm{lo}} \setminus\mathcal{M}| W lo ∣ V lo ∖ M ∣ by W l o W_{\mathrm{lo}} W lo . This decrease pays for the scan and exact counter updates. Next, traversing V m i d V_{\mathrm{mid}} V mid in Step (3) takes O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) time. For each vertex that joins M m i d \mathcal{M}_{\mathrm{mid}} M mid , the algorithm scans O ( b 1 ) O(b_1) O ( b 1 ) neighbors and decreases W m i d ∣ V m i d ∖ M ∣ W_{\mathrm{mid}}|V_{\mathrm{mid}} \setminus\mathcal{M}| W mid ∣ V mid ∖ M ∣ by W m i d W_{\mathrm{mid}} W mid . This decrease again pays for the scan and counter updates. A vertex already in the MIS or dominated requires only the constant-time tests included in these traversal costs. No vertex of M l o ∪ M m i d \mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}} M lo ∪ M mid is removed during either pass.
By Lemma 4.15, every vertex of C 1 0 C_1^0 C 1 0 leaves C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 , and no new vertex enters the union. Thus α ∣ C 1 ∪ C 2 ∣ \alpha|C_1 \cup C_2| α ∣ C 1 ∪ C 2 ∣ decreases by at least α ∣ C 1 0 ∣ \alpha|C_1^0| α ∣ C 1 0 ∣ . Moreover, C 1 C_1 C 1 becomes empty, so β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ decreases by β ∣ C 1 0 ∣ \beta|C_1^0| β ∣ C 1 0 ∣ . Combining these decreases with the traversal costs proves the lemma.
Flush mode: reconstructing the high layer. After the low and middle passes, Q = C 1 = ∅ Q = C_1 = \emptyset Q = C 1 = ∅ . The degree classes and every list E z h i E_z^{\mathrm{hi}} E z hi were already updated during preparation, so the flush does not rebuild these adjacency lists.
Lemma 4.18. For Step (4) , the actual running time plus the change in Φ \Phi Φ is at most
O ( ∣ V h i ∣ W h i ) = O ~ ( m 3 / 4 ) . O(|V_{\mathrm{hi}}|W_{\mathrm{hi}}) = \widetilde{O}(m^{3/4}). O ( ∣ V hi ∣ W hi ) = O ( m 3/4 ) . These operations do not change C 1 ∪ C 2 C_1 \cup C_2 C 1 ∪ C 2 .
Proof. After the low and middle passes, the algorithm scans E z h i \mathcal{E}^{\mathrm{hi}}_z E z hi for high vertices z z z to construct a greedy MIS of
G [ V h i ∖ N ( M l o ∪ M m i d ) ] . G[V_{\mathrm{hi}} \setminus N(\mathcal{M}_{\mathrm{lo}} \cup\mathcal{M}_{\mathrm{mid}})]. G [ V hi ∖ N ( M lo ∪ M mid )] .
The same pass updates d h i ( w ) d_{\mathrm{hi}}(w) d hi ( w ) for every high vertex w w w . Its runtime is
O ~ ( ∣ V h i ∣ + ∣ V h i ∣ 2 ) = O ~ ( m 3 / 4 ) . \widetilde{O}(|V_{\mathrm{hi}}| + |V_{\mathrm{hi}}|^2) = \widetilde{O}(m^{3/4}). O ( ∣ V hi ∣ + ∣ V hi ∣ 2 ) = O ( m 3/4 ) .
Each vertex included in the rebuilt M h i \mathcal{M}_{\mathrm{hi}} M hi decreases W h i ∣ V h i ∖ M ∣ W_{\mathrm{hi}}|V_{\mathrm{hi}} \setminus\mathcal{M}| W hi ∣ V hi ∖ M ∣ by W h i W_{\mathrm{hi}} W hi , so omitting these decreases only makes the upper bound larger.
For every vertex x x x selected for the rebuilt M h i \mathcal{M}_{\mathrm{hi}} M hi , apply Lemma 3.1 to V m i d V_{\mathrm{mid}} V mid with probability p h i p_{\mathrm{hi}} p hi and test adjacency for every returned vertex. By Lemma 4.7, this takes O ~ ( m 3 / 8 ) \widetilde{O}(m^{3/8}) O ( m 3/8 ) time per vertex. For each returned z z z adjacent to x x x , store an entry for ( z , x ) (z,x) ( z , x ) in both R x h i R^{\mathrm{hi}}_x R x hi and A z h i A^{\mathrm{hi}}_z A z hi . Thus reconstruction of the sampled lists also takes O ~ ( ∣ V h i ∣ m 3 / 8 ) ⊆ O ( ∣ V h i ∣ W h i ) \widetilde{O}(|V_{\mathrm{hi}}|m^{3/8}) \subseteq O(|V_{\mathrm{hi}}|W_{\mathrm{hi}}) O ( ∣ V hi ∣ m 3/8 ) ⊆ O ( ∣ V hi ∣ W hi ) time. Since C 1 = ∅ C_1 = \emptyset C 1 = ∅ , no high domination edge list at a low vertex is initialized. No scan of all graph edges is required. □ \square □
Lemma 4.19. For a flush, the actual running time plus the change in Φ \Phi Φ is at most − β ∣ C 1 0 ∣ -\beta|C^0_1| − β ∣ C 1 0 ∣ .
Proof. The operations in Lemmas 4.16 to 4.18 account for the entire flush in execution order. Adding their bounds gives
actual time + Δ Φ ≤ − ( α + β ) ∣ C 1 0 ∣ + O ~ ( ∣ C 1 0 ∣ + m 3 / 4 ) . \text{actual time} + \Delta\Phi\leq-(\alpha+\beta)|C^0_1| + \widetilde{O}(|C^0_1| + m^{3/4}). actual time + ΔΦ ≤ − ( α + β ) ∣ C 1 0 ∣ + O ( ∣ C 1 0 ∣ + m 3/4 ) .
The flush starts only when ∣ C 1 0 ∣ ≥ B |C^0_1| \geq B ∣ C 1 0 ∣ ≥ B , and
α B = Θ ~ ( m 1 / 4 + 1 / 2 ) = Θ ~ ( m 3 / 4 ) . \alpha B = \widetilde{\Theta}(m^{1/4+1/2}) = \widetilde{\Theta}(m^{3/4}). α B = Θ ( m 1/4 + 1/2 ) = Θ ( m 3/4 ) .
A sufficiently large coefficient and polylogarithmic factor in α \alpha α therefore make the displayed amortized cost at most − β ∣ C 1 0 ∣ -\beta|C^0_1| − β ∣ C 1 0 ∣ . □ \square □
The increase in β ∣ C 1 ∣ \beta|C_1| β ∣ C 1 ∣ during preparation is at most β ∣ C 1 0 ∣ \beta|C^0_1| β ∣ C 1 0 ∣ , since C 1 = C 1 0 C_1 = C^0_1 C 1 = C 1 0 when the flush starts. Lemma 4.19 cancels this increase. Together with Lemma 4.10, it follows that, for an update using flush mode, the actual running time plus the change in Φ \Phi Φ is at most O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) .
Coefficients of the potential. First choose a sufficiently large constant in the queue term Θ ( log n ) ∣ Q ∣ \Theta(\log n)|Q| Θ ( log n ) ∣ Q ∣ . Then choose the constants and logarithmic factors successively for β \beta β , W h i W_{\mathrm{hi}} W hi , α \alpha α , and W l o = W m i d W_{\mathrm{lo}} = W_{\mathrm{mid}} W lo = W mid . The queue coefficient pays for extractions and tests of MIS membership and domination; β \beta β pays for deleting a high domination edge list at a low vertex during regular mode; and W h i W_{\mathrm{hi}} W hi pays for including a vertex in the high MIS. The choice of α \alpha α then pays for a flush, and W l o W_{\mathrm{lo}} W lo and W m i d W_{\mathrm{mid}} W mid pay for neighborhood scans and for removing high-MIS neighbors from M h i \mathcal{M}_{\mathrm{hi}} M hi before vertices join M l o \mathcal{M}_{\mathrm{lo}} M lo and M m i d \mathcal{M}_{\mathrm{mid}} M mid , respectively. All these choices have the stated exponents. Any additional polylogarithmic sampling cost can be absorbed by a common factor in these weights.
Proof of Theorem 1.1. Correctness follows from Lemma 4.6. By Lemmas 4.7 and 4.8, the sampling bounds used in the running-time analysis hold with high probability against adaptive adversaries. Combining Lemmas 4.10, 4.12 to 4.14 and 4.19 gives O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) amortized update time. □ \square □
Acknowledgment
This research is supported by the Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (No. JYB2025XDXM118) and the “111 Center” (No. B26023).
Disclosure of AI Use
Table 1.
Details (elaborating on the points above).
Asking the research question. The authors formulated the research question and set the objective of improving the update time for fully dynamic MIS against adaptive adversaries.
Coming up with the main approach. The authors developed the main algorithmic ideas, including the layered candidate construction and adaptive sampling framework.
Developing the main proof ideas. The authors developed the main proof ideas, including the probabilistic games for adaptivity analysis and the potential-based amortized analysis. GPT assisted in refining and checking the details of these arguments.
Writing and exposition. GPT assisted with drafting and editing the manuscript, including the overview, detailed algorithm, proofs, and figures.
Checking for bugs. GPT assisted in discovering bugs in earlier versions of the adaptivity analysis.
Other supporting tasks. The authors initially developed an algorithm with amortized update time O ~ ( m 2 / 3 − 1 / 54 ) \widetilde{O}(m^{2/3-1/54}) O ( m 2/3 − 1/54 ) . OpenAI GPT subsequently identified that many subroutines were unnecessary. Removing these subroutines substantially simplified the algorithm and yielded the current O ~ ( m 5 / 8 ) \widetilde{O}(m^{5/8}) O ( m 5/8 ) amortized update bound.