Deterministic Dynamic Maximal Matching in Sublinear Update Time Aaron Bernstein, Sayan Bhattacharya, Peter Kiss, Thatchaphol Saranurak Abstract We give a fully dynamic deterministic algorithm for maintaining a maximal matching of an n n -vertex graph in O ~ ​ ( n 8 / 9 ) \tilde{O}(n^{8/9}) amortized update time. This breaks the long-standing Ω ⁡ ( n ) \Omega(n) -update-time barrier on dense graphs, achievable by trivially scanning all incident vertices of the updated edge, and affirmatively answers a major open question repeatedly asked in the literature [ BGS15 , BCHN18 , Sol22 ] . We also present a faster randomized algorithm against an adaptive adversary with O ~ ​ ( n 3 / 4 ) \tilde{O}(n^{3/4}) amortized update time. Our approach employs the edge degree constrained subgraph (EDCS), a central object for optimizing approximation ratio, in a completely novel way; we instead use it for maintaining a matching that matches all high degree vertices in sublinear update time so that it remains to handle low degree vertices rather straightforwardly. To optimize this approach, we employ tools never used in the dynamic matching literature prior to our work, including sublinear-time algorithms for matching high degree vertices, random walks on directed expanders, and the monotone Even-Shiloach tree for dynamic shortest paths. a 1 Introduction A matching M of a graph G=(V,E) is a set of vertex-disjoint edges. We say that M is maximal if every free edge (u,v)\in E\setminus M is not vertex-disjoint from M . That is, a maximal matching is precisely a set of edges that are disjoint yet intersect all other edges. Although computing a maximal matching admits a simple linear-time greedy algorithm, it presents interesting challenges in various computational models and has been extensively studied since the 80s, including in the PRAM model [ KW85 , Lub85 , II86 , IS86 , AGLP89 , ABI86 , GH21 ] , distributed models [ HKP99 , HKP01 , BEPS16a , Fis20 , BBH+21 ] , and, more recently, the MPC model [ LMSV11 , GGK+18 , CŁM+18 , GU19 , ABB+19b , BHH19 ] . In this paper, we study this problem in the dynamic setting. Dynamic Maximal Matching. In the fully dynamic maximal matching problem, we must maintain a maximal matching M of an n -vertex m -edge graph G undergoing both edge insertions and deletions. The goal is to minimize the update time for updating M , given an edge update. Since the 90s, Ivković and Lloyd [ IL93 ] showed the first non-trivial algorithm that has O((n+m)^{0.7072}) amortized update time and is deterministic. A key milestone was made by Baswana, Gupta, and Sen [ BGS11 , BGS18 ] who showed a near-optimal randomized algorithm with O(\log n) amortized update time. This was further improved to an optimal O(1) update time by Solomon [ Sol16a ] . Different \mathrm{poly}(\log n) -update-time algorithms with additional properties were given in [ BDH+19 , BFH21 , GT24 ] . Unfortunately, all these algorithms share a common drawback; they are all randomized and assume an oblivious adversary . 1 1 1 Dynamic algorithms assume an oblivious adversary if they assume that the whole update sequence is fixed from the beginning and is independent of the answers maintained by the algorithm. Without this assumption, we say that the algorithms work against an adaptive adversary. The state of the art of deterministic algorithms is much worse. No previous algorithms could even strictly beat the following trivial solution: When (u,v) is inserted, match u and v if both u and v were unmatched. When (u,v) is deleted, check if u or v can be matched by scanning through O(n) neighbors of u and v . This straightforwardly takes O(n) update time. While there are algorithms with \tilde{O}(\alpha) worst-case update time where \alpha is the arboricity [ NS16 , CHvdH+22 ] , they still require \Omega(n) update time in dense graphs. Overcoming the \Omega(n) deterministic barrier remains a long-standing open problem. Success in Dynamic Approximate Maximum Matching. The influential result of [ BGS11 , BGS18 ] also implies a fully dynamic algorithm for maintaining 2 -approximate maximum matching. Since then, the community has shifted its focus to fully dynamic approximate maximum matching in various approximation regimes, including the approximation factors of (2+\epsilon) [ BHN16 , BCH17 , BHN17 , ACC+18 , CS18 , BHI18 , BK19 , BFH21 , Kis22 ] , (2-\epsilon) [ BHN16 , BLM20 , RSW22 , Beh23a , BKSW23 , ABR24 ] , (1.5+\epsilon) [ BS15a , BS16a , GSSU22a , Kis22 ] , (1.5-\epsilon) [ Beh23b ] , and (1+\epsilon) [ GP13 , ABKL23 , Liu24 ] . Numerous papers dove into specialized topics, including partially dynamic algorithms [ GRS14 , GLS+19 , BGS20 , BKS23a , JJST22 , ABD22 , BK23 , CST23 , BCK+24 ] , dynamic approximation-preserving reductions from weighted to unweighted graphs [ GP13 , SV17 , BDL21 , BCD+24 ] , and dynamic rounding algorithms [ ACC+18 , Waj20 , BK21 , BKSW24 , Dud24 ] . Within the last decade, these 40+ papers have made the dynamic matching problem one of the most actively studied dynamic graph problems. A significant part of this body of work [ BHN16 , BCH17 , BHN17 , BHI18 , BK19 , Kis22 , GSSU22b ] successfully developed deterministic algorithms whose update times match those of their randomized counterparts. The Barrier Remains. But despite the successes mentioned above, the \Omega(n) deterministic barrier for dynamic maximal matching remains unbroken. A high-level explanation is that a maximal matching is far more fragile than an approximate matching. For approximate matching, via standard reductions [ AKL19 , Kis22 ] , it requires \Omega(\epsilon n) edge updates before the maximum matching size changes by a (1+\epsilon) factor. In contrast, a single edge deletion can destroy maximality completely. This challenge has become a major open problem in the field and has been repeatedly posed as an open question [ BGS15 , BCHN18 , Sol22 ] . The problem remains unresolved even for randomized algorithms against an adaptive adversary. In this paper, we break this long-standing \Omega(n) deterministic barrier. Theorem 1.1 . There is a deterministic fully dynamic maximal matching algorithm with \tilde{O}(n^{8/9}) amortized update time. Also, there is a randomized fully dynamic maximal matching algorithm with \tilde{O}(n^{3/4}) amortized update time that works with high probability against an adaptive adversary . 2 2 2 The \tilde{O} notation hides \mathrm{poly}\log n factors. Thus, we give the first deterministic maximal matching algorithm with sublinear update time. Using randomization but without an oblivious adversary, we can speed up the algorithm even further. In general, significant effort has been made towards closing the gap between oblivious and adaptive adversaries in dynamic graph problems, which include dynamic connectivity [ HDLT01 , NS17 , WN17 , NSWN17 , GRST21 , CGL+20 ] , sparsifiers [ BBG+20 , CGH+20 , GRST21 , BSS22 , vdBGJ+22 , KMPG24 , HLS24 ] , and shortest paths [ BC16 , Ber17 , BC17 , CK19 , GWN20a , GWN20b , CS21 , CZ23 , KMPG24 , HLS24 ] . These algorithms are crucial building blocks in the modern development of fast static graph algorithms [ CKL+22 , AKL+22 , ALPS23 , BCK+24 ] . We take the first step in this direction for dynamic maximal matching. Techniques Previous Techniques. The key question in designing dynamic maximal matching algorithms is how to handle deletions of a matched edge, as it is relatively easy to handle edge insertions or deletions of an unmatched edge. A trivial solution is that, whenever a vertex v is unmatched, we scan through v ’s neighbors and try to match v . This takes O(\mathrm{deg}(v))=O(n) update time. The previous randomized algorithms [ BGS18 , Sol16b , BDH+19 , GT24 ] speed this up by trying to ensure that the matched edges are not deleted too often. For intuition, consider the following simplistic scenario when the graph is a star with root u and leaves v_{1},\dots,v_{n} , and the adversary only deletes edges. Suppose we sample a random edge (u,v_{i}) and include it in the matching. If the adversary is oblivious to our random choices , then it will take \Omega(n) edge deletions in expectation before the adversary deletes our matched edge (u,v_{i}) . Once this happens, even if we spend O(n) time, we can charge this cost to the \Omega(n) deletions, leading to O(1) amortized update time. This is the basic idea that all previous randomized algorithms exploited and successfully carried out beyond this simplistic scenario. Unfortunately, it completely fails without an oblivious adversary, and, in particular, for deterministic algorithms. A Bird’s-Eye View of Our Algorithm. Our deterministic algorithm is very different. We maintain a vertex set V^{\star} in o(n) update time such that 1. the maximum degree in G[V\setminus V^{\star}] is o(n) 3 3 3 Technically, we actually show that G[V\setminus V^{\star}] has arboricity o(n) . , and 2. we can further maintain a V^{\star} -perfect matching M_{\texttt{base}} that matches all vertices in V^{\star} in o(n) update time. Given this, we can maintain a maximal matching M\supseteq M_{\texttt{base}} in o(n) update time. Indeed, if vertex v becomes unmatched, we only need to scan through v ’s neighbors in V\setminus V^{\star} , which has o(n) vertices, as all vertices in V^{\star} are already matched by M_{\texttt{base}} . Observe that this argument crucially requires that all vertices of V^{\star} are matched. Maintaining a perfect matching is normally very difficult in the dynamic setting and there are strong conditional lower bound for this task [ HKNS15 , Dah16 ] . So we will need to pick a V^{\star} that has additional structure. New Applications of EDCS. Surprisingly, we can obtain V^{\star} from an edge-degree constrained subgraph (EDCS), a well-known subgraph H\subseteq G that is useful for (1.5+\epsilon) -approximate maximum matching algorithms in the dynamic setting and beyond [ BS15b , BS16b , AB19 , ABB+19a , GSSU22b , AB23 , Beh23a , BKS23b , Ber24 ] . See Definition 2.1 for definition. The outline below presents a completely novel application of this central object in the literature. The set V^{\star} is simply the set of vertices with “high degree” in the EDCS H , which can be explicitly maintained in o(n) time using existing results [ GSSU22a ] . By the structure of EDCS, Item 1 follows directly. To see why Item 2 should hold, we observe that the graph H_{\texttt{hilo}}:=E_{H}(V^{\star},V\setminus V^{\star}) has a degree gap . More precisely, for some number X and \gamma>0 , every vertex in V^{\star} has degree at least X in H_{\texttt{hilo}} , while every vertex in V\setminus V^{\star} has degree at most (1-\gamma)X in H_{\texttt{hilo}} . Consequently, for every set S\subseteq V^{\star} , we have |N_{H_{\texttt{hilo}}}(S)|\geq(1+\Omega(\gamma))|S| , i.e., Hall’s condition holds with a slack . This strong expansion implies the existence of short O(\log(n)/\gamma) -length augmenting paths and allows us to maintain a V^{\star} -perfect matching in o(n) update time. New Toolkit for Dynamic Matching. To carry out the above approach, we employ tools never used in the dynamic matching literature prior to our work. For example, to maintain the V^{\star} -perfect matching deterministically, we use the monotone Even-Shiloach tree for dynamic shortest paths [ SE81 , Kin99 , HKN16 ] and, for our faster randomized algorithm, we apply random walks on directed expanders. Although not necessary for breaking the \Omega(n) barrier, we also apply a a sublinear-time algorithm for matching high-degree vertices [ Ass24 ] to further optimize our update time. Concurrent Work. Computing maximal matching is among the fundamental symmetry breaking problems, that also include computing maximal independent set, vertex coloring and edge coloring. Very recently, Behnezhad, Rajaraman and Wasim [ BRW25 ] showed the first randomized fully dynamic algorithm for maintaining a (\Delta+1) -vertex coloring against an adaptive adversary in sub-linear update time. Organization. We first present the preliminaries in Section 2 and the subroutine for efficiently matching most vertices with almost maximum degree in Section 3 . They are needed for our detailed overview in Section 4 . Then, we present a complete algorithm for maintaining perfect matching of high-degree vertices in a graph with degree gap in Section 5 and use it to formally prove our main result in Section 6 . 2 Preliminaries Basic Notations. Consider any graph G=(V,E) . We let N_{G}(v)\subseteq E denote the set of edges in G that are incident on a node v\in V , and we define \mathrm{deg}_{G}(v):=|N_{G}(v)| to be the degree of v in G . Matching. A matching M\subseteq E in a graph G=(V,E) is a subset of edges that do not share any common endpoint. We let V(M) denote the set of nodes matched under M . Furthermore, for any set S\subseteq V , we let M(S):=\{(u,v)\in M:\{u,v\}\cap S\neq\emptyset\} denote the set of matched edges under M that are incident on some node in S . Let M be a matching in G . We say that a vertex v is M -free if v\notin V(M) , otherwise it is M -matched. An augmenting path P in G with respect to M is a path in G such that the endpoints are M -free and its edges alternate between edges in M and edges not in M . Let M\oplus P stand for (M\setminus P)\cup(P\setminus M) , the matching obtained by extending M with the augmenting path P . We have M\oplus P is a matching of size |M|+1 . Every M -matched vertex is also matched in M\oplus P . EDCS. For any graph H and e=(u,v) where e is not necessary an edge of H , the degree of e in H is defined as \mathrm{deg}_{H}(e)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\mathrm{deg}_{H}(u)+\mathrm{deg}_{H}(v) . The basis of our algorithm is an edge degree constrained subgraph (EDCS). Definition 2.1 . An (B,B^{-}) -EDCS H of G is a subgraph of G such that • For each edge e\in H , \mathrm{deg}_{H}(e)\leq B , and • For each edge e\in G\setminus H , \mathrm{deg}_{H}(e)\geq B^{-} . Theorem 2.2 ( [ GSSU22a ] ) . For any parameters B\leq n and \epsilon>0 , there is a deterministic algorithm that, given a graph G with n vertices undergoing both edge insertions and deletions, explicitly maintains a (B,B(1-\epsilon)) -EDCS H of G using O(\frac{n}{B\epsilon}) worst-case update time. Furthermore, there are at most two vertices u,v\in V such that their degree \mathrm{deg}_{H}(v),\mathrm{deg}_{H}(u) in the EDCS changes due to the handling of an update. Graph Access. We say that an algorithm has adjacency matrix query access to graph G if it can answer queries with inputs (u,v)\in V\times V returning true iff (u,v)\in E in O(1) time. We say that an algorithm has adjacency list query access to graph G if it can find the degree of any vertex and answer queries with input (v,i)\in V\times[\mathrm{deg}_{G}(v)] returning the i -th neighbour of vertex v in G according to some arbitrary ordering in O(\log n) time. 3 Match Most Vertices with Almost Maximum Degree Next, we give a useful observation that there always exists a matching that matches most all vertices with almost maximum degree. Our deterministic and randomized implementations of the algorithm of Lemma 3.1 rely on a black box application of [ EK24 ] and a white box application of [ Ass24 ] . As the lemma can mostly be concluded from existing results in literature we defer its proof to Appendix B . Lemma 3.1 . Let G=(V,E) be a graph with maximum degree at most \Delta which can be accessed through both adjacency list and matrix queries. Let V_{\kappa} denote the set of all nodes in G with degree at least (1-\kappa)\Delta . Then, for any \kappa>0 there exists a matching M\subseteq E that matches all but 2\kappa n many nodes in V_{\kappa} . • If \Delta\geq\frac{4}{\kappa} , then M can be computed in O(n\Delta\kappa\log^{2}n) time with high probability. • M can be deterministically computed in O(m\frac{\log n}{\kappa})=O(n\Delta\cdot\frac{\log n}{\kappa}) time. 3.2 . While the specific bounds of Lemma 3.1 rely on recent advances in static coloring algorithms, any bound of the form O(m\mathrm{poly}(\Delta/\kappa)) would translate to a sublinear update time for our main result of fully dynamic maximal matching. For example, one could instead use the classical coloring algorithm of Gabow et al. [ GNK+85 ] , or one could start with a trivial fractional matching and use existing tools to round it to an integral matching one (see e.g. [ BKSW24 ] ). 3.3 . The randomized algorithm of Lemma 3.1 can be improved to have a running time of \tilde{O}(n) using a white-box modification of [ Ass24 ] . As this running time difference doesn’t ultimately end up affecting the update time of our final algorithm, we opted for the slower subroutine of Lemma 3.1 , because it can be obtained from [ Ass24 ] in a black-box way. 4 Overview: Our Dynamic Maximal Matching Algorithm For ease of exposition, we first present the algorithm in a decremental setting, where the input graph only undergoes edge deletions. We will show how to handle fully dynamic updates without increasing update time at the end in Section 4.7 . The Framework. We fix two parameters B\in[n] and \epsilon\in(0,1) whose values will be determined later on, and define \delta:=100\epsilon. (1) The reader should think of \epsilon=1/n^{\beta} and B=1/\epsilon^{2} for some absolute constant 0<\beta<1 . Let G=(V,E) be the input graph with n nodes, undergoing edge deletions. We maintain a (B,(1-\epsilon)B) -EDCS H:=(V,E(H)) of G at all times, as per Theorem 2.2 . This incurs an update time of O\left(\frac{n}{B\epsilon}\right) . The EDCS H is maintained explicitly, and we can make adjacency-list and adjacency-matrix queries to H whenever we want. We maintain the adjacency-lists of all vertices in H as binary search trees. Hence, we may answer an adjacency-list and adjacency-matrix query to H in O(\log n) and O(1) time respectively. Our dynamic algorithm works in phases , where each phase consists of \delta n consecutive updates in G . Let G_{\texttt{init}}=(V,E_{\texttt{init}}) and H_{\texttt{init}}=(V,E(H_{\texttt{init}})) respectively denote the status of the input graph G and the EDCS H at the start of a given phase. Throughout the duration of the phase, we let H_{\texttt{core}} denote the subgraph of H_{\texttt{init}} restricted to the edges in G . Specifically, we define H_{\texttt{core}}:=(V,E(H_{\texttt{core}})) , where E(H_{\texttt{core}}):=E(H_{\texttt{init}})\cap E . Note that H_{\texttt{core}} is a decremental graph within a phase, i.e., the only updates that can occur to H_{\texttt{core}} are edge deletions. Organization of the Overview. In Section 4.1 , we present a classification of nodes based on their degrees in the EDCS H at the start of a phase, under one simplifying assumption (see 4.1 ). To highlight the main ideas, we first describe and analyze our algorithm under this assumption. Section 4.2 shows how to maintain a base matching M_{\texttt{base}} , which matches all the nodes of a certain type (that have large EDCS degrees). Next, Section 4.3 shows how to maintain a maximal matching in the subgraph of G induced by the nodes that are free under M_{\texttt{base}} . In Section 4.4 , we put together the algorithms from Sections 4.2 and 4.3 , and derive Theorem 1.1 . Next, in Section 4.5 , we explain how to deal with the scenario when the simplifying assumption we made earlier (see 4.1 ) does not hold. Section 4.6 sketches the proof outline of a key lemma, which allows us to maintain the matching M_{\texttt{base}} efficiently in Section 4.2 . Finally, Section 4.7 shows how to extend our algorithm so that it can deal with fully dynamic updates. 4.1 Classification of Nodes and a Simplifying Assumption We will outline how to maintain a maximal matching M_{\texttt{final}} in G during a phase. We start by making one simplifying assumption stated below. Towards the end of this section, we explain how to adapt our algorithm when this assumption does not hold (see Section 4.5 ). 4.1 . For every node v\in V , either \mathrm{deg}_{H_{\texttt{init}}}(v)>\left(\frac{1}{2}+\delta\right)B or \mathrm{deg}_{H_{\texttt{init}}}(v)<\left(\frac{1}{2}-\delta\right)B . In other words, this establishes a small “degree-gap” within the EDCS H at the start of the phase, by asserting that there does not exist any node v\in V with \left(\frac{1}{2}-\delta\right)B\leq\mathrm{deg}_{H_{\texttt{init}}}(v)\leq\left(\frac{1}{2}+\delta\right)B . We say that a node v\in V is very high if \mathrm{deg}_{H_{\texttt{init}}}(v)>\left(\frac{1}{2}+\delta\right)B , and low if \mathrm{deg}_{H_{\texttt{init}}}(v)<\left(\frac{1}{2}-\delta\right)B . We let V_{\texttt{v-hi}} and V_{\texttt{lo}} respectively denote the sets of very high and low nodes. By 4.1 , the node-set V is partitioned into V_{\texttt{v-hi}}\subseteq V and V_{\texttt{lo}}=V\setminus V_{\texttt{v-hi}} . Our algorithm will crucially use two properties that arise out of this classification of nodes, as described below. Proposition 4.2 . The following properties hold. 1. Consider any edge (u,v)\in E(H_{\texttt{init}}) where u is very-high. Then v must be low. 2. Consider any edge e\in E_{\texttt{init}} whose both endpoints are low. Then e must appear in H_{\texttt{init}} . Proof. First, we prove Item 1 . Note that since (u,v)\in E(H_{\texttt{init}}) , we have \mathrm{deg}_{H_{\texttt{init}}}(u)+\mathrm{deg}_{H_{\texttt{init}}}(v)\leq B (see Definition 2.1 ). Furthermore, since u is very-high, we have \mathrm{deg}_{H_{\texttt{init}}}(u)>\left(\frac{1}{2}+\delta\right)B . Thus, it follows that \mathrm{deg}_{H_{\texttt{init}}}(v)\leq B-\mathrm{deg}_{H_{\texttt{init}}}(u)<\left(\frac{1}{2}-\delta\right)B , and so v must be a low node. Next, we prove Item 2 . Let e=(u,v) , where both u,v are low nodes. Then \mathrm{deg}_{H_{\texttt{init}}}(u)<\left(\frac{1}{2}-\delta\right)B and \mathrm{deg}_{H_{\texttt{init}}}(v)<\left(\frac{1}{2}-\delta\right)B , and hence \mathrm{deg}_{H_{\texttt{init}}}(u)+\mathrm{deg}_{H_{\texttt{init}}}(v)<(1-2\delta)B<(1-\epsilon)B . As H_{\texttt{init}} is a (B,(1-\epsilon)B) -EDCS of G_{\texttt{init}} , it follows that (u,v)\in E\left(H_{\texttt{init}}\right) (see Definition 2.1 ). ∎ We next introduce one last category of nodes, as defined below. 4.3 . Consider a very high node v\in V_{\texttt{v-hi}} . At any point in time within the current phase, we say that v is damaged if \mathrm{deg}_{H_{\texttt{core}}}(v)<\left(\frac{1}{2}+\delta-2\epsilon\right)B , and safe otherwise. We let V_{\texttt{dmg}}\subseteq V_{\texttt{v-hi}} and V_{\texttt{sf}}:=V_{\texttt{v-hi}}\setminus V_{\texttt{dmg}} respectively denote the sets of damaged and safe nodes. Recall that \mathrm{deg}_{H_{\texttt{init}}}(v)>\left(\frac{1}{2}+\delta\right)B for all nodes v\in V_{\texttt{v-hi}} . Thus, for such a node to get damaged at least 2\epsilon B many of its incident edges must be deleted since the start of the phase. Since each phase lasts for \delta n updates in G and \delta=100\epsilon (see ( 1 )), we get the following important corollary. Corollary 4.4 . We always have \left|V_{\texttt{dmg}}\right|\leq\frac{2\delta n}{2\epsilon B}=O\left(\frac{n}{B}\right) . Furthermore, at the start of a phase we have V_{\texttt{dmg}}=\emptyset . During the phase, the subset V_{\texttt{dmg}} grows monotonically over time. 4.2 Maintaining a Matching of All the Safe Nodes One of our key technical insights is that the degree gap in H_{\texttt{core}} allows us to efficiently maintain a matching M_{\texttt{base}}\subseteq E(H_{\texttt{core}}) that matches all safe nodes, as per Lemma 4.5 below. With appropriate setting of parameters, the update time of both of the algorithms (deterministic and randomized) in Lemma 4.5 are sublinear in n . 4.5 . We can maintain a matching M_{\texttt{base}}\subseteq E(H_{\texttt{core}}) that satisfy the following properties. 1. Every safe node is matched under M_{\texttt{base}} , i.e., V_{\texttt{sf}}\subseteq V(M_{\texttt{base}}) . 2. Every update in G that is internal to a phase (i.e., excluding those updates where one phase ends and the next phase begins) leads to at most O(1) node insertions/deletions in V(M_{\texttt{base}}) . The matching M_{\texttt{base}} can be maintained either by • a deterministic algorithm with \tilde{O}\left(B\cdot n^{1/2}\cdot\delta^{-3/2}\right) amortized update time; or • a randomized algorithm with \tilde{O}\left(B\cdot\delta^{-1}+\delta^{-3}\right) amortized update time. The algorithm is correct with high probability against an adaptive adversary. Intuition Aside: The only property of H_{\texttt{core}} that we need for Lemma Lemma 4.5 is the degree gap between V_{\texttt{sf}} and V_{\texttt{lo}} ; in fact, the whole reason we use an EDCS in the first place is to ensure this degree gap. We defer the proof sketch of Lemma 4.5 to Section 4.6 , but to provide an intuition for why the degree gap helps match vertices in V_{\texttt{sf}} , we show here that it is easy to deterministically maintain a fractional matching satisfying the concerned properties of Lemma 4.5 , in O(B/\delta) update time. We do not this result in the main body of our paper and include it only for intuition. We denote the fractional matching by x_{\texttt{base}}:E(H_{\texttt{core}})\rightarrow[0,1] , which is constructed as follows. • \Gamma\leftarrow\left(\frac{1}{2}+\delta-2\epsilon\right)B and x_{\texttt{base}}(e)\leftarrow 0 for all e\in E • For every safe node v\in V_{\texttt{sf}} – Let E^{\star}_{v}\subseteq E(H_{\texttt{core}}) be a set of \Gamma distinct edges incident to v . ( E^{\star}_{v} exists as v\in V_{\texttt{sf}} ). – x_{\texttt{base}}(e)\leftarrow 1/\Gamma for all e\in E^{\star}_{v} • Return x_{\texttt{base}}:E(H_{\texttt{core}})\rightarrow[0,1] . Consider any two distinct nodes v,v^{\prime}\in V_{\texttt{sf}}\subseteq V_{\texttt{v-hi}} . By Item 1 of Proposition 4.2 , there cannot be an edge (v,v^{\prime})\in E(H_{\texttt{core}})\subseteq E(H_{\texttt{init}}) , and hence E^{\star}_{v}\cap E^{\star}_{v^{\prime}}=\emptyset . Using this observation, it is easy to verify that the function x_{\texttt{base}} is a valid fractional matching in H_{\texttt{core}} , and that every node v\in V_{\texttt{sf}} receives a weight x_{\texttt{base}}(v)=1 under this fractional matching. 4 4 4 The weight x_{\texttt{base}}(v) is the sum of the values x_{\texttt{base}}(e) , over all the edges in H_{\texttt{core}} that are incident on v . Furthermore, since the EDCS H_{\texttt{init}} has maximum degree at most B (this follows from Definition 2.1 ) and each phase lasts for \delta n updates, we can deterministically maintain the fractional matching x_{\texttt{base}} in O\left(\frac{nB}{\delta n}\right)=O(B/\delta) amortized update time. One can also verify that each update in G that is internal to a phase leads to at most O(1) nodes v\in V changing their weights x_{\texttt{base}}(v) under x_{\texttt{base}} . 4.3 Maintaining a Maximal Matching in the Adjunct Subgraph Let G_{\texttt{adj}}:=(V_{\texttt{adj}},E_{\texttt{adj}}) denote the subgraph of G induced by the set of nodes that are unmatched under M_{\texttt{base}} , that is, V_{\texttt{adj}}:=V\setminus V(M_{\texttt{base}}) and E_{\texttt{adj}}:=\{(u,v)\in E:u,v\in V_{\texttt{adj}}\} . We will refer to G_{\texttt{adj}} as the adjunct subgraph of G w.r.t. M_{\texttt{base}} . By the following observation, all that remains is to maintain a maximal matching in G_{\texttt{adj}} Observation 4.6 . If M_{\texttt{adj}} is a maximal matching of G_{\texttt{adj}} , then M_{\texttt{final}}:=M_{\texttt{base}}\cup M_{\texttt{adj}} is a maximal matching in G=(V,E) We now show how to efficiently maintain a maximal matching M_{\texttt{adj}} of G_{\texttt{adj}} (we refer to it as the adjunct matching ). Lemma 4.7 . Suppose that we maintain the matching M_{\texttt{base}} as per Lemma 4.5 . Then with an additive overhead of \tilde{O}\left(\frac{B}{\delta}+\frac{n}{\delta B}\right) amortized update time, we can deterministically and explicitly maintain a maximal matching M_{\texttt{adj}}\subseteq E_{\texttt{adj}} in G_{\texttt{adj}} . At this point, the reader might get alarmed because G_{\texttt{adj}} undergoes node-updates every time an edge gets added to/removed from M_{\texttt{base}} , which might indicate that it is impossible to efficiently maintain a maximal matching in G_{\texttt{adj}} . To assuage this concern, we emphasize that: (i) the arboricity of G_{\texttt{adj}} is sublinear in n (see 4.8 ), and (ii) an edge update in G that is internal to a phase leads to at most O(1) node-updates in G_{\texttt{adj}} (see 4.9 ). These two properties ensure that we can maintain the matching M_{\texttt{adj}} in sublinear in n update time. 4.8 . The subgraph G_{\texttt{adj}}=(V,E_{\texttt{adj}}) satisfies the following properties. 1. V_{\texttt{sf}}\cap V_{\texttt{adj}}=\emptyset and \left|V_{\texttt{dmg}}\cap V_{\texttt{adj}}\right|=O\left(\frac{n}{B}\right) . Furthermore, V_{\texttt{dmg}}\cap V_{\texttt{adj}}=\emptyset at the start of a phase. 2. \mathrm{deg}_{G_{\texttt{adj}}}(v)\leq B+\left|V_{\texttt{dmg}}\cap V_{\texttt{adj}}\right| for all nodes v\in V_{\texttt{lo}} . Proof. Since V_{\texttt{adj}}:=V\setminus V(M_{\texttt{base}}) , Item 1 follows from Item 1 of Lemma 4.5 , and Corollary 4.4 . To prove Item 2 , consider any node v\in V_{\texttt{lo}} . Let u\in V_{\texttt{lo}} be any low neighbor of v in E_{\texttt{adj}}\subseteq E\subseteq E_{\texttt{init}} . Then, by Item 2 of Proposition 4.2 , we have (u,v)\in H_{\texttt{init}} . Accordingly, the number of low neighbors of v in G_{\texttt{adj}} is at most \mathrm{deg}_{H_{\texttt{init}}}(v)\leq B , where the last inequality holds because H_{\texttt{init}} is a (B,(1-\epsilon)B) -EDCS of G_{\texttt{init}} (see Definition 2.1 ). As the node-set V is partitioned into V_{\texttt{lo}},V_{\texttt{v-hi}} (see 4.1 ) and V_{\texttt{v-hi}} is further partitioned into V_{\texttt{sf}},V_{\texttt{dmg}} , we get: \mathrm{deg}_{G_{\texttt{adj}}}(v)\leq B+|V_{\texttt{sf}}\cap V_{\texttt{adj}}|+|V_{\texttt{dmg}}\cap V_{\texttt{adj}}|=B+|V_{\texttt{dmg}}\cap V_{\texttt{adj}}|, where the last equality follows from Item 1 . ∎ 4.9 . An edge-update in G internal to a phase leads to at most O(1) node-updates in G_{\texttt{adj}} . Proof. Since V_{\texttt{adj}}:=V\setminus V(M_{\texttt{base}}) , the claim follows from Item 2 of Lemma 4.5 . ∎ 4.10 . At the start of a phase, we have |E_{\texttt{adj}}|=O(Bn) . Proof. By Proposition 4.2 ( 2 ) we have that E_{\texttt{adj}}\subseteq H_{\texttt{init}} . As H_{\texttt{init}} is a (B,B(1-\epsilon)) -EDCS and the maximum vertex degree of a (B,B(1-\epsilon)) -EDCS is B we must have that |E_{\texttt{adj}}|\leq|H_{\texttt{init}}|=O(nB) . ∎ Proof of Lemma 4.7 At the start of a phase, we initialize M_{\texttt{adj}} to be any arbitrary maximal matching in G_{\texttt{adj}} . By Corollary 4.10 , this takes O(Bn) time. Since the phase lasts for \delta n updates in G , this step incurs an amortized update time of: O\left(\frac{Bn}{\delta n}\right)=O\left(\frac{B}{\delta}\right). (2) Subsequently, to handle the updates during a phase, we use the following auxiliary data structures: Each node v\in V_{\texttt{dmg}} maintains the set \mathcal{F}_{\texttt{adj}}(v):=\left\{u\in V_{\texttt{adj}}\setminus V(M_{\texttt{adj}}):(u,v)\in E_{\texttt{adj}}\right\} of its free neighbors (in G_{\texttt{adj}} ) under the matching M_{\texttt{adj}} . 5 5 5 Maximality of M_{\texttt{adj}} implies that \mathcal{F}_{\texttt{adj}}(v)=\emptyset for all v\in V_{\texttt{dmg}}\setminus V(M_{\texttt{adj}}) . Whenever a node v moves from V_{\texttt{sf}} to V_{\texttt{dmg}} , we spend \tilde{O}(n) time to initialize the set \mathcal{F}_{\texttt{adj}}(v) as a balanced search tree. Within a phase, a node can move from V_{\texttt{sf}} to V_{\texttt{dmg}} at most once (see Definition 4.3 and Corollary 4.4 ). Thus, by Item 1 of 4.8 , these initializations take \tilde{O}\left(\frac{n}{B}\cdot n\right)=\tilde{O}\left(\frac{n^{2}}{B}\right) total time during a phase. As each phase lasts for \delta n updates in G , this incurs an amortized update time of \tilde{O}\left(\frac{n^{2}}{B\cdot\delta n}\right)=\tilde{O}\left(\frac{n}{\delta B}\right) . 4.9 guarantees that each edge update in G leads to O(1) node-updates in G_{\texttt{adj}} . We now show that to maintain the maximal matching M_{\texttt{adj}} , a node-update to G_{\texttt{adj}} can be handled in \tilde{O}\left(B+\frac{n}{B}\right) worst-case time. If a new vertex v enters G_{\texttt{adj}} (because v became unmatched in M_{\texttt{base}} ), then to maintain the maximality of M_{\texttt{adj}} , the algorithm needs to find a free neighbor of v (if one exists). The same needs to be done if x leaves G_{\texttt{adj}} , and x was previously matched to v in M_{\texttt{adj}} . So to handle a node-update in G_{\texttt{adj}} we need a subroutine that takes in a vertex v and either finds a M_{\texttt{adj}} -free neighbor of v in G_{\texttt{adj}} or certifies that none exists. The above subroutine can be performed in \tilde{O}(1) time if v\in V_{\texttt{dmg}} (using the set \mathcal{F}_{\texttt{adj}}(v) ); if v\in V_{\texttt{adj}}\setminus V_{\texttt{dmg}} then by Item 1 of 4.8 v\in V_{\texttt{lo}} , so by Item 2 of the same claim we can perform the subroutine in time \mathrm{deg}_{G_{\texttt{adj}}}(v)=O\left(B+\frac{n}{B}\right) . Further, once we decide to match a node u\in V_{\texttt{adj}} to one of its free neighbors, we can update all the relevant sets \mathcal{F}_{\texttt{adj}}(v) in \tilde{O}\left(\left|V_{\texttt{dmg}}\right|\right)=\tilde{O}\left(\frac{n}{B}\right) time (see 4.8 ). To summarize, the amortized update of maintaining the matching M_{\texttt{adj}} under adversarial updates in G is at most: \tilde{O}\left(\frac{n}{\delta B}+B+\frac{n}{B}\right)=\tilde{O}\left(B+\frac{n}{\delta B}\right). (3) Lemma 4.7 follows from ( 2 ) and ( 3 ). 4.4 Putting Everything Together: How to Derive Theorem 1.1 Since E(H_{\texttt{core}})\subseteq E , it follows that M_{\texttt{base}}\subseteq E(H_{\texttt{core}}) is a valid matching in G (see Lemma 4.5 ). Furthermore, Lemma 4.7 guarantees that M_{\texttt{adj}} is a maximal matching in G_{\texttt{adj}} Thus, by Observation 4.6 , the matching M_{\texttt{final}}:=M_{\texttt{base}}\cup M_{\texttt{adj}} is a maximal matching in G . It now remains to analyze the overall amortized update time of our algorithm. Recall that maintaining the EDCS H incurs an update time of O\left(\frac{n}{\epsilon B}\right)=O\left(\frac{n}{\delta B}\right) , according to ( 1 ). Now, for the deterministic algorithm, Lemma 4.5 incurs an amortized update time of \tilde{O}\left(B\cdot n^{1/2}\cdot\delta^{-3/2}\right) . Thus, by Lemma 4.7 , the overall amortized update time becomes O\left(\frac{n}{\delta B}\right)+\tilde{O}\left(B\cdot n^{1/2}\cdot\delta^{-3/2}\right)+\tilde{O}\left(\frac{B}{\delta}+\frac{n}{\delta B}\right)=\tilde{O}(n^{8/9}),\text{ for }\delta=\frac{1}{n^{1/9}}\text{ and }B=n^{2/9}. For the randomized algorithm against an adaptive adversary, Lemma 4.5 incurs an amortized update time of \tilde{O}(B\delta^{-1}+\delta^{-3}) . Thus, by Lemma 4.7 , the overall amortized update time becomes O\left(\frac{n}{\delta B}\right)+\tilde{O}\left(\frac{B}{\delta}+\frac{1}{\delta^{3}}\right)+\tilde{O}\left(\frac{B}{\delta}+\frac{n}{\delta B}\right)=\tilde{O}\left(n^{3/4}\right),\text{ for }\delta=\frac{1}{n^{1/4}}\text{ and }B=n^{1/2}. This leads us to Theorem 1.1 in the decremental setting. 4.5 Dealing with Medium Nodes: Getting Rid of 4.1 We now provide a high-level outline of our algorithm in the general case, when 4.1 does not hold. Recall that under 4.1 there cannot be any node v with \left(\frac{1}{2}-\delta\right)B\leq\mathrm{deg}_{H_{\texttt{init}}}(v)\leq\left(\frac{1}{2}+\delta\right)B . Conceptually, the most significant challenge here is to deal with the set of medium nodes , given by: V_{\texttt{med}}:=\left\{v\in V:\left(\frac{1}{2}-\delta\right)B\leq\mathrm{deg}_{H_{\texttt{init}}}(v)<\left(\frac{1}{2}+\delta-\epsilon\right)B\right\}. For the rest of this overview, we replace 4.1 with the following weaker assumption 4.11 Replaces 4.1 . All vertices are in V_{\texttt{lo}} , V_{\texttt{med}} , or V_{\texttt{v-hi}} In the main body of the paper we also have to handle the nodes that are ruled out by the above assumption, namely the ones whose degrees in H_{\texttt{init}} lie in the range \left[\left(\frac{1}{2}+\delta-\epsilon\right)B,\left(\frac{1}{2}+\delta\right)B\right] . These remaining nodes lie in an extremely narrow range, so while they require some technical massaging, they do not pose any additional conceptual difficulties. We now show how to adapt our algorithm to also handle the medium nodes. Lemma 4.12 , stated below, generalizes Lemma 4.5 , and serves as a key building block of our algorithm. The only difference between these two lemmas is that in Item 1 of Lemma 4.12 , we allow for O(\delta n) medium nodes that are free under M_{\texttt{base}} . Note that sets V_{\texttt{sf}} and V_{\texttt{dmg}} are defined the same as before ( Definition 4.3 ), and are in particular both subsets of V_{\texttt{v-hi}} . 4.12 . We can maintain a matching M_{\texttt{base}}\subseteq E(H_{\texttt{core}}) that satisfy the following properties. 1. Every safe node is matched under M_{\texttt{base}} , i.e., V_{\texttt{sf}}\subseteq V(M_{\texttt{base}}) . Furthermore, at most O(\delta n) medium nodes are free under M_{\texttt{base}} , i.e., |V_{\texttt{med}}\setminus V(M_{\texttt{base}})|=O(\delta n) . 2. Every update in G that is internal to a phase (i.e., excluding those updates where one phase ends and the next phase begins) leads to at most O(1) node insertions/deletions in V(M_{\texttt{base}}) . The matching M_{\texttt{base}} can be maintained • either by a deterministic algorithm with \tilde{O}\left(B\cdot n^{1/2}\cdot\delta^{-3/2}\right) amortized update time; or • by a randomized algorithm with \tilde{O}\left(B\cdot\delta^{-1}+\delta^{-3}\right) amortized update time. The algorithm is correct with high probability against an adaptive adversary. Before outlining the proof sketch of Lemma 4.12 , we explain how to adapt the algorithm for maintaining a maximal matching M_{\texttt{adj}}\subseteq E_{\texttt{adj}} in the adjunct graph G_{\texttt{adj}}:=(V_{\texttt{adj}},E_{\texttt{adj}}) , which is the subgraph of G induced by the node-set V_{\texttt{adj}}:=V\setminus V(M_{\texttt{base}}) (see Section 4.3 ). Lemma 4.13 , stated below, generalizes Lemma 4.7 in the presence of medium nodes. Lemma 4.13 . Suppose that we maintain the matching M_{\texttt{base}} as per Lemma 4.12 . Then with an additive overhead of \tilde{O}\left(\delta n+\frac{B}{\delta}+\frac{n}{\delta B}\right) amortized update time, we can deterministically and explicitly maintain a maximal matching M_{\texttt{adj}}\subseteq E_{\texttt{adj}} in G_{\texttt{adj}} . Proof Sketch. The only difference with the proof of Lemma 4.7 is that now the set V_{\texttt{adj}} can contain some medium nodes, although |V_{\texttt{adj}}\cap V_{\texttt{med}}|=O(\delta n) as per Item 1 of Lemma 4.12 . We explicitly maintain the set V_{\texttt{adj}}\cap V_{\texttt{med}} as a doubly linked list. Whenever a node v\in V_{\texttt{lo}}\cup V_{\texttt{dmg}} is searching for a free neighbor (in the proof of Lemma 4.7 ), we ensure that it additionally scans the set V_{\texttt{adj}}\cap V_{\texttt{med}} . This leads to an additive overhead of |V_{\texttt{med}}\cap V_{\texttt{adj}}|=O(\delta n) in the update time. Next, recall that H_{\texttt{init}} is a (B,(1-\epsilon)B) -EDCS of G_{\texttt{init}} . Consider any edge (u,v)\in E_{\texttt{adj}}\subseteq E\subseteq E_{\texttt{init}} with v\in V_{\texttt{med}} and u\in V_{\texttt{lo}} . Then, we have \mathrm{deg}_{H_{\texttt{init}}}(u)+\mathrm{deg}_{H_{\texttt{init}}}(v)<\left(\frac{1}{2}-\delta\right)B+\left(\frac{1}{2}+\delta-\epsilon\right)B=(1-\epsilon)B , and hence Definition 2.1 implies that (u,v)\in E(H_{\texttt{init}}) . In other words, all the edges in G_{\texttt{adj}} that connect a low node with a medium node belong to the EDCS H_{\texttt{init}} , which in turn has maximum degree at most B (see Definition 2.1 ). Thus, every medium node has at most B low neighbors in G_{\texttt{adj}} . Now, suppose that we are searching for a free neighbor of a node v\in V_{\texttt{med}} in G_{\texttt{adj}} . This step involves scanning through: (i) all the low neighbors of v in G_{\texttt{adj}} (and by the previous discussion there are at most B such neighbors), (ii) the set V_{\texttt{med}}\cap V_{\texttt{adj}} of size O(\delta n) , and (iii) and at most O\left(\frac{n}{B}\right) damaged nodes V_{\texttt{dmg}}\cap V_{\texttt{adj}} (see Section 4.3 ). Overall, this scan takes O\left(\delta n+B+\frac{n}{B}\right) time, and just as before, contributes an additive overhead of O(\delta n) to the update time in Lemma 4.7 . Everything else remains the same as in the proof of Lemma 4.7 . ∎ Comparing Lemmas 4.12 and 4.13 against Lemmas 4.5 and 4.7 , we conclude that there is an additive overhead of O(\delta n) update time while dealing with the medium nodes. Finally, from the analysis from Section 4.4 , it is easy to verify that this overhead of O(\delta n) does not degrade our overall asymptotic update time (the values of \delta,B remain the same as in Section 4.4 ). Proof Sketch of Lemma 4.12 Consider the scenario at the start of a new phase (just before the first update within that phase). At this point, we first compute a subgraph H^{\prime}_{\texttt{init}}:=(V,E(H^{\prime}_{\texttt{init}})) of H_{\texttt{init}} , as follows. We initialize H^{\prime}_{\texttt{init}}\leftarrow H_{\texttt{init}} . Subsequently, for every node v\in V_{\texttt{v-hi}} , we keep deleting edges (u,v)\in E(H^{\prime}_{\texttt{init}}) incident on v from H^{\prime}_{\texttt{init}} , until \mathrm{deg}_{H^{\prime}_{\texttt{init}}}(v) becomes equal to \Delta:=\left(\frac{1}{2}+\delta\right)B . By Item 1 of Proposition 4.2 , every edge (u,v) that gets deleted from H^{\prime}_{\texttt{init}} has its other endpoint u\in V_{\texttt{lo}} . Accordingly, this process does not reduce the degree of any medium node. When this for loop terminates, we have \left(\frac{1}{2}-\delta\right)B\leq\mathrm{deg}_{H^{\prime}_{\texttt{init}}}(v)\leq\Delta for all v\in V_{\texttt{med}}\cup V_{\texttt{v-hi}} , and \mathrm{deg}_{H^{\prime}_{\texttt{init}}}(v)<\left(\frac{1}{2}-\delta\right)B for all v\in V_{\texttt{lo}} . In other words, the degree of every node v\in V_{\texttt{med}}\cup V_{\texttt{v-hi}} in H^{\prime}_{\texttt{init}} is at least (1-\Theta(\delta)) times the maximum degree \Delta . Now, we apply Lemma 3.1 , with \kappa=\Theta(\delta) , to compute a matching M\subseteq E(H^{\prime}_{\texttt{init}})\subseteq E(H_{\texttt{init}}) that matches all but O(\delta n) nodes in V_{\texttt{med}}\cup V_{\texttt{v-hi}} . Note that \Delta=\Theta(B) , and that a phase lasts for \delta n updates in G . Thus, at the start of a phase, computing the subgraph H^{\prime}_{\texttt{init}} and the invocation of Lemma 3.1 incurs an amortized update time of \tilde{O}\left(\frac{nB+n\Delta/\delta}{\delta n}\right)=\tilde{O}\left(\frac{B}{\delta^{2}}\right) if we use the deterministic algorithm, and an amortized update time of \tilde{O}\left(\frac{nB+n\Delta\delta}{\delta n}\right)=\tilde{O}\left(\frac{B}{\delta}\right) if we use the randomized algorithm. It is easy to verify that both these terms get subsumed within the respective (deterministic or randomized) guarantees of Lemma 4.12 . We have thus shown to initialize the desired matching M_{\texttt{base}}=M at the beginning of the phase. We now give a sketch of how we maintain M_{\texttt{base}} dynamically throughout the phase. Define H_{\texttt{hilo}} to be the induced graph H_{\texttt{core}}[V_{\texttt{v-hi}}\cup V_{\texttt{lo}}] . Recall that all edges in E_{H_{\texttt{core}}}(V_{\texttt{v-hi}}) have their other endpoint in V_{\texttt{lo}} ( Item 1 of Proposition 4.2 ), so the set of edges incident to V_{\texttt{v-hi}} is exactly the same in E_{H_{\texttt{hilo}}} and E_{H_{\texttt{core}}} . We are thus able to apply Lemma 4.5 exactly as before to maintain a matching M_{\texttt{hilo}} in H_{\texttt{hilo}} that matches all of V_{\texttt{sf}} . We will maintain the invariant that M_{\texttt{hilo}}\subseteq M_{\texttt{base}} , thus guaranteeing that all nodes in V_{\texttt{sf}} remain matched throughout the phase. The only remaining concern is that the algorithm for maintaining M_{\texttt{hilo}} might end up unmatching medium vertices in M_{\texttt{base}} : if vertex u\in V_{\texttt{hi}} becomes unmatched, then to maintain M_{\texttt{hilo}} the algorithm from Lemma 4.5 finds an augmenting path from u to some v\in V_{\texttt{lo}} that was free in M_{\texttt{hilo}} ; but although v was free in M_{\texttt{hilo}} , it might have been matched to some medium node x in M_{\texttt{base}} , in which case node x now becomes unmatched. Fortunately, it is not hard to show that every adversarial update creates only O(1) free vertices, so since M_{\texttt{base}} has O(\delta n) free medium vertices at the beginning of the phase, and since each phase lasts for O(\delta n) updates, we maintain the desired property that there are always O(\delta n) free medium vertices. 4.6 Matching All the Safe Nodes: Proof Outline for Lemma 4.5 The key to our proof is an algorithm for maintaining a left-perfect matching in a bipartite graph with a degree gap. 4.14 Simplified version of Lemma 5.1 . Let G=(L\cup R,E) be a bipartite graph where, for some X>0 and 0<\gamma<1 , every vertex v\in L has 2X\geq\mathrm{deg}(v)\geq X and every vertex in R has degree \leq X(1-\gamma) . Suppose that the above degree constraints always hold as G is subject to O(\delta n) decremental updates. Then, there exists an algorithm that maintains a left-perfect matching in G – i.e. a matching in which every vertex in L is matched – with the following update times: • A randomized algorithm with worst-case update time \tilde{O}\left(X+1/\gamma^{3}\right) . • A deterministic algorithm with total update time \tilde{O}\left(\frac{nX}{\gamma}+\frac{n^{1.5}X\delta}{\gamma^{1.5}}\right) . Before proving the above Lemma, let us see why it implies Lemma 4.5 Proof sketch of Lemma 4.5 . For this proof sketch, we assume that we always have V_{\texttt{v-hi}}=V_{\texttt{sf}} ; in the full version, we are able to effectively ignore damaged nodes because Lemma 4.5 only requires us to match all the nodes of V_{\texttt{sf}} . Let H_{\texttt{hilo}} be the subgraph of H_{\texttt{core}} that contains only the edges incident to V_{\texttt{v-hi}} . Observe that under our assumption of V_{\texttt{v-hi}}=V_{\texttt{sf}} , H_{\texttt{hilo}} satisfies the properties of Lemma 4.14 with X=B/2 and \gamma\sim\delta : note in particular that the first property of an EDCS ( Definition 2.1 ) ensures that every vertex has degree \leq B=2X , and that H_{\texttt{hilo}} is bipartite because by Proposition 4.2 , H_{\texttt{init}} contains no edges between vertices in V_{\texttt{v-hi}} . We can thus apply Lemma 4.14 to maintain a matching that matches all of V_{\texttt{sf}} , as desired. The update-time bounds of Lemma 4.14 precisely imply those of Lemma 4.5 ; for the deterministic algorithm, recall that we amortize over the O(\delta n) updates of a phase. ∎ 4.6.1 Maintaining Left-Perfect Matching: Proof of Lemma 4.14 Randomized Algorithm. The randomized algorithm is extremely simple. Say that we have a matching M under which some v\in L is still unmatched. We then find an augmenting path from v to an M -free node in R by taking a random matching-walk from v . That is, we follow a random edge (v,x) to R ; if x is unmatched then we have successfully found an augmenting path, while if x is matched to some y\in L then we repeat the process from y . We are able to show that because of the assumed degree gap of G , this random matching-walk terminates within \tilde{O}(1/\gamma^{3}) steps with high probability. The intuitive reason is as follows: because of the degree gap, every set S\subset L as at least S(1+\gamma) neighbors in R . The graph is thus effectively a \gamma -expander, and in particular we are able to show a correspondence between random matching-walks in G and ordinary random walks in some Eulerian directed \gamma -expander G^{\prime} ; the bound of \tilde{O}(1/\gamma^{3}) then follows from known facts about Eulerian expanders. To initialize the a left perfect matching before the first decremental update occurs we apply the randomized algorithm of Lemma 3.1 with \Delta=X,\kappa=\gamma . This returns a matching covering all but O(n\gamma) vertices of L in time \tilde{O}(nX\gamma) adding an amortized update time component of \tilde{O}(X) over the deletions. We may match each of the O(n\gamma) unmatched vertices using the same random walk based technique as we use to handle deletions in time \tilde{O(n\gamma^{-2})} adding an amortized update time component of \tilde{O(\gamma^{-3})} over the O(n\gamma) deletions. Deterministic Algorithm. The deterministic algorithm is more involved than the randomized one, so we only give a high-level sketch. We start by maintaining a standard directed residual graph G_{\textrm{res}} corresponding to the matching M that we maintain (edges in E\setminus M point from L to R in G_{\textrm{res}} , while edges in M point from R to L ). We also create a dummy sink t in G_{\textrm{res}} , with an edge from all M -free vertices in R to t . It is not hard to check that there is a correspondence between paths from L to t in G_{\textrm{res}} and augmenting paths in G . Our algorithm maintains a shortest path tree T_{\mathrm{res}} to sink t in G_{\textrm{res}} . Given any M -free free vertex v\in L , we can find an augmenting path from v by simply following the v-t path in T_{\mathrm{res}} . The primary challenge is to maintain T_{\mathrm{res}} . It is not hard to prove that for any M -free v\in L , there always exists an augmenting path of length \tilde{O}(1/\gamma) from v to an M -free vertex in R ; this follows from the same expander-based arguments as above, and can also be proved using more elementary techniques. This means that the depth of T_{\mathrm{res}} is bounded by \tilde{O}(1/\gamma) , which makes it easier to maintain. There exists a classic data structure known as an Even and Shiloach tree (denoted ES-tree) that can maintain a low-depth shortest path tree to a sink t in a decremental graph [ SE81 ] . The ES-tree can also handle a special kind of edge insertion into G – namely, an edge insertion is a valid update if it does not decrease any distances to t . If G_{\textrm{res}} were a decremental graph, then we could us an ES-tree to maintain T_{\mathrm{res}} , and we would be done. Unfortunately, even though the input graph G to Lemma 4.14 only undergoes edge deletions, the graph G_{\textrm{res}} can undergo edge insertions for two reasons. Firstly, whenever we augment down a path P , every edge in P flips whether or not it is in M , which means we need to flip the directions of all these edges in G_{\textrm{res}} . We can model this flipping as an inserting of all edges on the reverse path \overleftarrow{P} , followed by a deletion of all edges on the original path P . Fortunately, it is not hard to show that because T_{\mathrm{res}} is a shortest-path tree, inserting \overleftarrow{P} does not decrease any distances (as long as we so before deleting P ), and hence is a valid update to the ES-tree. It is the second kind of edge insertion to G_{\textrm{res}} that poses a significant problem. Say that the adversary deletes some matching edge (u,v) in G . Then v becomes free, so the graph G_{\textrm{res}} should now contain an edge (v,t) ; but simply inserting this edge into G_{\textrm{res}} would not be a valid update to the ES-tree, as it would decrease \mathrm{dist}(v,t) . To overcome this issue, we observe that before the deletion of edge (u,v) we had \mathrm{dist}_{G_{\textrm{res}}}(v,t)=\tilde{O}(1/\gamma) , because we could follow the matching edge from v to u , and as discussed above we know that there exists an augmenting path from u to a free vertex of length \tilde{O}(1/\gamma) . So inserting an edge (v,t) of weight \tilde{O}(1/\gamma) does not decrease any distances to t and is hence a valid operation for the ES-tree. Unfortunately, once we start adding weights to edges to of G_{\textrm{res}} , the distances in G_{\textrm{res}} will get longer and longer, so the next time we add an edge (v^{\prime},t) it might need to have even larger weight for this to be a valid insertion into the ES-tree. (In particular, the presence of edge weights means that we can no longer guarantee that before the insertion of (v^{\prime},t) we had \mathrm{dist}(v^{\prime},t)=\tilde{O}(1/\gamma) .) The distances in G_{\textrm{res}} can thus blow up, which increases the (weighted) depth of T_{\mathrm{res}} and hence causes the ES-tree to become inefficient. To overcome the above issue, we define parameter q=\sqrt{n\gamma} and use structural properties of degree-gap graphs to show that as long as \leq q insertions have occurred, the edge weights have not had a chance to get too large, and the average \mathrm{dist}(v,t) remains small, so the ES-tree remains efficient. Then, after q updates, we simply rebuild the entire ES tree from scratch. Since the total number of resets is only O(n\delta/q) , the total update time ends up being not too large. To initialize a left perfect matching we will use the deterministic algorithm of Lemma 3.1 which returns a matching covering all but O(n\gamma) vertices of L in time \tilde{O}(nX/\gamma) . We augment this imperfect matching at initialization to be a perfect matching using the same datastructure as we use to handle edge deletions. This results in a running time proportional to handling O(n\gamma) deletions matching the cost of handling the decremental updates. 4.7 Extension to the Fully Dynamic Setting It is relatively straightforward to extend the algorithm from Section 4 to a setting where the input graph G=(V,E) undergoes both edge insertions and edge deletions. As in Section 4 , our fully dynamic algorithm works in phases, where each phase lasts for \delta n updates in G . We maintain two subgraphs G_{\texttt{new}}:=(V,E_{\texttt{new}}) and G_{\texttt{core}}:=(V,E_{\texttt{core}}) of G=(V,E) , such that the edge-set E is partitioned into E_{\texttt{new}} and E_{\texttt{core}} . To be more specific, at the start of a phase, we set E_{\texttt{new}}:=\emptyset and E_{\texttt{core}}:=E . Subsequently, during the phase, whenever an edge e gets deleted from G , we set E_{\texttt{core}}\leftarrow E_{\texttt{core}}\setminus\{e\} and E_{\texttt{new}}\leftarrow E_{\texttt{new}}\setminus\{e\} . In contrast, whenever an edge e gets inserted into G , we leave the set E_{\texttt{core}} unchanged, and set E_{\texttt{new}}\leftarrow E_{\texttt{new}}\cup\{e\} . It is easy to verify that within any given phase G_{\texttt{core}} is a decremental subgraph of G . Furthermore, since E_{\texttt{new}}=\emptyset at the start of a phase, each update adds at most one edge to E_{\texttt{new}} and a phase lasts for \delta n updates, it follows that |E_{\texttt{new}}|\leq\delta n at all times. We maintain a maximal matching M_{\texttt{core}}\subseteq E_{\texttt{core}} in G_{\texttt{core}} , using the decremental algorithm from Section 4 . In a bit more detail, we handle an update in G as follows. We first let the decremental algorithm from Section 4 handle the resulting update in G_{\texttt{core}} and accordingly modify the matching M_{\texttt{core}} . Next, we scan through all the edges in G_{\texttt{new}} and greedily add as many of these edges as we can on top of M_{\texttt{core}} , subject to the condition that the resulting edge-set M_{\texttt{final}}\supseteq M_{\texttt{core}} remains a valid matching in G . This scan takes O(|E_{\texttt{new}}|)=O(\delta n) time. It is easy to verify that the matching M_{\texttt{final}} we obtain at the end of our scan is a maximal matching in G . To summarize, with an additive overhead of O(\delta n) update time, we can convert the decremental maximal matching algorithm from Section 4 into a fully dynamic algorithm. Finally, looking back at the analysis from Section 4.4 , it is easy to verify that this additive overhead of O(\delta n) does not degrade our overall asymptotic update time (the values of \delta,B remain the same as in Section 4.4 ). 5 Decremental Perfect Matching in Graphs with Degree Gap We say that a bipartite graph G=(L,R,E) has a \gamma -degree-gap at X if \mathrm{deg}_{G}(v)\geq X for all v\in L and \mathrm{deg}_{G}(v)\leq X(1-\gamma) for all v\in R . Note that if \gamma\geq 0 , then, by Hall’s theorem, there exists a matching M that is left-perfect , i.e., M matches every vertex in L . Lemma 5.1 . Let G=(L,R,E) be a bipartite graph with initial \gamma -degree-gap at X . We can build a data structure LPM (stands for Left Perfect Matching) on G that maintains a matching M and supports the following operations: • \mathrm{Init}(M_{0}) where M_{0} is a matching in G before any update: M\leftarrow M_{0} . • \mathrm{Delete}(u,v) where (u,v)\in E(L,R) : set G\leftarrow G-(u,v) and M\leftarrow M-(u,v) . If \mathrm{deg}_{G}(u)q_{\textrm{ep}} then 12 ResetES( ) and break. 13 if \mathrm{deg}_{G}(u)1 only if v\in R_{\textrm{aff}} . Structural Lemma The key to the analysis is showing that within a single epoch, most vertices in T_{\mathrm{res}} always have low distance to t . We cannot directly apply Lemma 5.2 because edges in T_{\mathrm{res}} can have positive weight. But by Observation 5.16 , the number of edges (v,t) with weight >1 is at most q_{\textrm{ep}} . We are thus able to show that the majority of vertices are unaffected and have \mathrm{dist}(v,t)=O(\log(n)/\gamma) , as in Lemma 5.2 . To formalize the above intuition, we use the following structural lemma, which is a generalization of Lemma 5.2 . It shows that in a degree-gap graph, if we mark an arbitrary small set of vertices in R , then most vertices in L still have a short augmenting path to an unmarked free vertex. 5.17 . Let G=(L,R,E) be a bipartite graph with \gamma -degree-gap at X and let |L|=n . Let M be any left-perfect matching in G . Then, given any set of marked right-vertices R_{\textrm{mark}}\subseteq R , there exists a set L_{\textrm{far}}\subseteq L with |L_{\textrm{far}}|\leq\frac{2}{\gamma}\cdot|R_{\textrm{mark}}| , such that for every vertex u\in L\setminus L_{\textrm{far}} , there exists an alternating path P from u that starts with an edge e\notin M , ends at an unmarked M -free vertex, and has length at most 4\ln(n)/\gamma=O(\log(n)/\gamma) . We defer the proof of Lemma 5.17 to the next section. Here we show how to complete the analysis of LPM using the lemma as a black box. 5.18 . Consider any epoch. There exists a set of vertices V_{\textrm{far}} with |V_{\textrm{far}}|=O(q_{\textrm{ep}}/\gamma) , such that for every v\in V\setminus V_{\textrm{far}} , \mathrm{dist}_{\textrm{max}}(v,t)=O(\log(n)/\gamma) . 7 7 7 Since the entire ES -tree data structure is reset at the end of the epoch, \mathrm{dist}_{\textrm{max}} refers to the maximum distance within a single epoch. Proof. Proof of Corollary Let G be the graph and M the matching at end of the epoch. Recall that G initially has \gamma -degree-gap at X by the statement of Lemma 5.1 . Observe that G continues to have \gamma -degree-gap at X throughout the execution of LPM : the degree constraint for R holds automatically because the update sequence is decremental, and the degree constraint for L holds because Line 1 of algorithm LPM removes violating vertices from the graph. Applying Lemma 5.17 with R_{\textrm{mark}}=R_{\textrm{aff}} yields a set L_{\textrm{far}} such that every v\in L\setminus L_{\textrm{far}} has an alternating path of length O(\log(n)/\gamma) to a free vertex x\notin R_{\textrm{aff}} . By observation Observation 5.16 , we have w(x,t)=1 , so \mathrm{dist}(v,t)=O(\log(n)/\gamma) . Since distances in the ES-tree T_{\mathrm{res}} are only increasing, and since we are considering the graph at the end of the epoch, we have \mathrm{dist}_{\textrm{max}}(v,t)=\mathrm{dist}(v,t)=O(\log(n)/\gamma) . We now need to consider vertices in R at the end of the epoch. Any v\in R that is free and not in R_{\textrm{aff}} has \mathrm{dist}_{\textrm{max}}(v,t)=\mathrm{dist}(v,t)=w(v,t)=1 . Any vertex v\in R that is matched to a vertex in L\setminus L_{\textrm{far}} can follow a single edge to its mate and then an augmenting path to t , so also has \mathrm{dist}_{\textrm{max}}(v,t)=\mathrm{dist}(v,t)=O(\log(n)/\gamma) . This leaves at most |R_{\textrm{aff}}|+|L_{\textrm{far}}|=O(q_{\textrm{ep}}/\gamma) vertices, all of which can be added to V_{\textrm{far}} . ∎ We couple the above corollary with a bound on \mathrm{dist}_{\textrm{max}}(v,t) that applies even to v\in V_{\textrm{far}} . 5.19 . Every vertex v\in G has \mathrm{dist}_{G_{\textrm{res}}}(v,t)=O((1+|R_{\textrm{aff}}|)\cdot\frac{\log(n)}{\gamma})=O(q_{\textrm{ep}}\cdot\frac{\log(n)}{\gamma}) Proof. Recall that each \textrm{LPM}.\textrm{Delete} adss at most one vertex to R_{\textrm{aff}} . We will prove the following subclaim for some large enough constant C : while |R_{\textrm{aff}}|\leq k , the maximum weight in G_{\textrm{res}} is \leq(k+1)C\frac{\log(n)}{\gamma} ; Claim 5.19 then follows from 5.12 and Lemma 5.2 (recall that only the edges into t can have weight >1 , so every vt path contains at most one edge of weight >1 ). The base case is that while no vertices are affected, all weights in G_{\textrm{res}} are 1 , so the subclaim follows from Lemma 5.2 . Now assume that the subclaim holds for |R_{\textrm{aff}}|\leq k-1 and let v_{k}\in R be the kth vertex in R_{\textrm{aff}} , which can only occur as a result of some \textrm{LPM}.\textrm{Delete}(u,v_{k}) . The LPM data structure adds edge (v_{k},t) to G_{\textrm{res}} ; the weight of this edge is the distance \mathrm{dist}(v_{k},t) before the deletion of (u,v_{k}) . We now complete the proof by showing that before the deletion of (u,v_{k}) , \mathrm{dist}(v_{k},t)\leq kC\log(n)/\gamma : by Lemma 5.2 there exists an augmenting path of length \leq C\log(n)/\gamma in G from v_{k} to some free vertex v^{\prime}\in R , and by the induction hypothesis there is an edge (v^{\prime},t)\in G_{\textrm{res}} of weight w(v^{\prime},t)\leq(k-1)C\log(n)/\gamma . ∎ We are now ready to analyze the total update time of the ES tree. 5.20 . The total running time of data structure LPM during a single epoch is O(\Delta\cdot n\cdot\frac{\log(n)}{\gamma}+\Delta\frac{q_{\textrm{ep}}^{2}\log(n)}{\gamma^{2}}) Proof. The running time is clearly dominated by the time to maintain the ES data structure. Recall that the running time of the latter is O(\textrm{total \# updates}+\sum_{v\in V}\mathrm{deg}_{\textrm{max}}(v)\cdot\mathrm{dist}_{\textrm{max}}(v,t)). We bound the second term by \displaystyle\sum_{v\in V}\mathrm{deg}_{\textrm{max}}(v)\cdot\mathrm{dist}_{\textrm{max}}(v,t) \displaystyle\leq \displaystyle\Delta\sum_{v\in V}\mathrm{dist}_{\textrm{max}}(v,t) \displaystyle\leq\quad(\Delta\textrm{ is max degree}) \displaystyle\Delta\sum_{v\in V\setminus V_{\textrm{far}}}\mathrm{dist}_{\textrm{max}}(v,t)+\Delta\sum_{v\in V_{\textrm{far}}}\mathrm{dist}_{\textrm{max}}(v,t) \displaystyle\leq \displaystyle\Delta\cdot|V\setminus V_{\textrm{far}}|\cdot\frac{\log(n)}{\gamma}+\Delta\cdot|V_{\textrm{far}}|\cdot q_{\textrm{ep}}\cdot\frac{\log(n)}{\gamma} \displaystyle\leq\quad(\textrm{Claims \ref{cor:short-path},\ref{claim:aff-length}}) \displaystyle\Delta\cdot n\cdot\frac{\log(n)}{\gamma}+\Delta\cdot\frac{q_{\textrm{ep}}^{2}\log(n)}{\gamma^{2}} \displaystyle\phantom{\leq}\quad\ \ (\textrm{\lx@cref{creftypecap~refnum}{cor:short-path}}) We now need to bound the total number of updates to the ES tree. Every \textrm{LPM}.\textrm{Delete} operation only causes O(1) updates to the ES tree, for a total of q_{\textrm{ep}} . It remains to analyze \textrm{LPM}.\textrm{Augment}(u) operations. Each such operation involves flipping every edge on the augmenting path, which amounts to O(\mathrm{dist}(u,t)) operations to the ES data structure, because \mathrm{dist}(u,t) is an upper bound on the number of edges in the ut augmenting path found by \textrm{LPM}.\textrm{Augment}(u) (it may not be a tight upper bound because G_{\textrm{res}} can have weights >1 ). Let us consider how many \textrm{Augment}(u) operations can occur within a single epoch. When the epoch starts some vertices can be free, and each of these free vertices can undergo an Augment operation. But for any vertex u , every \textrm{Augment}(u) operation in the epoch beyond the first must have been preceded by some \textrm{Delete}(u,v) , since that is the only way u could become free again. Thus in total there can be a single \textrm{Augment}(u) for every vertex u , as well as q_{\textrm{ep}} additional Augment operations that can distributed arbitrarily among the vertices. By Claim 5.19 , we have: \textrm{[total \# updates] to }\textrm{{ES}}\leq\sum_{u\in L}\mathrm{dist}_{\textrm{max}}(u,t)+q_{\textrm{ep}}\cdot\frac{q_{\textrm{ep}}\log(n)}{\gamma} We conclude the claim by noting that the term \sum_{u\in L}\mathrm{dist}_{\textrm{max}}(u,t) is dominated by term \sum_{v\in V}\mathrm{deg}_{\textrm{max}}(v)\cdot\mathrm{dist}_{\textrm{max}}(v,t) , which we already bounded in the long equation above. ∎ Proof of Lemma 5.1 ( 1 ). It is easy to check that the total update time of LPM is dominated by the time to maintain the ES structure. Choosing q_{\textrm{ep}}=\sqrt{n\gamma} results in a total of at most 1+u/q_{\textrm{ep}} epochs (Recall that u is the total number of calls to \textrm{LPM}.\textrm{Delete} ). Applying Lemma 5.20 yields the bound in Lemma 5.1 . ∎ 5.3.5 Proof of Lemma 5.17 Recall that we refer to vertices in R_{\textrm{mark}} as marked. Define L_{i}(v)\subseteq L to be the set of all vertices u\in L satisfying the following property: the shortest alternating path (w.r.t. M ) from u , which starts with an unmatched edge e\in E\setminus M incident on u and ends at an M -free vertex in R\setminus R_{\textrm{mark}} , has length exactly i . Define R_{i}(v) to be the vertices matched to L_{i}(v) by M : so |L_{i}(v)|=|R_{i}(v)| . We define L_{\leq i}=\bigcup_{j\leq i}L_{j} and define L_{i} , and L_{\geq i} analogously. The key to the proof is the following claim. 5.21 . Say that |L_{>i}|\geq\frac{2}{\gamma}|R_{\textrm{mark}}| . Then, |L_{i+1}|\geq\frac{\gamma}{2}\cdot|L_{>i}| . proof of claim: We know that |R_{>i}|=|L_{>i}| . Define R^{\prime}=R_{>i}\cup R_{\textrm{mark}} and note that by assumption of the claim |R^{\prime}|\leq|R_{>i}|(1+\gamma/2)=|L_{>i}|(1+\gamma/2). (6) Now, clearly L_{i+1}=L_{>i}-L_{\geq i+2} We now upper bound |L_{\geq i+2}| . It is easy to see that every vertex in L_{\geq i+2} has the property that all of its edges are incident to R^{\prime} . Since G has a \gamma -degree gap at X , counting the edges implies: X\cdot|L_{\geq i+2}|\leq(1-\gamma)X\cdot|R^{\prime}| Rearranging and appying Equation 6 implies |L_{\geq i+2}|\leq(1-\gamma)|R^{\prime}|\leq(1-\gamma)(1+\gamma/2)|R_{>i}|\leq(1-\gamma/2)|R_{>i}|=(1-\gamma/2)|L_{>i}| This implies that |L_{i+1}|=|L_{>i}|-|L_{\geq i+2}|\geq\frac{\gamma}{2}\cdot|L_{>i}| Proof of Lemma 5.17 given Claim 5.21 Let \delta=\frac{4}{\gamma}\ln(n) . We will show that |L_{>\delta}|\leq\frac{2}{\gamma}|R_{\textrm{mark}}| , which clearly implies Lemma 5.17 . Say for contradiction that |L_{>\delta}|>\frac{2}{\gamma}|R_{\textrm{mark}}| . This clearly implies that |L_{>j}|>\frac{2}{\gamma}|R_{\textrm{mark}}| for any j<\delta . But this means that for any j<\delta we can apply Claim 5.21 , which in turn implies that for any j<\delta we have |L_{>j}|=|L_{>j+1}|+|L_{j+1}|\geq|L_{>j+1}|+\frac{\gamma}{2}\cdot|L_{>j}|\geq(1+\frac{\gamma}{2})|L_{>j+1}| The above equation, combined with the fact that for any x>1 we have (1+1/x)^{2x}>e , implies: |L|=|L_{>0}|\geq|L_{>\delta}|\cdot(1+\frac{\gamma}{2})^{\delta}=|L_{>\delta}|\cdot(1+\frac{\gamma}{2})^{\frac{4}{\gamma}\ln(n)}>e^{\ln(n)}=n, which contradicts the definition |L|=n . 6 Our Dynamic Maximal Matching Algorithm In this section, we present our dynamic algorithm for maximal matching, and prove Theorem 1.1 . We fix two parameters B\in[n] and \epsilon\in(0,1) whose values will be determined later on, and define \delta:=100\epsilon. (7) The reader should think of B=n^{\alpha} and \epsilon=1/n^{\beta} , where 0<\beta<\alpha<1 are some absolute constants. 6.1 The Framework Let G=(V,E) be the input graph undergoing edge updates. We maintain a (B,(1-\epsilon)B) - EDCS H:=(V,E(H)) of G at all times, as per Theorem 2.2 . This incurs an update time of O\left(\frac{n}{B\epsilon}\right) . The EDCS H is maintained explicitly, and we can make adjacency-list and adjacency-matrix queries to H whenever we want. It takes O(1) time to get the answer to any such query. Our dynamic maximal matching algorithm works in phases , where each phase consists of \delta n consecutive updates in G . We next introduce the concept of the core subgraph G_{\texttt{core}}:=\left(V,E_{\texttt{core}}\right) . At the start of any given phase, we have E_{\texttt{core}}:=E . Subsequently, during the phase, the subgraph G_{\texttt{core}} evolves as follows. Whenever an edge e gets deleted from G , we set E_{\texttt{core}}\leftarrow E_{\texttt{core}}\setminus\{e\} . In contrast, whenever an edge e gets inserted into G , we leave the set E_{\texttt{core}} unchanged. This ensures that within any given phase G_{\texttt{core}} is a decremental graph, with E_{\texttt{core}}\subseteq E at all times. Our first task will be to efficiently maintain a matching M_{\texttt{base}}\subseteq E_{\texttt{core}} in the core subgraph, which we will refer to as the base matching . This base matching will satisfy certain desirable properties (see Lemma 6.6 ). Let G_{\texttt{adj}}:=(V_{\texttt{adj}},E_{\texttt{adj}}) denote the subgraph of G induced by the set of nodes that are unmatched under M_{\texttt{base}} , that is, V_{\texttt{adj}}:=V\setminus V(M_{\texttt{base}}) and E_{\texttt{adj}}:=\{(u,v)\in E:u,v\in V_{\texttt{adj}}\} . We will refer to G_{\texttt{adj}} as the adjunct subgraph of G w.r.t. M_{\texttt{base}} . Next, we will show how to efficiently maintain a maximal matching M_{\texttt{adj}}\subseteq E_{\texttt{adj}} in G_{\texttt{adj}} , which will be called the adjunct matching (see Lemma 6.14 ). This will immediately imply that M_{\texttt{final}}:=M_{\texttt{base}}\cup M_{\texttt{adj}} is a maximal matching in G=(V,E) ; and M_{\texttt{final}} will be the output of our dynamic algorithm. At this point, the reader might get alarmed because G_{\texttt{adj}} undergoes node-updates every time an edge gets added to/removed from M_{\texttt{base}} , which might indicate that it is impossible to efficiently maintain a maximal matching in G_{\texttt{adj}} . To overcome this barrier, we will ensure that: (i) the arboricity of G_{\texttt{adj}} is sublinear in n ; (ii) the node-updates in G_{\texttt{adj}} satisfy some nice properties, so that coupled with (i) we can maintain the matching M_{\texttt{adj}} in sublinear in n update time. Organization of the rest of Section 6 . In Section 6.2 , we present a classification of nodes according to their degrees in H , which will be used to define the base and the adjunct matchings. In Sections 6.3 and 6.4 , we respectively show how to maintain the matchings M_{\texttt{base}} and M_{\texttt{adj}} (see Lemma 6.6 and Lemma 6.14 ). Finally, we prove Theorem 1.1 in Section 6.5 . 6.2 Classification of Nodes according to EDCS Degrees To define the base-matching, we first need to classify the nodes in V into the following categories. Let G_{\texttt{init}}=(V,E_{\texttt{init}}) and H_{\texttt{init}}=(V,E(H_{\texttt{init}})) respectively denote the status of the input graph G and the EDCS H at the start of a given phase. Then throughout that phase: • a node v\in V is high if \mathrm{deg}_{H_{\texttt{init}}}(v)\geq\left(\frac{1}{2}+\delta-\epsilon\right)B , • a high node v\in V is very-high if \mathrm{deg}_{H_{\texttt{init}}}(v)>\left(\frac{1}{2}+\delta\right)B , • a node v\in V is medium if \left(\frac{1}{2}-\delta\right)B\leq\mathrm{deg}_{H_{\texttt{init}}}(v)<\left(\frac{1}{2}+\delta-\epsilon\right)B , • a medium node v\in V is almost-low if \mathrm{deg}_{H_{\texttt{init}}}(v)\leq\left(\frac{1}{2}-\delta+\epsilon\right)B , and • a node v\in V is low if \mathrm{deg}_{H_{\texttt{init}}}(v)<\left(\frac{1}{2}-\delta\right)B . Let V_{\texttt{hi}},V_{\texttt{v-hi}},V_{\texttt{med}},V_{\texttt{a-lo}} and V_{\texttt{lo}} respectively denote the sets of high, very-high, medium, almost-low and low nodes. Note that these sets remain fixed throughout the duration of a phase ; they change only when the current phase ends and the next phase starts. The main reason why we use this classification is to ensure the proposition below. Proposition 6.1 . The following properties hold. 1. Consider any edge (u,v)\in E(H_{\texttt{init}}) where u is very-high. Then v must be low. 2. Consider any edge (u,v)\in E(H_{\texttt{init}}) where u is high. Then v must be either low or almost-low. 3. Consider any edge e\in E_{\texttt{init}} whose one endpoint is low and the other endpoint is either low or medium. Then such an edge e must appear in H_{\texttt{init}} . Proof. For part ( 1 ) , note that since (u,v)\in E(H_{\texttt{init}}) , we have \mathrm{deg}_{H_{\texttt{init}}}(u)+\mathrm{deg}_{H_{\texttt{init}}}(v)\leq B (see Definition 2.1 ). Furthermore, since u is very-high, we have \mathrm{deg}_{H_{\texttt{init}}}(u)>\left(\frac{1}{2}+\delta\right)B . Thus, it follows that \mathrm{deg}_{H_{\texttt{init}}}(v)\leq B-\mathrm{deg}_{H_{\texttt{init}}}(u)<\left(\frac{1}{2}-\delta\right)B , and so v must be a low node. For part ( 2 ) , note that since (u,v)\in E(H_{\texttt{init}}) , we have \mathrm{deg}_{H_{\texttt{init}}}(u)+\mathrm{deg}_{H_{\texttt{init}}}(v)\leq B (see Definition 2.1 ). Next, since u is high, we have \mathrm{deg}_{H_{\texttt{init}}}(u)\geq\left(\frac{1}{2}+\delta-\epsilon\right)B . Thus, it follows that \mathrm{deg}_{H_{\texttt{init}}}(v)\leq B-\mathrm{deg}_{H_{\texttt{init}}}(u)\leq\left(\frac{1}{2}-\delta+\epsilon\right)B . Accordingly, the node v is either low or almost-low. For part ( 3 ) , let e=(u,v) , where u is low and v is either low or medium. Then \mathrm{deg}_{H_{\texttt{init}}}(u)<\left(\frac{1}{2}-\delta\right)B and \mathrm{deg}_{H_{\texttt{init}}}(v)<\left(\frac{1}{2}+\delta-\epsilon\right)B , and hence \mathrm{deg}_{H_{\texttt{init}}}(u)+\mathrm{deg}_{H_{\texttt{init}}}(v)<(1-\epsilon)B . As H_{\texttt{init}} is a (B,(1-\epsilon)B) -EDCS of G_{\texttt{init}} , it follows that (u,v)\in E\left(H_{\texttt{init}}\right) (see Definition 2.1 ). ∎ Before concluding this section, we introduce one last category of nodes, as follows. 6.2 . At any point in time within a phase, let H_{\texttt{core}} denote the subgraph of H_{\texttt{init}} restricted to the edges in G_{\texttt{core}} . Specifically, we define H_{\texttt{core}}:=\left(V,E(H_{\texttt{core}})\right) , where E(H_{\texttt{core}}):=E\left(H_{\texttt{init}}\right)\cap E_{\texttt{core}} . Now, consider a high node v\in V_{\texttt{hi}} . At any point in time within the current phase, we say that v is damaged if \mathrm{deg}_{H_{\texttt{core}}}(v)<\left(\frac{1}{2}+\delta-2\epsilon\right)B , and safe otherwise. We let V_{\texttt{dmg}}\subseteq V_{\texttt{hi}} and V_{\texttt{sf}}:=V_{\texttt{hi}}\setminus V_{\texttt{dmg}} respectively denote the sets of damaged and safe nodes. Recall that \mathrm{deg}_{H_{\texttt{init}}}(v)\geq\left(\frac{1}{2}+\delta-\epsilon\right)B for all nodes v\in V_{\texttt{hi}} . Thus, for such a node to get damaged at least \epsilon B many of its incident edges must be deleted since the start of the phase. Since each phase lasts for \delta n updates in G and \delta=100\epsilon (see ( 7 )), we get the following important corollary. Corollary 6.3 . We always have \left|V_{\texttt{dmg}}\right|\leq\frac{2\delta n}{\epsilon B}=O\left(\frac{n}{B}\right) . Furthermore, at the start of a phase we have V_{\texttt{dmg}}=\emptyset . Subsequently, during the phase, the subset V_{\texttt{dmg}} grows monotonically over time. 6.3 Maintaining the Base Matching We will show how to maintain the matching M_{\texttt{base}}\subseteq E(H_{\texttt{core}}) , satisfying two conditions. 6.4 specifies which nodes are matched under M_{\texttt{base}} , whereas 6.5 ensures the “stability” of the base matching as the input graph G undergoes updates within a given phase. 6.4 . Every safe high node is matched under M_{\texttt{base}} , and every damaged high node is free under M_{\texttt{base}} . Furthermore, at most 22\delta n medium nodes are free under M_{\texttt{base}} . 6.5 . Consider any update in G within a given phase. Due to this update, at most O(1) nodes get inserted into/deleted from the set V(M_{\texttt{base}}) . Our main result in this section is summarized below. Lemma 6.6 . We can maintain a matching M_{\texttt{base}}\subseteq E(H_{\texttt{core}}) satisfying 6.4 and 6.5 by: 1. either a deterministic algorithm with \tilde{O}\left(B\cdot n^{1/2}\cdot\delta^{-3/2}\right) amortized update time; or 2. a randomized algorithm with \tilde{O}\left(B\cdot\delta^{-1}+\delta^{-3}\right) amortized update time. The algorithm is correct with high probability against an adaptive adversary. Our algorithm for maintaining the matching M_{\texttt{base}} will make use of the following building blocks. • A matching M_{\texttt{most}}\subseteq E_{\texttt{init}} that will be computed at the start of each phase. • A matching M_{\texttt{hilo}} in a subgraph H_{\texttt{hilo}} , that will be maintained throughout the phase. The rest of Section 6.3 is organized as follows. In Section 6.3.1 , We first show how to compute the matching M_{\texttt{most}}\subseteq E_{\texttt{init}} at the start of a phase. Next, we define the subgraph H_{\texttt{hilo}} in Section 6.3.2 , and summarize some of its key properties. In Section 6.3.3 and Section 6.3.4 , we respectively show how to initialize the matchings M_{\texttt{hilo}} and M_{\texttt{base}} at the start of a phase, and how to maintain M_{\texttt{hilo}} and M_{\texttt{base}} throughout the updates within a phase. Finally, we put everything together in Section 6.3.5 and prove Lemma 6.6 . 6.3.1 Computing the matching M_{\texttt{most}} at the start of a phase Our main result in this section is summarized in the claim below (see Algorithm 2 for the pseudocode). 6.7 . At the start of a phase, we can compute a matching M_{\texttt{most}}\subseteq E(H_{\texttt{init}}) , such that at most 6\delta n nodes from the set V_{\texttt{hi}}\cup V_{\texttt{med}} are free under M_{\texttt{most}} . The matching M_{\texttt{most}} can be computed • either by a deterministic algorithm that runs in \tilde{O}\left(\frac{nB}{\delta}\right) time, • or by a randomized algorithm that runs in \tilde{O}\left(nB\right) time with high probability. Proof. At the start of a phase, let H^{\prime}_{\texttt{init}} be the subgraph of H_{\texttt{init}} obtained as follows. Initialize H^{\prime}_{\texttt{init}}\leftarrow H_{\texttt{init}} . Next, for each very-high node v\in V_{\texttt{v-hi}} , arbitrarily keep deleting edges (in H^{\prime}_{\texttt{init}} ) incident on v until \mathrm{deg}_{H^{\prime}_{\texttt{init}}}(v) becomes equal to \left(\frac{1}{2}+\delta\right)B . By part ( 1 ) of Proposition 6.1 , this procedure does not delete any edge incident on a medium or high node. Thus, when this procedure terminates, we have \left(\frac{1}{2}-\delta\right)B\leq\mathrm{deg}_{H^{\prime}_{\texttt{init}}}(v)\leq\left(\frac{1}{2}+\delta\right)B for every node v\in V_{\texttt{hi}}\cup V_{\texttt{med}} , and \mathrm{deg}_{H^{\prime}_{\texttt{init}}}(v)<\left(\frac{1}{2}-\delta\right)B for every node v\in V_{\texttt{lo}}=V\setminus(V_{\texttt{hi}}\cup V_{\texttt{med}}) . Next, we set: \kappa:=3\delta\text{ and }\Delta:=\left(\frac{1}{2}+\delta\right)B. (8) Since B=n^{\alpha} and \epsilon=1/n^{\beta} , for some absolute constants 0<\beta<\alpha<1 (see the comment after ( 7 )), and \delta=100\epsilon (see ( 7 )), we infer that \Delta\geq\frac{4}{\kappa} . Also, from the preceding discussion, it follows that \Delta is an upper bound on the maximum degree in H^{\prime}_{\texttt{init}} . We next apply the concerned subroutine (deterministic or randomized) from Lemma 3.1 , by setting G:=H^{\prime}_{\texttt{init}} , and the parameters \kappa,\Delta as in ( 8 ). Let M denote the matching returned by the subroutine from Lemma 3.1 . At this point, we set M_{\texttt{most}}\leftarrow M . Because of the way we have defined \kappa,\Delta in ( 8 ), it follows that \left(\frac{1}{2}-\delta\right)B\geq(1-\kappa)\Delta , and hence V_{\kappa}\supseteq V_{\texttt{hi}}\cup V_{\texttt{med}} (see Lemma 3.1 to recall the definition of V_{\kappa} ). From Lemma 3.1 , we now get: • When the phase starts, at most 2\kappa n=6\delta n nodes from V_{\texttt{hi}}\cup V_{\texttt{med}} are free under M_{\texttt{most}} . • Since H_{\texttt{init}} is a (B,(1-\epsilon)B) -EDCS of G_{\texttt{init}} , it has maximum degree at most B (see Definition 2.1 ). So, it takes O(nB) time to compute the subgraph H^{\prime}_{\texttt{init}} of H_{\texttt{init}} . After that, we can compute M_{\texttt{most}} either in \tilde{O}(nB/\delta) time deterministically, or in \tilde{O}(nB\delta) time with high probability. This leads to an overall deterministic time complexity of O(nB)+\tilde{O}(nB/\delta)=\tilde{O}(nB/\delta) , and an overall randomized time complexity of O(nB)+\tilde{O}(nB\delta)=\tilde{O}(nB) . This concludes the proof of the claim. ∎ Algorithm 2 Computing M_{\texttt{most}} . We run \texttt{Initialize-}M_{\texttt{most}}() at the start of a phase. 1 Function Initialize- M_{\texttt{most}} ( ) : 2 H_{\texttt{init}}^{\prime}\leftarrow H_{\texttt{init}} 3 for v\in V_{\texttt{v-hi}} do 4 while \mathrm{deg}_{H_{\texttt{init}}^{\prime}}(v)>(\frac{1}{2}+\delta)B do 5 Let e be an arbitrary edge incident on v in H^{\prime}_{\texttt{init}} 6 H_{\texttt{init}}^{\prime}\leftarrow H_{\texttt{init}}^{\prime}\setminus\{e\} 7 M_{\texttt{most}}\leftarrow apply the algorithm of Lemma 3.1 on H_{\texttt{init}}^{\prime} , with \kappa:=3\delta and \Delta:=\left(\frac{1}{2}+\delta\right)B 6.3.2 The subgraph H_{\texttt{hilo}} We define the subgraph H_{\texttt{hilo}}:=(V_{\texttt{hilo}},E(H_{\texttt{hilo}})) as follows: E(H_{\texttt{hilo}}):=\left\{(u,v)\in E(H_{\texttt{core}}):\{u,v\}\cap V_{\texttt{hi}}\neq\emptyset\right\}\text{ and }V_{\texttt{hilo}}:=V_{\texttt{hi}}\cup(V_{\texttt{lo}}\cup V_{\texttt{a-lo}}). (9) In words, E(H_{\texttt{hilo}}) is the set of all the edges in H_{\texttt{core}} incident on the high nodes, and V_{\texttt{hilo}} is the set of all nodes that are either hi, or low, or almost-low. Since E(H_{\texttt{core}})\subseteq E(H_{\texttt{init}}) , part-( 2 ) of Proposition 6.1 implies that every edge in E(H_{\texttt{hilo}}) has one endpoint in V_{\texttt{hi}} and the other endpoint in V_{\texttt{lo}}\cup V_{\texttt{a-lo}} . Thus, H_{\texttt{hilo}} is a bipartite subgraph of H_{\texttt{core}} . We will designate the nodes in V_{\texttt{hi}} as being on the “left”, and the nodes in V_{\texttt{lo}}\cup V_{\texttt{a-lo}} as being on the “right”. We also define two parameters X,\gamma as in ( 10 ), which allow us to derive some useful properties of the subgraph H_{\texttt{hilo}} . This sets up the stage so that we can apply Lemma 5.1 on H_{\texttt{hilo}} . X:=\left(\frac{1}{2}+\delta-2\epsilon\right)B\text{ and }\gamma:=\frac{\delta}{10^{8}}. (10) 6.8 . Fix \gamma and X as defined in ( 10 ). Then H_{\texttt{hilo}} is a bipartite subgraph of H_{\texttt{core}} whose edges cross between V_{\texttt{hi}} (on the left) and V_{\texttt{lo}}\cup V_{\texttt{a-lo}} (on the right). 1. At the start of any given phase, H_{\texttt{hilo}} has an initial \gamma -degree gap at X . 2. Subsequently, during the phase: (a) We always have \mathrm{deg}_{H_{\texttt{hilo}}}(v)\geq X for all nodes v\in V_{\texttt{sf}}\subseteq V_{\texttt{hi}} , and \mathrm{deg}_{H_{\texttt{hilo}}}(v)0 then 33 v^{\prime}\leftarrow arbitrary element of S 34 Insert- M_{\texttt{adj}} ( (v^{\prime},w) ) 35 \triangleright Called when an edge is deleted from E_{\texttt{adj}} 36 Function Delete- E_{\texttt{adj}} ( u,v ) : 37 E_{\texttt{adj}}\leftarrow E_{\texttt{adj}}\setminus\{(u,v)\} 38 if (u,v)\notin M_{\texttt{adj}} then 39 Update \mathcal{F}_{(v)} and \mathcal{F}_{(u)} 40 else 41 Delete- M_{\texttt{adj}} ( (u,v) ) Lemma 6.14 . Suppose that we maintain the matching M_{\texttt{base}} as per Lemma 6.6 . Then with an additive overhead of \tilde{O}\left(\delta n+\frac{B}{\delta}+\frac{n}{\delta B}\right) amortized update time, we can deterministically and explicitly maintain a maximal matching M_{\texttt{adj}}\subseteq E_{\texttt{adj}} in G_{\texttt{adj}} . We devote the rest of Section 6.4 to the proof of Lemma 6.14 . We start by summarizing a few key properties of the adjunct graph G_{\texttt{adj}} in the claim below. 6.15 . The adjunct graph G_{\texttt{adj}} satisfies the following properties at all times. 1. V_{\texttt{sf}}\cap V_{\texttt{adj}}=\emptyset . 2. V_{\texttt{dmg}}\subseteq V_{\texttt{adj}} and \left|V_{\texttt{dmg}}\right|=O\left(\frac{n}{B}\right) . Moreover, V_{\texttt{dmg}}=\emptyset at the start of a phase. 3. \left|V_{\texttt{med}}\cap V_{\texttt{adj}}\right|\leq 22\delta n . Proof. Part-( 1 ) All nodes of V_{\texttt{sf}} are matched by M_{\texttt{base}} (Condition 6.4 ) hence no nodes of V_{\texttt{sf}} are in V_{\texttt{adj}}=V\setminus V(M_{\texttt{base}}) . Part-( 2 ) V_{\texttt{dmg}} is initialized as empty at the start of each phase and any node which is moved to V_{\texttt{dmg}} from V_{\texttt{sf}} has its matching M_{\texttt{base}} edge removed hence V_{\texttt{dmg}}\subseteq V_{\texttt{adj}} . |V_{\texttt{dmg}}|=O\left(\frac{n}{B}\right) at all times due to Corollary 6.3 . Part-( 3 ) At initialization by Claim 6.9 at most 18n\delta vertices of V_{\texttt{med}} are unmatched by M_{\texttt{base}} . As phase consists of \delta n updates and each update may unmatch at most two nodes of V_{\texttt{med}} in M_{\texttt{base}} we must have that |V_{\texttt{med}}\cap V_{\texttt{adj}}|=|V_{\texttt{med}}\setminus V(M_{\texttt{base}})|\leq 22\delta n . ∎ 6.16 . For all nodes v\in V_{\texttt{adj}}\setminus V_{\texttt{dmg}} , we have \mathrm{deg}_{G_{\texttt{adj}}}(v)=O\left(\delta n+B+\frac{n}{B}\right) at all times. Proof. Consider any node v\in V_{\texttt{adj}}\setminus V_{\texttt{dmg}} . By part-( 1 ) of 6.15 , we have v\notin V_{\texttt{sf}} , and hence v\notin V_{\texttt{hi}} (see Definition 6.2 ). As the node-set V is partitioned into the subsets V_{\texttt{lo}},V_{\texttt{med}},V_{\texttt{hi}} (see Section 6.2 ), it follows that v\in V_{\texttt{lo}}\cup V_{\texttt{med}} . Since each phase lasts for \delta n updates in G , we infer that |E\setminus E_{\texttt{init}}|\leq\delta n (see Section 6.2 ). Thus, the node v can have at most \delta n incident edges in G_{\texttt{adj}} that are part of E\setminus E_{\texttt{init}} . Henceforth, we focus on bounding the number of incident edges on v in G_{res} that are part of E\cap E_{\texttt{init}} . We start by partitioning this concerned set of edges into three subsets, depending on their other endpoints: \displaystyle Z_{\texttt{lo}} \displaystyle:= \displaystyle\{(u,v)\in E_{\texttt{adj}}\cap E_{\texttt{init}}:u\in V_{\texttt{lo}}\cap V_{\texttt{adj}}\}, \displaystyle Z_{\texttt{med}} \displaystyle:= \displaystyle\{(u,v)\in E_{\texttt{adj}}\cap E_{\texttt{init}}:u\in V_{\texttt{med}}\cap V_{\texttt{adj}}\}, \displaystyle Z_{\texttt{hi}} \displaystyle:= \displaystyle\{(u,v)\in E_{\texttt{adj}}\cap E_{\texttt{init}}:u\in V_{\texttt{hi}}\cap V_{\texttt{adj}}\}. By part-( 3 ) of Proposition 6.1 , we have Z_{\texttt{lo}}\subseteq E(H_{\texttt{init}}) . Since H_{\texttt{init}} is a (B,(1-\epsilon)B) -EDCS of G_{\texttt{init}} , it has maximum degree B (see Definition 2.1 ), and hence we get |Z_{\texttt{lo}}|\leq B . Next, part-( 3 ) of 6.15 implies that |Z_{\texttt{med}}|\leq 22\delta n=O(\delta n) . Finally, since V=V_{\texttt{sf}}\cup V_{\texttt{dmg}} (see Definition 6.2 ), by part-( 1 ) and part-( 2 ), we get |Z_{\texttt{hi}}|=O\left(\frac{n}{B}\right) . From the preceding discussion, it follows that \mathrm{deg}_{G_{\texttt{adj}}}(v)=O\left(\delta n+B+\frac{n}{B}\right) . ∎ 6.17 . At the start of a phase, we have |E_{\texttt{adj}}|=O(\delta n\cdot\delta n+Bn) . Proof. At the start of a phase, we have V_{\texttt{adj}}\cap V_{\texttt{hi}}=(V_{\texttt{adj}}\cap V_{\texttt{sf}})\cup(V_{\texttt{adj}}\cap V_{\texttt{dmg}})=\emptyset , by Definition 6.2 and part-( 1 ) and part-( 2 ) of 6.15 . Accordingly, at this point in time, the node-set V_{\texttt{adj}} is partitioned into two subsets: V_{\texttt{adj}}\cap V_{\texttt{lo}} and V_{\texttt{adj}}\cap V_{\texttt{med}} . By part-( 3 ) of 6.15 , there are at most O(\delta n\cdot\delta n) edges in E_{\texttt{adj}} whose both endpoints are in V_{\texttt{adj}}\cap V_{\texttt{med}} . Next, consider any node u\in V_{\texttt{adj}}\cap V_{\texttt{lo}} . Since V_{\texttt{adj}}\cap V_{\texttt{hi}}=\emptyset at this point in time, every edge in E_{\texttt{adj}} that is incident on u has its other endpoint in V_{\texttt{lo}}\cup V_{\texttt{med}} (see Section 6.2 ). Accordingly, by part-( 3 ) of Proposition 6.1 , every edge in E_{\texttt{adj}}\subseteq E_{\texttt{init}} that is incident on u is part of H_{\texttt{init}} . Since H_{\texttt{init}} is a (B,(1-\epsilon)B) -EDCS of G_{\texttt{init}} , it has maximum degree B (see Definition 2.1 ). Thus, the node u\in V_{\texttt{adj}}\cup V_{\texttt{hi}} has degree at most B in G_{\texttt{adj}} , at this point in time. We conclude that there are at most O(nB) edges in E_{\texttt{adj}} that have some endpoint in V_{\texttt{adj}}\cap V_{\texttt{lo}} . From the preceding discussion, it follows that |E_{\texttt{adj}}|=O(\delta n\cdot\delta n+Bn) . ∎ 6.4.1 Proof of Lemma 6.14 . At the start of a phase, we initialize M_{\texttt{adj}} to be any arbitrary maximal matching in G_{\texttt{adj}} . By Corollary 6.17 , this takes O(\delta n\cdot\delta n+Bn) time. Since the phase lasts for \delta n updates in G , this step incurs an amortized update time of: O\left(\frac{\delta n\cdot\delta n+Bn}{\delta n}\right)=O\left(\delta n+\frac{B}{\delta}\right). (14) Subsequently, to handle the updates during a phase, we use the following auxiliary data structures: Each node v\in V_{\texttt{dmg}} maintains the set \mathcal{F}_{\texttt{adj}}(v):=\left\{u\in V_{\texttt{adj}}\setminus V(M_{\texttt{adj}}):(u,v)\in E_{\texttt{adj}}\right\} of its free neighbors (in G_{\texttt{adj}} ) under the matching M_{\texttt{adj}} . 9 9 9 Maximality of M_{\texttt{adj}} implies that \mathcal{F}_{\texttt{adj}}(v)=\emptyset for all v\in V_{\texttt{dmg}}\setminus V(M_{\texttt{adj}}) . Whenever a node v moves from V_{\texttt{sf}} to V_{\texttt{dmg}} , we spend \tilde{O}(n) time to initialize the set \mathcal{F}_{\texttt{adj}}(v) as a balanced search tree. Within a phase, a node can move from V_{\texttt{sf}} to V_{\texttt{dmg}} at most once (see Definition 6.2 and Corollary 6.3 ). Thus, by part-( 2 ) of 6.15 , these initializations take \tilde{O}\left(\frac{n}{B}\cdot n\right)=\tilde{O}\left(\frac{n^{2}}{B}\right) total time during a phase. As each phase lasts for \delta n updates in G , this incurs an amortized update time of \tilde{O}\left(\frac{n^{2}}{B\cdot\delta n}\right)=\tilde{O}\left(\frac{n}{\delta B}\right) . Since V_{\texttt{adj}}:=V\setminus V(M_{\texttt{base}}) , 6.5 and Lemma 6.6 imply that each edge update in G leads to O(1) node-updates in G_{\texttt{adj}} . Moreover, while maintaining the maximal matching M_{\texttt{adj}} in G_{\texttt{adj}} , a node-update can be handled in \tilde{O}\left(\delta n+B+\frac{n}{B}\right) worst-case time, for the following reason. Suppose that we are trying to find a free neighbor (if it exists) of some node v\in V_{\texttt{adj}} . This can be done in \mathrm{deg}_{G_{\texttt{adj}}}(v)=O\left(\delta n+B+\frac{n}{B}\right) time if v\in V_{\texttt{adj}}\setminus V_{\texttt{dmg}} (see Corollary 6.16 ), and in \tilde{O}(1) time if v\in V_{\texttt{dmg}} (using the set \mathcal{F}_{\texttt{adj}}(v) ). Further, once we decide to match a node u\in V_{\texttt{adj}} to one of its free neighbors, we can accordingly update all the relevant sets \mathcal{F}_{\texttt{adj}}(v) in \tilde{O}\left(\left|V_{\texttt{dmg}}\right|\right)=\tilde{O}\left(\frac{n}{B}\right) time (see part-( 2 ) of 6.15 ). To summarize, the amortized update time we incur, while maintaining the matching M_{\texttt{adj}} throughout the updates within a given phase, is at most: \tilde{O}\left(\frac{n}{\delta B}+\delta n+B+\frac{n}{B}\right)=\tilde{O}\left(\delta n+B+\frac{n}{\delta B}\right). (15) Lemma 6.14 follows from ( 14 ) and ( 15 ). 6.5 Wrapping Up: Proof of Theorem 1.1 Theorem 1.1 follows from Lemmas 6.6 and 6.14 . To be a bit more specific, first recall that maintaining the EDCS H incurs an update time of O\left(\frac{n}{\epsilon B}\right)=O\left(\frac{n}{\delta B}\right) , according to ( 7 ) and the first paragraph of Section 6.1 . Now, for the deterministic algorithm, part-( 1 ) of Lemma 6.6 incurs an amortized update time of \tilde{O}\left(B\cdot n^{1/2}\cdot\delta^{-3/2}\right) . Thus, by Lemma 6.14 , the overall amortized update time becomes O\left(\frac{n}{\delta B}\right)+\tilde{O}\left(B\cdot n^{1/2}\cdot\delta^{-3/2}\right)+\tilde{O}\left(\delta n+\frac{B}{\delta}+\frac{n}{\delta B}\right)=\tilde{O}(n^{8/9}),\text{ for }\delta=\frac{1}{n^{1/9}}\text{ and }B=n^{2/9}. Finally, for the randomized algorithm, part-( 2 ) of Lemma 6.6 incurs an amortized update time of \tilde{O}(B\delta^{-1}+\delta^{-3}) . Thus, by Lemma 6.14 , the overall amortized update time becomes O\left(\frac{n}{\delta B}\right)+\tilde{O}\left(\frac{B}{\delta}+\frac{1}{\delta^{3}}\right)+\tilde{O}\left(\delta n+\frac{B}{\delta}+\frac{n}{\delta B}\right)=\tilde{O}\left(n^{3/4}\right),\text{ for }\delta=\frac{1}{n^{1/4}}\text{ and }B=n^{1/2}. 7 Open Problems Our novel approach for maintaining a maximal matching suggests several interesting questions. The Right Answer. Fundamentally, how fast can we maintain a maximal matching against an adaptive adversary? Our approach inherently takes \Omega(\min\{\sqrt{n},\Delta\}) update time where \Delta is the maximum degree. This lower bounds simply follows from how it handles edge insertions. During a phase insertions are handled greedily. After each update the algorithm iterates over all edges inserted during the phase incident on affected vertices. Assuming that the length of the phase is \Omega(\sqrt{n}) this must take at least \Omega(\min(\sqrt{n},\Delta)) time. As at the start of the phase the algorithm needs to construct a maximal matching of the graph the initialization of a phase must take \Omega(n) time. Hence, in order to ensure that the amortized cost of the initializations is O(\sqrt{n}) over a phase the phase length has to be \Omega(\sqrt{n}) . Is there an algorithm against an adaptive adversary with o(\min\{\sqrt{n},\Delta\}) update time? Otherwise, is there a conditional lower bound refuting this hope, or even refuting polylogarithmic update time? The answer in either direction would be very exciting. Better Decremental Perfect Matching. The algorithm from Lemma 5.1 is the main bottleneck in our dynamic maximal matching algorithm. In the static setting, we can deterministically find a perfect matching in an m -edge graph with \gamma -degree-gap with \tilde{O}(m/\gamma) time, for example, using Dinic’s flow algorithm. Can we deterministically match this running time in the decremental setting? Such an algorithm would immediately imply a deterministic dynamic maximal matching algorithm with \tilde{O}(n^{4/5}) update time via our framework. We can also hope to improve our randomized update time further to \tilde{O}(n^{2/3}) . Currently, our amortized time for initializing each phase is \tilde{O}(\frac{n}{B\delta}+\delta n+\frac{B}{\delta}). But we can actually improve this to \tilde{O}(\frac{n}{B\delta}+\delta n+B) via warm-starting. We omit this because it alone does not lead to any improvement and will complicate the algorithm further. But, suppose that, in our randomized algorithm, the time spent on \mathrm{Augment(\cdot)} can be improved from \tilde{O}(1/\gamma^{3}) to \tilde{O}(1/\gamma^{2}) . Combining this with warm-starting would immediately improve the final update time from \tilde{O}(\frac{n}{B\delta}+\delta n+\frac{B}{\delta}+\frac{1}{\delta^{3}})=\tilde{O}(n^{3/4})\text{ by setting }\delta=\frac{1}{n^{1/4}}\text{ and }B=n^{1/2} to \tilde{O}(\frac{n}{B\delta}+\delta n+B+\frac{1}{\delta^{2}})=\tilde{O}(n^{2/3})\text{ by setting }\delta=\frac{1}{n^{1/3}}\text{ and }B=n^{2/3}, where the improvement from \frac{1}{\delta^{3}} to \frac{1}{\delta^{2}} is from the assumption on \mathrm{Augment(\cdot)} . Worst-case Update Time. Interestingly, it is open if there exists a dynamic maximal matching algorithm with o(n) worst-case update time, even against an oblivious adversary. Previous algorithms against an oblivious adversary inherently guarantee only amortized update time because they must spend a lot of time once the adversary “deletes the sampled edge”. Our algorithm might be a starting point to resolve this open problem. Indeed, our approach exploits amortization in a much more superficial manner. Within each phase, our randomized implementation inherently runs in worst-case update time. The deterministic implementation relies on periodic recomputation of the ’high-low’ matching data-structure. However, at the cost of a small blowup in update time these rebuilds can be avoided. Thus, it remains to spread the work for preprocessing at the beginning of each phase; the task has been easily handled in many other dynamic problems. The idea is to start the pre-processing of the next phase during the operations of the current phase. Once the current phase comes to an end the algorithm switches to the output of the already initialized next phase. This only comes at the cost of a constant blowup in update time. However, the switching process between the output of the current and next phase also has to be de-amortized. If the goal of the algorithm is to maintain a constant approximate matching this de-amortization process can be achieved with optimal update time trade-offs (see Solomon and Solomon [ SS21 ] ). Unfortunately, if our goal is to maintain a maximal matching the swtich between outputs becomes more challenging. A partial transformation of one maximal matching to an other one might leave some nodes with unmatched neighbors unmatched. Trivially, to resolve this we have to iterate over the neighborhood of these problematic nodes. However, here we are able to exploit the structure of our maximal matching. Its possible to ensure that none of these problematic nodes happens to be a high node. This in turn means that they may have a small number of potentially unmatched neighbors we need to iterate over to ensure maximallity. Note that we do not claim that our algorithm can trivially be improved to have worst-case update time. The above discussion ignores multiple situations which can occur due to updates to the current and next maximal matching maintained by the algorithm during the transformation process which appear technically complex to handle. Dynamic Symmetry Breaking. Within the distributed literature symmetry breaking problems have received significant attention (for a detailed list see [ BEPS16b ] ). In the context of distributed computing the process of solving these problems can be described as follows: initially all nodes are assigned the same state symmetrically. In every round nodes have to decide which sate they take in the next round which often has to be different for neighboring nodes. Hence, the process can be described as a task of symmetry breaking. Interestingly, various problems studied by the symmetry breaking distribution literature have received research attention in the dynamic model. Namely, (\Delta+1) -vertex coloring, maximal matching, and maximal independent set are all known to admit efficient distributed algorithms as well as polylogarithmic update time dynamic algorithms [ HP22 , Sol16b , CZ19 ] against an oblivious adversary. While there are known efficient deterministic distributed algorithms for these problems even against an adaptive adversary only maximal matching and (\Delta+1) -vertex coloring is known to admit a sub-linear update time dynamic algorithm. This proposes the question weather further symmetry breaking problems admit efficient adaptive or deterministic dynamic implementations and weather there is a deeper connection between distributed and dynamic algorithms in the context of symmetry breaking problems. Appendix A Convergence of Random Walks in Eulerian Expanders In this section, we prove Theorem 5.6 for completeness. We follow the notations from [ RTV06 ] . We say that a matrix M\in[0,1]^{V\times V} is a Markov chain with vertex set V if \sum_{v\in V}M(v,u)=1 for every vertex u . Given a directed graph G , the random walk matrix M_{G} of G is the matrix where, for each entry (v,u) , M_{G}(v,u)=\frac{|E_{G}(u,v)|}{\mathrm{deg}_{G}^{{\rm out}}(u)}. Observe that M_{G} is a Markov chain. We will only consider Eulerian graphs where the stationary distribution has a closed form. Fact A.1 (Example 1 of [ ACP16 ] ) . For any Eulerian graph G , the stationary distribution \pi\in[0,1]^{V} of the random walk is such that, for each vertex v\in V , \pi(v)=\mathrm{deg}_{G}(v)/\mathrm{vol}_{G}(V). For any S\subseteq V , let \pi(S)=\sum_{u\in S}\pi(u) . The conductance of a Markov chain is defined as follows. Definition A.2 (Definition 2.4 of [ RTV06 ] ) . Let M be a Markov chain with n vertices and \pi a stationary distribution. The conductance of M with respect to \pi is defined to be h_{\pi}(M)=\min_{A:0<\pi(A)\leq 1/2}\frac{\sum_{u\in A,v\notin A}\pi(u)M(v,u)}{\pi(A)} For an Eulerian graph G , observe that the conductance of M_{G} defined above coincides with the conductance of G defined in Equation 4 . That is, we have \Phi(G)=h_{\pi}(M_{G}). (16) We will omit the precise definition of the spectral expansion \lambda_{\pi}(M) of a Markov chain M . See [ RTV06 ] for details. We only needs the fact that \lambda_{\pi}(M) dictates the rate of convergence of the distribution of random walks to the stationary distribution, formalized as follows. For any vector x\in\mathbb{R}^{V} , let \|x\|_{\pi}=\sqrt{\sum_{v\in{\rm supp}(\pi)}\frac{x(v)^{2}}{\pi(v)}.} Lemma A.3 (Lemma 2.2 of [ RTV06 ] ) . Let \pi be a stationary distribution of Markov chain M on V , and let \alpha be any distribution on V such that {\rm supp}(\alpha)\subseteq{\rm supp}(\pi) . Then \|M^{k}\alpha-\pi\|_{\pi}\leq\lambda_{\pi}(M)^{k}\|\alpha-\pi\|_{\pi}. That is, the smaller \lambda_{\pi}(M) is the faster the convergence. We can bound \lambda_{\pi}(M) via conductance as follows. Lemma A.4 (Lemma 2.5 of [ RTV06 ] ) . Let M be a Markov chain on n vertices such that M(u,u)\geq 1/2 for every u , and let \pi be a stationary distribution of M . Then \lambda_{\pi}(M)\leq 1-h_{\pi}(M)^{2}/2 . With all lemmas above, we are now ready to prove Theorem 5.6 . Proof of Theorem 5.6 . Proof. We are given an Eulerian \phi -expander G=(V,E) with n vertices where, for each vertex v , the number of self loops at v is at least \mathrm{deg}(v)/2 . Let p denote the probability that a k -step random walk in G for k steps starting at vertex v ends at vertex t . Our goal is show that |p-\pi(t)| is small. Let \alpha be the distribution over V where \alpha(u)=1 if u=v and \alpha(u)=0 for u\neq v . Observe that M_{G}^{k}\alpha is precisely the distribution over V after making k random walk steps in G starting from vertex v . So p is precisely the t -th entry of M_{G}^{k}\alpha . By Lemma A.3 , we have that \|M_{G}^{k}\alpha-\pi\|_{\pi}\leq\lambda_{\pi}(M_{G})^{k}\|\alpha-\pi\|_{\pi}. Let x\in\mathbb{R}^{V} be obtained from M_{G}^{k}\alpha-\pi by restricting to only the t -th entry (i.e. x(u)=0 for all u\neq t ). On the one hand, we have \frac{|p-\pi(t)|}{\sqrt{\pi(t)}}=\|x\|_{\pi}\leq\|M_{G}^{k}\alpha-\pi\|_{\pi} one the other hand, we have \|\alpha-\pi\|_{\pi}\leq\sqrt{1/\pi(v)}. So we conclude that |p-\pi(t)|\leq(\lambda_{\pi}(M_{G})^{k}\sqrt{\frac{\pi(t)}{\pi(v)}}. To bound \lambda_{\pi}(M_{G}) , observe that M_{G}(u,u)\geq 1/2 for every u because the number of self loops at u is at least \mathrm{deg}(u)/2 . So, by Lemma A.4 and Equation 16 , we have \lambda_{\pi}(M_{G})\leq 1-h_{\pi}(M_{G})^{2}/2=1-\Phi(G)^{2}/2\leq 1-\phi^{2}/2. Now, we conclude that \left|p-\frac{\mathrm{deg}_{G}(t)}{\mathrm{vol}_{G}(V)}\right|\leq(1-\phi^{2}/2)^{k}\sqrt{\frac{\mathrm{deg}_{G}(t)}{\mathrm{deg}_{G}(v)}}. ∎ Appendix B Proof of Lemma 3.1 We will use the following tools. Theorem B.1 ( [ Ass24 ] ) . For graph G=(V,E) with maximum degree \Delta define V_{\Delta}=\{v\in V\mid\mathrm{deg}_{G}(v)=\Delta\} . Given both adjacency matrix and list query access to G there exists a randomized algorithm which returns matching M\in E such that, for each v\in V , it holds that \Pr[v\notin M(V)]\leq 2/\Delta (not independently) in expected running time O(n\log n) . A k -edge-coloring of graph G is a partitioning of the edges G into k different matchings. Theorem B.2 ( [ EK24 ] ) . There exists a deterministic algorithm which for graph G with maximum degree \Delta and small constant \epsilon>0 returns a \Delta(1+\epsilon) -edge-coloring of G in time O(m\log(n)/\epsilon) . Now, we are ready to prove Lemma 3.1 . Proof. Randomized Algorithm: The randomized algorithm first generates an extended graph G^{\prime}=(V^{\prime},E^{\prime}) such that V^{\prime}\supseteq V,E^{\prime}\subseteq E and \mathrm{deg}_{G^{\prime}}(v)=\Delta for all v\in V_{\kappa} . To obtain such a graph from G it introduces n\kappa dummy vertices V_{D} and let V^{\prime}=V_{D}\cup V . Set E_{D}=\emptyset and for any vertex v\in V_{\kappa} inserts \Delta-\mathrm{deg}_{G}(v)\leq\Delta\kappa edges between v and V_{D} into E_{D} such that the maximum degree of V_{D} in E_{D} is \Delta . This can be done in a round-robin fashion deterministically. Finally, define E^{\prime}=E\cup E_{D} . Note, that generating G^{\prime} takes O(|V_{D}|+|E_{D}|)=O(n\Delta\kappa) time and its easy to see that given adjacency matrix and list query access to G we have adjacency matrix and list query access to G^{\prime} . Note that when the algorithm of Theorem B.1 is called on G^{\prime} in O(|V^{\prime}|\log|V^{\prime}|)=O(n\log n) expected time it returns a matching M such that every vertex in V_{\kappa} is not matched by M^{\prime} with probability at most 2/\Delta . Therefore, the expected number of unmatched vertices in V_{\kappa} under M is at most 2|V_{\kappa}|/\Delta\leq 2n/\Delta\leq n\kappa/2 . Define a matching M returned by the algorithm to be suitable if it doesn’t match at most n\kappa vertices of V_{\kappa} . By Markov’s inequality we can argue that the algorithm of Theorem B.1 returns a suitable matching with constant probability. Furthermore, since its running time is O(n\log n) in expectation it runs in O(n\log n) time with constant probability. Hence, through O(\log n) calls to the algorithm and stopping early if the running time exceeds O(n\log n) we can find a suitable matching M_{S} with high probability in time O(n\log^{2}n) . The algorithm finally returns M_{F}=M_{S}\cap E To bound the number of unmatched vertices of V_{\kappa} under M_{F} observe that there are two ways a vertex in V_{\kappa} may be unmatched by M_{F} : either it is not matched by M_{S} or it is matched to a vertex in V_{D} through an edge not in E . Both cases may only hold for \kappa n vertices each since M_{S} is a suitable matching and |V_{D}|\leq n\kappa . Hence, M_{F} matched all but 2\kappa n vertices of V_{\kappa} . Deterministic Algorithm: To obtain our deterministic algorithm we find a \Delta(1+\kappa) -edge-coloring of G using the algorithm of Elkin and Khuzman [ EK24 ] in O(m\frac{\log n}{\kappa}) time. The algorithm partitions the edges of the graph into \Delta(1+\kappa) matchings (or colors). Every vertex in v\in V_{\kappa} has degree at least \Delta(1-\kappa) in G , hence it is matched by at least \Delta(1-\kappa)/\Delta(1+\kappa)\geq 1-2\kappa fraction of colors. Therefore, in expectation a uniformly selected color matches at least |V_{\kappa}|\cdot(1-2\kappa) vertices of V_{\kappa} , that is it doesn’t match at most 2|V_{\kappa}|\kappa\leq 2n\kappa vertices. Hence, by the pigeonhole principle there must exist a color which doesn’t match less then 2\kappa n vertices of V_{\kappa} . We may find this color in O(m) time by simply counting the edges incident on V_{\kappa} in all colors. ∎