Fully Dynamic Approximate Maximum Matching and Minimum
Vertex Cover in O(log3 n) Worst Case Update Time∗

arXiv:1704.02844v1 [] 10 Apr 2017

Sayan Bhattacharya†

Monika Henzinger‡

Danupon Nanongkai§

Abstract
We consider the problem of maintaining an approximately maximum (fractional) matching and an
approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper by Onak and
Rubinfeld [STOC 2010], this problem has received significant attention in recent years. There remains,
however, a polynomial gap between the best known worst case update time and the best known amortised
update time for this problem, even after allowing for randomisation. Specifically, Bernstein and Stein
[ICALP 2015, SODA 2016] have the best known worst case update time. They present a deterministic
data structure with approximation ratio (3/2 + ε) and worst case update time O(m1/4 /ε 2 ), where m is
the number of edges in the graph. In recent past, Gupta and Peng [FOCS√2013] gave a deterministic data
structure with approximation ratio (1+ε) and worst case update time O( m/ε 2 ). No known randomised
data structure beats the worst case update times of these two results. In contrast, the paper by Onak and
Rubinfeld [STOC 2010] gave a randomised data structure with approximation ratio O(1) and amortised
update time O(log2 n), where n is the number of nodes in the graph. This was later improved by Baswana,
Gupta and Sen [FOCS 2011] and Solomon [FOCS 2016], leading to a randomised date structure with
approximation ratio 2 and amortised update time O(1).
We bridge the polynomial gap between the worst case and amortised update times for this problem,
without using any randomisation. We present a deterministic data structure with approximation ratio
(2 + ε) and worst case update time O(log3 n), for all sufficiently small constants ε.

∗ An

extended abstract of this paper appeared in SODA 2017.
of Warwick, UK. Email: s.bhattacharya@warwick.ac.uk
‡ University of Vienna, Austria. Email: monika.henzinger@univie.ac.at. The research leading to these results has
received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/20072013) / ERC Grant Agreement no. 340506.
§ KTH Royal Institute of Technology, Sweden. Email: danupon@gmail.com. Supported by Swedish Research Council grant
2015-04659 “Algorithms and Complexity for Dynamic Graph Problems”.
† University

i

1

Introduction

A matching in a graph is a set of edges that do not share any common endpoint. In the dynamic matching
problem, we want to maintain an (approximately) maximum-cardinality matching when the input graph is
undergoing edge insertions and deletions. The time taken to handle an edge insertion or deletion in the input
graph is called the update time of the concerned dynamic algorithm. Our goal is this paper is to design a
dynamic algorithm whose update time is as small as possible. Throughout this paper, we denote the number
of nodes and edges in the input graph by n and m respectively. The value of n remains fixed over time,
since the set of nodes in the graph remains the same. However, the value of m changes as edges get inserted
or deleted in the graph. Similar to static problems where we want the running time of an algorithm to be
polynomial in the input size, in the dynamic setting we desire the update time to be polylog(n), for an input
(edge insertion or deletion) to a dynamic problem can be specified using O(log n) bits.
The dynamic matching problem has been extensively studied in the past few years. We now know that
within polylog(n) update time we can maintain a 2-approximate matching using a randomized algorithm
[2, 20, 22] and a (2 + ε)-approximate matching using a deterministic algorithm [5–7]. The downside of
these algorithms, however, is that their update times are amortised. Thus, the algorithms take polylog(n)
update time on average, but from time to time they may take as large as O(n) time to respond to a single
update. It is much more desirable to be able to guarantee a small update time after every update. This type
of update time is called worst-case update time.
Unfortunately, known worst-case update time bounds for this problem are polynomial in n: the known algorithms take O(n1.495 ) worst-case update time to maintain the value of the maximum matching exactly [21]
√
(also see [1, 14, 18] for complementing lower bounds), O( m/ε 2 ) time to maintain a (1 + ε)-approximate
maximum matching [11, 19], O(m1/3 /ε 2 ) time to maintain a (4 + ε)-approximate maximum matching [6],
and O(m1/4 /ε 2 ) time to maintain a (3/2 + ε)-approximate maximum matching in bipartite graphs [3, 4].
There is no algorithm with polylog(n) worst-case update time even with a polylog(n) approximation ratio.
We note that the lack of a data structure with good worst-case update time is not at all specific to the problem of dynamic matching. Other fundamental dynamic graph problems, such as spanning tree, minimum
spanning tree and shortest paths also suffer the same issue (see, e.g., [8–10, 13, 15, 23, 24]). One exception
is the celebrated randomized algorithm with polylog(n) update time for dynamic connectivity [16]. To the
best of our knowledge, our result is the first deterministic fully-dynamic graph algorithm with polylog(n)
worst-case update time in general graphs. In contrast, for a special class of graphs with arboricity bounded
by α (say), the papers [12, 17] present deterministic dynamic algorithms with Õ(α) worst case update times
for the problem of maintaining edge orientation.
Our result. We present a deterministic algorithm that maintains a fractional matching1 and a vertex cover2
whose sizes are within a (2 + ε) factor of each other, for all sufficiently small constants ε. Since the size of
a maximum fractional matching is at most 3/2 times the size of a maximum matching, we can also maintain
a (3 + ε)-approximation to the size of the maximum matching in O(log3 n) worst-case update time.

2

A high level overview of our algorithm

In this section, we present the main ideas behind our algorithm. The formal description of the algorithm and
the analysis appears in subsequent sections.
Hierarchical Partition. Our algorithm builds on the ideas from a dynamic data structure of Bhattacharya,
Henzinger and Italiano [6] called (α, β )-decomposition. This data structure maintains a (2+ε)-approximate
maximum fractional matching in O(log n/ε 2 ) amortised update time. It defines the fractional edge weights
using levels of nodes and edges. In particular, fix two constants α, β ≥ 1, and recall that the input graph
1 In a fractional matching each edge is assigned a nonzero weight, ensuring that for every node the sum of the weights of the
edges incident to it is at most 1. The size of a fractional matching is the sum of the weights of all the edges in the graph.
2 A vertex cover is a set of nodes such that every edge in the graph has at least one endpoint in that set.

1

G = (V, E) has |V | = n nodes. Partition the node set V into L + 1 levels {0, . . . , L}, where L = logβ n. Let
`(y) ∈ {0, . . . , L} denote the level of a node y ∈ V . The level of an edge (x, y) is given by Eq. (1), and we
assign a fractional weight w(x, y) as per Eq. (2).
`(x, y) = max(`(x), `(y))
w(x, y) = β

−`(x,y)

(1)
(2)

Thus, the weight of an edge decreases exponentially with its level. The weight of a node y ∈ V is defined as
Wy = ∑(x,y)∈E w(x, y). This equals the sum of the weights of the edges incident on it. The goal is to maintain
a partition satisfying the following property.
Property 2.1. Every node y with `(y) > 0 has weight 1/(αβ ) ≤ Wy < 1. Furthermore, every node y with
`(y) = 0 has weight 0 ≤ Wy < 1.
To provide some intuition, we show how to construct a hierarchical partition satisfying Property 2.1 in
the static setting, when there is no edge insertions/deletions. For notational convenience, we define VL∗ = V .
Initially, we put all the nodes in level L, and as per equations 1, 2 we assign a weight w(x, y) = β −L = 1/n
to every edge (x, y) ∈ E. Since every node has degree at most n − 1, we get 0 ≤ Wy < 1 for all y ∈ VL∗ . We
now execute a F OR loop as follows.
• F OR i = L to 1:
∗ = {y ∈
– We partition the node-set Vi∗ into two subsets: Vi = {y ∈ V : 1/β ≤ Wy < 1} and Vi−1
∗
V : 0 ≤ Wy < 1/β }. Next, we move down the nodes in Vi−1 to level i − 1. The level and weight
∗ = V ∪ . . . ∪ V remain unchanged during this step,
of every edge incident on a node in V \ Vi−1
i
L
∗ are moved down to level i − 1, we
as per equations 1 and 2. Hence, just after the nodes in Vi−1
get 1/β ≤ Wy < 1 for all nodes y at level i. The weights of the remaining edges (whose both
∗ ) increase by a factor of β . Hence, the weights of the nodes in V ∗ also
endpoints lie in Vi−1
i−1
∗ were moved down to level i − 1, we
increase by at most a factor of β . Before the nodes in Vi−1
∗ . Thus, just after the nodes in V ∗ are moved down to level
had 0 ≤ Wy < 1/β for all y ∈ Vi−1
i−1
∗ .
i − 1, we get 0 ≤ Wy < 1 for all y ∈ Vi−1

When the above F OR loop terminates, we have 1/β ≤ Wy < 1 for all nodes y ∈ V at levels `(y) > 0, and
0 ≤ Wy < 1 for all nodes y ∈ V at level `(y) = 0. Specifically, Property 2.1 is satisfied with α = 1.

Theorem 2.2 ([6]). Under Property 2.1, the edge-weights {w(e)} form a 2αβ -approximate maximum fractional matching in G.
In [6], Bhattacharya et al. showed that we can dynamically maintain such a partition with α = β =
(1 + ε) in O(log n/ε 2 ) amortised update time. The main idea is as follows. Assume that we have a partition
that satisfies Property 2.1. Now an edge (u, v) is inserted or deleted. This causes Wu and Wv to increase or
decrease. Hence, it might happen that some node x ∈ {u, v} violates Property 2.1 after the insertion/deletion
of the edge (u, v), i.e. either (1) Wx ≥ 1 or (2) Wx < 1/(αβ ) and `(x) > 0. We call such a node x dirty, and
deal with this event by changing the level of x in a straightforward way as per Figure 1: If Wx is too large
(resp. too small), then we increase (resp. decrease) `(x) by one. This causes the weights of some edges
incident on x to decrease (resp. increase), which in turn decreases (resp. increases) the value of Wx . For each
level i ∈ [0, L], we define the set of edges Ei (x) as follows.
Ei (x) = {(x, y) ∈ E | `(x, y) = i}.

(3)

An important observation is that as a node x moves up (resp. down) from level i to level i + 1 (resp. i − 1),
the edges whose weights get changed all belong to the set Ei (x). Since the relevant data structures can
be maintained efficiently, this implies that the runtime of one iteration of the W HILE loop in Figure 1 is
2

dominated by the cost of Line 7, which takes O(|Ei (x)|) time. In [6], the authors showed that this cost can
be amortised over previous edge insertions/deletions.
Note that one iteration of the W HILE loop can make some neighbours of x dirty, and x itself might
remain dirty at the end of the iteration. These dirty nodes are dealt with in subsequent iterations in a similar
way (until there is no dirty node left).
01. W HILE there is a dirty node x
02.
Let i = `(x)
03.
I F Wx ≥ 1, T HEN // In this case i < L
04.
Set `(x) ← `(x) + 1.
05.
E LSE // In this case Wx < 1/(αβ ), i > 0
06.
Set `(x) ← `(x) − 1.
07.
Update `(x, y) for all (x, y) ∈ Ei (x).
Figure 1: Fixing the dirty nodes.
Example: Inserting edges to a star. The following example shows the basic idea behind the amortisation
argument. Consider a star centred at node v consisting of β i−1 edges, for some large i. To satisfy Property 2.1, we can set `(v) = i, while all other nodes have level 0. Thus, we get Wv = 1/β since every edge
has weight 1/β i . Now keep inserting edges to the star (the graph remains a star throughout). Property 2.1
remains satisfied until the (β i − β i−1 )-th edge is inserted – at this point the star consists of β i edges, Wv = 1,
and the node v becomes dirty. We fix the node by increasing `(v) to i + 1 as in Algorithm 1, thus reducing the
edge-weights to 1/β i+1 and the value of Wv to 1/β . To do this we have to pay the cost of O(|Ei (v)|) = O(β i )
in terms of update time. We can amortise this cost over the (β i − β i−1 ) newly inserted edges. This gives an
amortised update time of O(1) for constant β .
Note that in the above example the algorithm does not perform well in the worst case: after the (β i −
β i−1 )-th insertion it has to “probe” all edges in Ei (v). So the worst case update time becomes O(β i ), which
can be polynomial in n when i is large. But in this particular instance the problem can be fixed easily:
Whenever v becomes dirty due to the insertion of an edge with weight 1/β i , we reduce the weight of the
newly inserted edge and some other edge in the star from 1/β i to 1/β i+1 . Thus, the net increase in the
weight of v becomes equal to 1/β i − 2(1/β i − 1/β i+1 ) = 2/β i+1 − 1/β i ≤ 0 (the last inequality holds as
long as β ≥ 2). In other words, when the node v becomes dirty, by reducing the weights of two edges to
1/β i+1 we can ensure that Wv again becomes smaller than one. Once every edge has weight 1/β i+1 , we set
`(v) = i + 1.
Shadow-level (`y (x, y)). To make the above idea concrete, we introduce the notion of a shadow-level. For
every node y ∈ V and every incident edge (x, y) ∈ E, we define the shadow-level of y with respect to (x, y),
denoted by `y (x, y) ∈ {0, . . . , L}, to be an integer in {0, . . . , L} such that the following property holds.
Property 2.3. For every node y and edge (x, y), `(y) − 1 ≤ `y (x, y) ≤ `(y) + 1.
We modify the definition of the level of an edge (x, y) ∈ E (in Eq. (1)) to
`(x, y) = max(`x (x, y), `y (x, y)).

(4)

This affects the value of w(x, y) and the set Ei (y) as they depend on the levels of edges (see Eq. (2) and
(3)). The idea of the shadow-level is that if `y (x, y) > `(y) (respectively `y (x, y) < `(y)), then from the
perspective of the edge (x, y) we have already increased (resp. decreased) `(y); thus, the level and weight
of (x, y) has changed accordingly. In this case, we say that y up-marks (respectively down-marks) the edge
3

x11

j=

i

/↵
2

uk

xk1
······

k=

i 1

x1j

·········

v

······

u1

xkj

Figure 2: Example. Suppose that i is very large, e.g. i = (log n)/2, and β is a large constant.
(x, y). We will use this operation when Wy is too large (resp. too small). Intuitively, y should not upmark and down-mark edges at the same time. In particular, let Mdown (y) = {(x, y) ∈ E : `y (x, y) = `(y) − 1}
and Mup (y) = {(x, y) ∈ E : `y (x, y) = `(y) + 1} respectively denote the set of all edges down-marked and
up-marked by y. Then, we will maintain the following property.
Property 2.4. Either Mup (y) = 0/ or Mdown (y) = 0.
/
To see the usefulness of this new definition, consider the following algorithm for dealing with the case
where the graph is always a star centred at v: If there are only edge insertions, then v up-marks the newly
inserted edge and another edge in E`(v) (v) whenever it becomes dirty (i.e. Wv ≥ 1). It is easy to see that this
will be enough to keep Wv < 1 as long as β ≥ 2. Once E`(v) (v) = 0,
/ we increase `(v) by one. Similarly,
if there are only edge deletions, then v can down-mark an edge in E`(v) (v) whenever it becomes dirty (i.e.
Wv < 1/(αβ )).
The algorithm follows the same strategy when there are both edge insertions and deletions, albeit with
one caveat: To ensure that Property 2.4 holds, it cannot up-mark an edge if Mdown (v) 6= 0,
/ and cannot downmark an edge if Mup (v) 6= 0.
/ Suppose that Mdown (v) 6= 0/ and we want to reduce the weight of v. In this event,
the node v picks an edge (u, v) in Mdown (v) and sets `v (u, v) back from `(v) − 1 to `(v), which reduces the
value of w(u, v). This causes the edge (u, v) to be removed from Mdown (v) and be added to E`(v) (v). We say
that the node v un-marks the edge (u, v). Next, suppose that Mup (v) 6= 0/ and we want to increase the weight
of v. In this event, the node v un-marks an edge in Mup (v).
Failures. So far we have described an idea that leads to small worst-case update time when the input
instance is a star graph. To make this idea work on a general input instance, we have to deal with several
issues that make the algorithm more complicated. The chief one among them is the observation that the
algorithm may fail in adjusting edge weights. Consider, for example, a tree rooted at a node v having
k = β i−1 /α children, say u1 , . . . uk . Further, each ui has j = β i − 2 children. See Fig. 2. Suppose that we
satisfy Property 2.1 by setting `(x p,q ) ← 0 for every leaf-node x p,q with p ∈ [k] and q ∈ [ j], `(u p ) ← i for
every internal node u p with p ∈ [k], and `(v) ← i for the root node v. No edge is down-marked or up-marked
by any node. This implies that Wv = 1/(αβ ), Wu p = 1 − 1/β i for all p ∈ [k], and Wx p,q = 1/β i for all p ∈ [k]
and q ∈ [ j].
Now, suppose that the edge (v, u1 ) gets deleted. This makes v dirty, for Wv becomes smaller than 1/(αβ ).
The algorithm responds by down-marking an edge in Ei (v), say (v, u2 ). Unfortunately, this down-marking
4

does not change the weight w(u, v2 ) since `v2 (u, v2 ) = i. I We say that this down-marking fails. When a
down-marking fails, the node v remains dirty and Property 2.1 remains unsatisfied. In fact, in this example,
the node v will remain dirty even if we down-mark all the edges in Ei (v). To satisfy Property 2.1, we have
no other option but to set `(v) ← 0. However, we cannot do so unless we probe all the edges in Ei (v), for
we have to ensure that all the down-markings on these edges fail. This takes too much time.
To deal with this issue, we keep down-marking the edges in Ei (v) as long as we fail, until the point
when we experience polylog(n) failures. We might still end up having Wv < 1/(αβ ). Nevertheless, we will
guarantee a constant approximation ratio by arguing that we continue to have Wv = Ω(1/(αβ )). Intuitively,
every time Wv decreases by 1/β i because of these failures, we down-mark many edges in the set Ei (v). Since
|Ei (v)| ≤ β i−1 /α, we are able to down-mark all the edges in Ei (v) before the value of Wv becomes too small.
At that point, we are ready to decrease the level of v.
Specifically, suppose that the edges incident to v keep getting deleted. While handling t = β i−1 /(α log2 n)
such deletions, we perform t · polylog(n) ≥ β i−1 /α failed down-markings. This is enough to down-mark
every edge in Ei (v). At this point we move v down to level (i − 1), and we still have Wv ≥ 1/(αβ ) − t/β i =
(1 − 1/ log2 n)/(αβ ). By repeating this argument, we conclude that even if there are more deletions, we still
have Wv = Ω(1/(αβ )) until the point in time when v moves down to level 0 (where v can not be dirty for its
weight being small).
The algorithm in a nutshell. Our algorithm obeys the following principles. When a node y becomes
dirty, it either (1) up-marks or down-marks an edge (x, y), or (2) un-marks an edge (x, y) if up-marking or
down-marking would violate Property 2.4. Such an action may fail, meaning that w(x, y) might not change,
for reasons exemplified in Fig. 2. In this event, y continues probing its other incident edges, and stops when
it experiences either its first success or its polylog(n)th failure. We show: (a) the failures do not cause the
weight Wy to become too small or too large, (b) fixing one dirty node leads to at most one new dirty node,
and (c) the level of the dirty node under consideration drops after constantly many fixes. Item (a) guarantees
a constant approximation factor. Items (b), (c) guarantee a polylog(n) update time, for there are O(log n)
levels.

3

Preliminaries

Henceforth, we focus on formally describing our dynamic algorithm and analysing its worst-case update
time. For the rest of the paper, we fix two constants β , K and define L and f (β ) as in equation 5. Note that
K < L when n is sufficiently large.
β ≥ 5, K = 20, f (β ) = 1 − 3/β , L = dlogβ ne.

(5)

We will maintain a hierarchical partition of the node-set in G = (V, E), and a fractional matching where
the weights assigned to the edges depend on the levels of their endpoints. For technical reasons, however,
there will be two key differences between the hierarchical partition actually used by our dynamic algorithm
and the one that was defined in Section 2.
1. We will collapse all the nodes in levels {0, . . . , K} into a single level K. Accordingly, the level of a
node will lie in the range [K, L] in this new hierarchical partition. The weights of the nodes y in levels
`(y) > K will satisfy the constraint: f (β ) ≤ Wy < 1. On the other hand, the weights of the nodes y at
the lowest level `(y) = K will satisfy the constraint: 0 ≤ Wy < 1. Comparing these constraints with
Property 2.1, it follows that the term 1/(αβ ) is replaced by f (β ) in the new partition.
2. We will allow the weight of an edge (u, v) to be off by a factor of β from its ideal value β − max(`(u),`(v)) .
The structure maintained by our algorithm will be called a nice-partition. This is formally defined below.
Definition 3.1. In a nice-partition, the node-set V is partitioned into (L − K + 1) subsets VK , . . . ,VL . For
i ∈ [K, L], if a node v belongs to Vi , then we say that the node v is at level `(v) = i. Each edge (u, v) ∈ E gets
5

a weight w(u, v). Let Wv = ∑(u,v)∈E w(u, v) be the total weight received by a node v from its incident edges.
The following properties hold.
1. For every edge (u, v) ∈ E, we have β − max(`(u),`(v))−1 ≤ w(u, v) ≤ β − max(`(u),`(v))+1 .
2. If a node v has `(v) > K, then f (β ) ≤ Wv < 1.
3. If a node v has `(v) = K, then Wv < 1.
Lemma 3.2. Suppose that we can maintain a nice-partition in O(T (n)) worst-case update time. Then we can
also maintain a 2/ f (β )-approximate maximum fractional matching and a 2/ f (β )-approximate minimum
vertex cover in O(T (n)) worst case update time.
Proof. Let E r = {(u, v) ∈ E : `(u) = `(v) = K} be the subset of edges with both endpoints at level K. We
will maintain a residual weight wr (e) ≥ 0 for every edge e ∈ E r . For notational consistency, we define
wr (e) = 0 for every edge e ∈ E \ E r . Let Wvr = ∑(u,v)∈E r wr (u, v) denote the residual weight received by a
node v from all its incident edges. Two conditions are satisfied:
• (a) For each node v ∈ V , we have 0 ≤ Wv +Wvr ≤ 1.
• (b) For every edge (u, v) ∈ E r , we have either Wv +Wvr ≥ 1 − 1/β or Wu +Wur ≥ 1 − 1/β .

Let degr (v) denote the degree of a node v ∈ V among the edges in E r . By condition (1) of Definition 3.1,
every edge (x, y) ∈ E r has weight w(x, y) ≥ β −K−1 . Hence, for every node v ∈ V , we get: 1 > Wv ≥
∑(u,v)∈E r w(u, v) ≥ degr (v) · β −K−1 . This implies that degr (v) < β K+1 for every node v ∈ V . Since β , K are
constants, we get: degr (v) = O(1) for every node v ∈ V .

Maintaining the residual weights {wr (e)}, e ∈ E r .
For every node v ∈ V , let b(v) = 1 − Wv denote the capacity of the node. Let br (v) be equal to the value
of b(v) rounded down to the nearest multiple of 1/β . We say that br (v) is the residual capacity of node
v. We create an auxiliary graph G∗ = (V ∗ , E ∗ ), where we have β copies of each node v ∈ V . For every
edge (u, v) ∈ E r , there are β 2 edges in G∗ : one for each pair of copies of u and v. For each node v ∈ V , if
br (v) = t/β for some integer t ∈ [0, β ], then t copies of v are turned on in G∗ , and the remaining (β − t)
copies of v are turned off in G∗ . We maintain a maximal matching M ∗ in the subgraph of G∗ induced by
the copies of nodes that are turned on. Since degr (v) = O(1) for every node v ∈ V , we can maintain the
matching M ∗ in O(1) update time using a trivial algorithm. From the matching M ∗ , we get back the residual
weights {wr (e)} as follows. For every edge (u, v) ∈ E r , if there are t edges in M ∗ between different copies
of u and v, then we set wr (u, v) ← t/β . It is easy to check that this satisfies both conditions (a) and (b).
Approximation guarantee.
Condition (a) implies that the edge-weights {w(e) + wr (e)} form a valid fractional matching in G. Define
the subset of nodes V ∗ = {v ∈ V : Wv +Wvr ≥ f (β )}. Consider any edge (u, v) ∈ E. If at least one endpoint
x ∈ {u, v} lies at a level `(x) > K, then condition (2) of Definition 3.1 implies that Wx + Wxr ≥ Wx ≥ f (β ),
and hence x ∈ V ∗ . On the other hand, if both the endpoints {u, v} lie at level K, then by conditions (a)
and (b) we have: Wx + Wxr ≥ 1 − 1/β ≥ f (β ) for some x ∈ {u, v}, and hence x ∈ V ∗ . It follows that V ∗
forms a valid vertex cover in G. Applying complementary slackness conditions, we infer that the edgeweights {w(e) + wr (e)} form a 2/ f (β )-approximate maximum fractional matching in G, and that V ∗ forms
a 2/ f (β )-approximate minimum vertex cover in G.

Fix any constant 0 < ε < 1 and let β = 3(2 + ε)/ε. Then β ≥ 5 and 2/ f (β ) = 2 + ε (see equation 5).
Setting β in this way, we can use Theorem 3.3 and Lemma 3.2 to maintain a (2 + ε)-approximate maximum
fractional matching and a (2 + ε)-approximate minimum vertex cover in O(log3 n) worst-case update time.
We devote the rest of the paper to proving Theorem 3.3.
Theorem 3.3. We can maintain a nice-partition in G = (V, E) in O(log3 n) worst case update time.

6

3.1

Shadow-levels.

As in Section 2, the shadow-levels will uniquely determine the weight w(u, v) assigned to every edge (u, v) ∈
E. They will ensure that w(u, v) differs from the ideal value β − max(`(u),`(v)) by at most a factor of β . This
implies condition (1) of Definition 3.1. Specifically, we require that each edge has two shadow-levels: one
for each of its endpoints. Let `y (x, y) ∈ [K, L] be the shadow-level of a node y with respect to the edge (x, y).
We require that this shadow-level can differ from the actual level of the node by at most one. This is formally
stated in the invariant below.
Invariant 3.4. For every node y ∈ V and every edge (x, y) ∈ E, we have `(y) − 1 ≤ `y (x, y) ≤ `(y) + 1.
Next, as in Section 2, we define the level of an edge to be the maximum value among the shadow-levels
of its endpoints. Let `(x, y) ∈ [K, L] be the level of an edge (x, y). Then for every edge (x, y) ∈ E we have:
`(x, y) = max(`x (x, y), `y (x, y)).

(6)

As in Section 2, we now require that the weight assigned to an edge (u, v) ∈ E be given by β −`(u,v) .
w(x, y) = β −`(x,y) for every edge (u, v) ∈ E.

(7)

Thus, the weight of an edge decreases exponentially with its level. It is easy to check that if Invariant 3.4
holds, then assigning the weights to the edges in this manner satisfies condition (1) of Definition 3.1.
Corollary 3.5. Suppose that Invariant 3.4 holds and edges are assigned weights as in equations 6, 7. Then
for every edge (x, y) ∈ E we have:
β − max(`(x),`(y))−1 ≤ w(x, y) ≤ β − max(`(x),`(y))+1 .
Proof. Since each shadow-level differs from the actual level by at most one (see Invariant 3.4), the maximum
value among the shadow-levels also differs from the maximum value among the actual levels by at most
one. Specifically, we get: max(`(x), `(y)) − 1 ≤ `(x, y) = max(`x (x, y), `y (x, y)) ≤ max(`(x), `(y)) + 1. The
corollary now follows from the fact that the weight of an edge (x, y) ∈ E is given by w(x, y) = β −`(x,y) .
As in Section 2, we now define the concept of an edge marked by a node. Consider any edge (x, y) ∈ E
incident to a node y ∈ V . If `y (x, y) = `(y) + 1, then we say that the edge (x, y) has been up-marked by the
node y. Similarly, if `y (x, y) = `(y) − 1, then we say that the edge (x, y) has been down-marked by the node
y. And if `y (x, y) = `(y), then we say that the edge (x, y) is un-marked by the node y. We let Mup (y) and
Mdown (y) respectively be the set of all edges (x, y) ∈ E incident to y that have been up-marked and downmarked by y. For every i ∈ [K, L], we let Ei (y) be the set of all edges (x, y) ∈ E incident to y that are at level
`(x, y) = i.
Mup (y) = {(x, y) ∈ E : `y (x, y) = `(y) + 1}

Mdown (y) = {(x, y) ∈ E : `y (x, y) = `(y) − 1}
Ei (y) = {(x, y) ∈ E : `(x, y) = i}

3.2

(8)
(9)
(10)

Different states of a node.

Our goal is to maintain a nice-partition in G. In Section 3.1, we defined the concept of shadow-levels so as to
ensure that the edge-weights satisfy condition (1) of Definition 3.1. In this section, we present a framework
which will ensure that the node-weights satisfy the remaining conditions (2), (3) of Definition 3.1. Towards
this end, we first need to define the concept of an activation of a node.

7

Activations of a node. The deletion of an edge (x, y) in G leads to a decrease in the values of Wx and
Wy . In contrast, when an edge (x, y) is inserted in G, we assign values to its two shadow-levels `x (x, y)
and `y (x, y) in such a way that Invariant 3.4 holds, and then assign a weight to the edge as per equation 7.
This leads to an increase in the values of Wx and Wy . These two events are called natural activations of
the endpoints x, y. In other words, a node is naturally activated whenever an edge incident to it is either
inserted into or deleted from G. The weight of a node changes whenever it encounters a natural activation.
Hence, such an event might lead to a scenario where the node-weight becomes either too large or too small,
thereby violating either condition (2) or condition (3) of Definition 3.1. For example, consider a node y at
a level `(y) > K whose current weight is just slightly smaller than one. Thus, we have: 1 − δ ≤ Wy < 1 for
some small δ . Now, suppose that y gets naturally activated due to the insertion of an edge (x, y). Further,
suppose that this leads to the value of Wy becoming larger than one after the natural activation. So the node
y violates condition (2) of Definition 3.1. In our algorithm, at this stage the node y will select some edge
(x0 , y) ∈ E`(y) (y) and up-mark that edge. Specifically, the node will set `y (x0 , y) ← `(y) + 1, insert the edge
(x0 , y) into the sets Mup (y) and E`(y)+1 (y), and remove the edge from the set E`(y) (y). The new level of
the edge will be given by `(x0 , y) = `(y) + 1. This will reduce the node-weight Wy by β −`(y) − β −(`(y)+1) ,
and (hopefully) the new value of Wy will again be smaller than one. The up-marking of the edge (x0 , y),
however, will change the weight of the other endpoint x0 . We call such an event an induced activation of
x0 . Specifically, an induced activation of a node x0 refers to the event when the node-weight Wx0 increases
(resp. decreases) because the other endpoint y of an incident edge (x0 , y) has decreased (resp. increased) its
shadow-level `y (x0 , y).
In general, consider an activation of a node y that increases its weight. Suppose that the node wants
to revert this change (weight increase) so as to ensure that conditions (2) and (3) of Definition 3.1 remain
satisfied. Then it either up-marks some edges from E`(y) (y) or un-marks some edges from Mdown (y). This,
in turn, might activate some of the neighbours of y.
Similarly, consider an activation of a node y that decreases its weight. Suppose that the node wants
to revert this change (weight decrease) so as to ensure that conditions (2) and (3) of Definition 3.1 remain
satisfied. Then it either down-marks some edges from E`(y) (y) or un-marks some edges from Mup (y). Again,
this might in turn activate some of the neighbours of y.
We require that a node cannot simultaneously have an up-marked and a down-marked edge incident on
it. This requirement is formally stated in Invariant 3.6. Intuitively, a node has up-marked incident edges
when it is trying to ensure that its weight does not become too large, and down-marked incident edges when
it is trying to ensure that its weight does not become too small. Thus, it makes sense to assume that a node
cannot simultaneously be in both these states.
Invariant 3.6. For every node y ∈ V , either Mup (y) = 0/ or Mdown (y) = 0.
/
Invariant 3.7 states that if a node y has up-marked or down-marked an incident edge (x, y), then the
shadow-level `x (x, y) of the other endpoint x is no more than the level of y. Intuitively, the node y up-marks
or down-marks an incident edge only if it wants to change its weight Wy without changing its own level
`(y). Suppose that the invariant is false, i.e., the node y has up-marked or down-marked an edge (x, y)
with `x (x, y) > `(y). Then we have `y (x, y) ≤ `(y) + 1 ≤ `x (x, y), where the first inequality follows from
Invariant 3.4. But, this implies that y can never change the weight w(x, y) by up-marking or down-marking
(x, y), for the value of w(x, y) is determined by the shadow-level of the other endpoint x. Thus, the node
y does not gain anything by up-marking or down-marking the edge (x, y). This is why we guarantee the
following invariant.
Invariant 3.7. For every edge (x, y) ∈ E, if `y (x, y) 6= `(y), then we must have `x (x, y) ≤ `(y).
Six different states. For technical reasons, we will require that a node is always in one of six possible
states. See Table 1. It is easy to check that this is sufficient to ensure conditions (2), (3) of Definition 3.1.
8

S TATE[y]

1. U P

Weight-range

Up-marked
edges

1 − β1 ≤ Wy < 1

Down-marked
edges

Other
constraints

Mdown (y) = 0/

E`(y) (y) 6= 0/

2. D OWN

f (β ) ≤ Wy < 1 − β2

Mup (y) = 0/

3. S LACK

0 ≤ Wy < f (β )

Mup (y) = 0/

Mdown (y) = 0/

4. I DLE

1 − β2 ≤ Wy < 1 − β1

Mup (y) = 0/

Mdown (y) = 0/

5. U P -B

1 − β2 ≤ Wy < 1 − β1

Mup (y) 6= 0/

Mdown (y) = 0/

6. D OWN -B

1 − β2 ≤ Wy < 1 − β1

Mup (y) = 0/

Mdown (y) 6= 0/

If `(y) > K, then
E`(y) (y) − Mdown (y) 6= 0/

Table 1: Constraints satisfied by a node in different states.

9

`(y) = K

See Lemma 3.8. One way to classify these states is as follows. Definition 3.1 requires that the weight of
a node y lies in the range 0 ≤ Wy < 1. We partition this range into four intervals: I1 , I2 , I3 and I4 . These
intervals are non-empty as long as β is a sufficiently large constant.
I1 = [0, f (β )) , I2 = [ f (β ), 1 − 2/β )

I3 = [1 − 2/β , 1 − 1/β ) and I4 = [1 − 1/β , 1) .
A node y is in U P state when Wy ∈ I4 , D OWN state when Wy ∈ I2 , and S LACK state when Wy ∈ I1 . As
per Table 1, the node y has to satisfy some additional constraints when S TATE[y] ∈ {U P, D OWN, S LACK}.
Finally, if Wy ∈ I3 , then y is in one of three possible states – I DLE, U P -B, D OWN -B – depending on whether
or not it has up-marked or down-marked any incident edge. By Invariant 3.6, a node cannot simultaneously
up-mark some incident edges and down-mark some other incident edges. Hence, three cases can occur when
Wy ∈ I3 . (a) Mup (y) = Mdown (y) = 0.
/ In this case y is in I DLE state. (b) Mdown (y) = 0/ and Mup (y) 6= 0.
/ In
this case y is in U P -B state. (c) Mup (y) = 0/ and Mdown (y) 6= 0.
/ In this case y is in D OWN -B state.
The six states are precisely defined in Table 1.

Lemma 3.8. If a node y ∈ V is in one of the states described in Table 1, then its weight Wy satisfies conditions
(2) and (3) of Definition 3.1.
Proof. In every state, we have 0 ≤ Wy < 1 (see Table 1). We consider two mutually exclusive and exhaustive
cases. (a) f (β ) ≤ Wy < 1. (b) 0 ≤ W < f (β ). In case (a), clearly the node-weight Wy satisfies conditions
(2), (3) of Definition 3.1. In case (b), the node must be in S LACK state (see Table 1), and so we must have
`(y) = K. Thus, the node satisfies conditions (2), (3) of Definition 3.1 even in case (b).
Note that each of the intervals I1 , I2 , I3 and I4 defined above is of length at least 1/β (see equation 5). On
the other hand, for every edge (u, v) ∈ E we have w(u, v) ≤ 1/β K , for K is the minimum possible level in a
nice-partition. Accordingly, a natural or induced activation of a node can change its weight by at most 1/β K .
Note that 1/β K is much smaller than 1/β . This apparently simple observation has an important implication,
namely, that a node must be activated at least β K−1 times for its weight to cross the feasible range of any
interval in {I1 , I2 , I3 , I4 }. As a corollary, if a node y has, say, Wy ∈ I3 just before getting activated, then the
activation can only move Wy to a neighbouring interval – I2 or I4 . But it is not possible to have Wy ∈ I3 just
before the activation, and Wy ∈ I1 just after the activation. Throughout the rest of the paper, we will be using
this observation each time we consider the effect of an activation on a node. Next, we will briefly explain
the motivation behind considering all these different states.
1. S TATE[y] = U P. See row (1) in Table 1.
A node y is in U P state when 1 − 1/β ≤ Wy < 1. In this state the node’s weight is close to one. Hence,
whenever its weight increases further due to an activation the node tries to up-mark some incident edges
from E`(y) (y), in the hope that this would reduce the node’s weight and ensure that Wy never exceeds one.
The node y can up-mark an edge only if the set E`(y) (y) is nonempty. Hence, we require that E`(y) (y) 6= 0.
/
Further, to ensure that a up-marking does not violate Invariant 3.6, we require that Mdown (y) = 0.
/
2. S TATE[y] = D OWN. See row (2) in Table 1.
A node y is in D OWN state when f (β ) ≤ Wy < 1 − 2/β . In this state the node’s weight is close to the
threshold f (β ). There are two cases to consider here, depending on the current level of the node.
2-a. `(y) > K. In this case, whenever the value of Wy decreases further due to an activation, the node tries
to down-mark some incident edges from E`(y) (y) \ Mdown (y), in the hope that this would increase the node’s
weight and ensure that Wy does not drop below the threshold f (β ). The node y can down-mark an edge only
if the set E`(y) (y) \ Mdown (y) is nonempty. Hence, we require that E`(y) (y) \ Mdown (y) 6= 0.
/ Furthermore, in
order to ensure that a down-marking does not violate Invariant 3.6, we require that Mup (y) = 0.
/
10

2-b. `(y) = K. In this case, the node y cannot down-mark any incident edge (x, y), for we must always have
`y (x, y) ∈ [K, L]. Thus, we get Mdown (y) = 0/ in addition to the constraints specified in row (2) of Table 1. If
an activation makes Wy smaller than f (β ), then we simply set S TATE[y] ← S LACK.

We highlight one apparent discrepancy between the states U P and D OWN. If a node y is in D OWN state with
`(y) > K, then it tries to down-mark some edges from E`(y) (y) \ Mdown (y) after an activation that reduces its
weight. However, if the same node is in U P state, then it tries to up-mark some edges from E`(y) (y) after an
activation that increases its weight. This discrepancy is due to the fact that E`(y) (y) ∩ Mup (y) = 0,
/ as every
edge (x, y) ∈ Mup (y) has `(x, y) ≥ `y (x, y) = `(y) + 1. In other words, an edge up-marked by y can never
belong to the set E`(y) (y), and hence E`(y) (y) \ Mup (y) = E`(y) (y). In contrast, an edge (x, y) ∈ Mdown (y)
belongs to the set E`(y) (x, y) if `x (x, y) = `(y).
3. S TATE[y] = S LACK. See row (3) in Table 1.
A node y is in S LACK state when 0 ≤ Wy < f (β ). In order to ensure condition (2) of Definition 3.1, we
require that the node be at level K. Since K is the minimum possible level, there is no need for the node to
prepare for moving down to a lower level in future. Hence, we require that Mdown (y) = 0.
/ Further, the node’s
weight is currently so small that it will take quite some time before the node has to prepare for moving up
to a higher level. Hence, we require that Mup (y) = 0.
/
4. S TATE[y] = I DLE. See row (4) in Table 1.
A node y is in I DLE state when 1 − 2/β ≤ Wy < 1 − 1/β and Mup (y) = Mdown (y) = 0.
/ In this state the
node’s weight is neither too large nor too small, and the node does not have any up-marked or down-marked
incident edges. Intuitively, the node need not worry even if its weight changes due to an activation in this
state. In other words, when a node gets activated in I DLE state, it does not up-mark, down-mark or un-mark
any of its incident edges. After a sufficiently large number of activations when the node’s weight drops
below (resp. rises above) the threshold 1 − 2/β (resp. 1 − 1/β ), it switches to the state D OWN (resp. U P).

5. S TATE[y] = U P -B. See row (5) in Table 1. The term “U P -B” stands for “U P -BACKTRACK”.
A node y is in U P -B state when 1 − 2/β ≤ Wy < 1 − 1/β , Mup (y) 6= 0/ and Mdown (y) = 0.
/ Intuitively,
this state of the node captures the following scenario. Some time back the node y was in U P state with
1 − 1/β ≤ Wy < 1, Mup (y) 6= 0/ and Mdown (y) = 0.
/ From that point onward, the node encountered a large
number of activations that kept on reducing its weight. Eventually, the value of Wy became smaller than
1 − 1/β and the node entered the state U P -B. If the node keeps getting activated in this manner, then in near
future Wy will become smaller than 1 − 2/β and the node y will have to enter the state D OWN. At that time
we must have Mup (y) = 0.
/ In other words, the node y has to ensure that Mup (y) = 0/ before its weight drops
below the threshold 1 − 2/β . Thus, whenever S TATE[y] = U P -B and the node-weight Wy decreases due to
an activation, the node y un-marks some edges from Mup (y).
6. S TATE[y] = D OWN -B. See row (6) in Table 1. The term “D OWN -B” stands for “D OWN -BACKTRACK”.
A node y is in D OWN -B state when 1 − 2/β ≤ Wy < 1 − 1/β , Mdown (y) 6= 0/ and Mup (y) = 0.
/ Intuitively,
this state of the node captures the following scenario. Some time back the node y was in D OWN state with
f (β ) ≤ Wy < 1 − 2/β , Mdown (y) 6= 0/ and Mup (y) = 0.
/ From that point onward, the node encountered a large
number of activations that kept on increasing its weight. Eventually, the value of Wy became greater than
1 − 2/β and the node entered the state D OWN -B. If the node keeps getting activated in this manner, then in
near future Wy will become greater than 1 − 1/β and it will have to enter the state U P. At that time we must
have Mdown (y) = 0.
/ In other words, the node y has to ensure that Mdown (y) = 0/ before its weight increases
beyond the threshold 1 − 1/β . Thus, whenever S TATE[y] = D OWN -B and Wy increases due to an activation,
the node y un-marks some edges from Mdown (y).
3.3

Dirty nodes.

Our algorithm maintains a bit D[y] ∈ {0, 1} associated with each node y ∈ V . We say that the node y is
dirty if D[y] = 1 and clean otherwise. Intuitively, the node y is dirty when it is unsatisfied about its current
11

condition and it wants to up-mark, down-mark or un-mark some of its incident edges. Once a dirty node is
done with up-marking, down-marking or un-marking the relevant edges, it becomes clean again.
In our algorithm, a node becomes dirty only after it encounters a natural or induced activation. The
converse of this statement, however, is not true. There may be times when a node remains clean even after
getting activated, and this will be crucial in bounding the worst-case update time of our algorithm. Whether
or not a node will become dirty due to an activation depends on: (1) the state of the node, (2) the type of
the activation under consideration (whether it increases or decreases the node-weight), and (3) the node’s
current level. We have three rules that determine when a node becomes dirty.
Rule 3.9. A node y with S TATE[y] ∈ {U P, D OWN -B} becomes dirty after an activation that increases its
weight. In contrast, such a node does not become dirty after an activation that decreases its weight.
Justification for Rule 3.9.
Case 1. S TATE[y] = U P. Here, we have 1 − 1/β ≤ Wy < 1 and Mdown (y) = 0.
/ If an activation increases the
value of Wy , then y needs to up-mark some edges from E`(y) (y), in the hope that Wy remains smaller than 1
(see the discussion in Section 3.2). Hence, the node becomes dirty. In contrast, if an activation reduces the
value of Wy , then y need not up-mark, down-mark or un-mark any of its incident edges. Due to this inaction,
if it so happens that 1 − 2/β ≤ Wy < 1 − 1/β after the activation, then the node simply switches to state
U P -B or I DLE depending on whether or not Mup (y) 6= 0.
/

Case 2. S TATE[y] = D OWN -B. Here, we have 1 − 2/β ≤ Wy < 1 − 1/β , Mdown (y) 6= 0/ and Mup (y) = 0.
/
Such a node must un-mark all its incident edges before its weight rises past the threshold 1 − 1/β (see
the discussion in Section 3.2). Hence, whenever its weight increases due to an activation and S TATE[y] =
D OWN -B, the node y becomes dirty and un-marks some edges from Mdown (y). In contrast, if an activation
reduces its weight, then the node y need not up-mark, down-mark or un-mark any of its incident edges. Due
to this inaction, if it so happens that f (β ) ≤ Wy < 1 − 2/β after the activation, then we set S TATE[y] ←
D OWN. At this point, if we have E`(y) (y) \ Mdown (y) = 0/ and `(y) > K, then the node y moves to a lower
level while being in D OWN state (see Case 2-b in Section 4.1).
Rule 3.10. Consider a node y such that either (1) S TATE[y] = D OWN and `(y) > K, or (2) S TATE[y] = U P -B.
This node becomes dirty after an activation that decreases its weight. In contrast, the node does not become
dirty after an activation that increases its weight.
Justification for Rule 3.10.
Case 1. S TATE[y] = D OWN and `(y) > K. Thus, we have f (β ) ≤ Wy < 1 − 2/β and Mup (y) = 0.
/ If an
activation decreases its weight, then y needs to down-mark some edges from E`(y) (y) \ Mdown (y), in the hope
that Wy does not become smaller than f (β ) (see the discussion in Section 3.2). Hence, the node y becomes
dirty. In contrast, if an activation increases its weight, then y need not up-mark, down-mark or un-mark any
of its incident edges. Due to this inaction, if it so happens that 1 − 2/β ≤ Wy < 1 − 1/β after the activation,
then the node simply switches to state D OWN -B or I DLE depending on whether or not Mdown (y) 6= 0.
/

Case 2. S TATE[y] = U P -B. Thus, we have 1 − 2/β ≤ Wy < 1 − 1/β , Mup (y) 6= 0/ and Mdown (y) = 0.
/ Such
a node must un-mark all its incident edges before its weight drops below the threshold 1 − 2/β (see the
discussion in Section 3.2). Hence, whenever its weight decreases due to an activation and S TATE[y] = U P -B,
the node y becomes dirty and un-marks some edges from Mup (y). In contrast, if an activation increases its
weight, then y need not up-mark, down-mark or un-mark any of its incident edges. Due to this inaction, if it
so happens that 1 − 1/β ≤ Wy < 1 after the activation, then we set S TATE[y] ← U P. At this point, if we have
E`(y) (y) = 0,
/ then the node y moves to a higher level while being in U P state (see Case 2-a in Section 4.1).
Rule 3.11. A node y with either (1) S TATE[y] ∈ {S LACK, I DLE} or (2) {S TATE[y] = D OWN and `(y) = K}
never becomes dirty after an activation.
12

Justification for Rule 3.11.
Case 1. S TATE[y] = S LACK. Here, we have 0 ≤ Wy < f (β ), Mup (y) = Mdown (y) = 0/ and `(y) = K. When
such a node gets activated, it need not up-mark or down-mark any of its incident edges. Due to this inaction,
if it so happens that f (β ) ≤ Wy < 1 − 2/β after the activation, then we set S TATE[y] ← D OWN.

Case 2. S TATE[y] = I DLE. Here, we have 1 − 2/β ≤ Wy < 1 − 1/β and Mup (y) = Mdown (y) = 0.
/ When such
a node gets activated, it need not up-mark or down-mark any of its incident edges. Due to this inaction, if it
so happens that 1 − 1/β ≤ Wy < 1 after the activation, then we set S TATE[y] ← U P. At this point, if we have
E`(y) (y) = 0,
/ then the node y moves to a higher level while being in U P state (see Case 2-a in Section 4.1).
In contrast, if it so happens that f (β ) ≤ Wy < 1 − 2/β after the activation, then we set S TATE[y] ← D OWN.
At this point, if we have E`(y) (y) \ Mdown (y) = 0/ and `(y) > K, then the node y moves to a lower level while
being in D OWN state (see Case 2-b in Section 4.1).
Case 3. S TATE[y] = D OWN and `(y) = K. Thus, we have f (β ) ≤ Wy < 1 − 2/β and Mup (y) = 0.
/ Since
`(y) = K and `y (x, y) ∈ [K, L] for every edge (x, y) ∈ E, we also have Mdown (y) = 0.
/ When such a node
gets activated, it need not up-mark or down-mark any of its incident edges. Due to this inaction, if we have
0 ≤ Wy < f (β ) after the activation, then we set S TATE[y] ← S LACK. In contrast, if 1 − 2/β ≤ Wy < 1 − 1/β
after the activation, then we set S TATE[y] ← I DLE.

Corollary 3.12. If an activation of a node y makes it dirty, then the state of the node remains the same just
before and just after the activation (see Section 6.1).
Proof. While justifying Rules 3.9 – 3.11, whenever we changed the state of the node y due to an activation,
we ensured that the node did not become dirty.
3.4

Data structures.

In our dynamic algorithm, every node y ∈ V maintains the following data structures.

1. Its weight Wy , level `(y), and state S TATE[y] ∈ {U P, D OWN , S LACK , I DLE , U P -B, D OWN -B}.
2. The sets Mup (y), Mdown (y) as balanced search trees.

3. A bit D[y] ∈ {0, 1} to indicate if the node y is dirty.

4. For every level i ∈ {0, . . . , L}, the set of edges Ei (y) as a balanced search tree.

Furthermore, every edge (x, y) ∈ E maintains the values of its weight w(x, y) and level `(x, y).

Remark about maintaining the shadow-levels. Note that we do not explicitly maintain the shadow-level
`x (x, y) of a node y ∈ V with respect to an edge (x, y) ∈ E. This is due to the following reason.
For the sake of contradiction, suppose that our algorithm in fact maintains the values of the shadowlevels `y (x, y). Consider a scenario where the node y has S TATE[y] = U P, `(y) = i, and the value of Wy is
very close to one. Next, suppose that an activation increases the value of Wy , and the node up-marks one or
more edges from the set Ei (y) to ensure that the value of Wy remains smaller than one. Since `(x, y) = i + 1
for every edge (x, y) ∈ Mup (y), all the newly up-marked edges get deleted from the set Ei (y) and added to
the set Ei+1 (y). At this point, we might end up in a situation where Ei (y) = 0,
/ which violates a constraint
of row (1) in Table 1. Our algorithm deals with this issue by moving the node y up to level (i + 1), i.e., by
setting `(y) ← (i + 1). Since Ei (y) = 0,
/ this does not affect the weight of any edge. However, for every edge
(x, y) ∈ E with `(x, y) > i + 1, the shadow-level `y (x, y) changes from i to (i + 1). Since each edge (x, y) ∈ E
with `(x, y) > i + 1 has weight at most β −(i+2) , and since Wy < 1, there can be β i+2 − 1 many such edges.
Accordingly, the node y might be forced to change the values of the shadow-levels `y (x, y) for O(β i+2 ) many
edges (x, y). The worst-case update time then becomes O(β i+2 ), which is polynomial in n for large values
of i.

13

We avoid this problem by giving up on explicitly maintaining the values of the shadow-levels `y (x, y).
Still we can determine the value of `x (x, y) in O(log n) time from the data structures that are in fact maintained by us. Specifically, we know that if (x, y) ∈ Mup (y), then `y (x, y) = `(y) + 1. Else if (x, y) ∈ Mdown (y),
then `y (x, y) = `(y) − 1. Finally, else if (u, y) ∈
/ Mup (y) ∪ Mdown (y), then `y (x, y) = `(y).
For ease of exposition, we nevertheless use the notation `y (x, y) while describing our algorithm in subsequent sections. Whenever we do this, the reader should keep it in mind that we are implicitly computing
`y (x, y) as per the above procedure.

4
4.1

Some basic subroutines
The subroutine UPDATE-STATUS(y).

This subroutine is called each time a node y experiences a natural or an induced activation. This tries
to ensure, by changing the state and level of y if necessary, that y satisfies the constraints specified in
Table 1. If the subroutine fails to ensure this condition, then our algorithm HALTS. During the analysis of
our algorithm, we will prove that it never HALTS due to a call to UPDATE-STATUS(y). This implies that
every node satisfies the constraints in Table 1, and hence Lemma 3.8 guarantees that conditions (2) and (3)
of Definition 3.1 continue to remain satisfied all the time.
We say that a node is fit in a state X ∈ {U P, D OWN, S LACK, I DLE, U P -B, D OWN -B} if it satisfies all the
constraints for state X as specified in Table 1, and unfit otherwise. If D[y] = 1, then our algorithm HALTS
if y is unfit in its current state. In contrast, if D[y] = 0, then our algorithm HALTS if y is unfit in every state,
albeit with one caveat: If the node is unfit in either state U P or state D OWN, then we first try to make it fit
in that state by changing its level `(y). Hence, there is a sharp distinction between the treatments received
by the clean nodes on the one hand and the dirty nodes on the other. Specifically, the state of a node y
can change during to a call to UPDATE-STATUS(y) only if y is clean at the beginning of the call. This
distinction comes from Corollary 3.12, which requires that a node does not change its state if it becomes
dirty. We now describe the subroutine in details.
Case 1. D[y] = 1. The node y is dirty.
If y is fit in its current state, then we terminate the subroutine. Otherwise our algorithm HALTS.
Case 2. D[y] = 0. The node y is clean.
If we can find some state X ∈ {U P, D OWN, S LACK, I DLE, U P -B, D OWN -B} in which y is fit, then we set
S TATE[y] ← X and terminate the subroutine. Else if the node y is unfit in every state, then we consider the
sub-cases 2-a, 2-b and 2-c.
Case 2-a. The node is unfit in state U P only due to the last constraint in row (1) of Table 1. Thus, we
have 1 − 1/β ≤ Wy < 1, Mdown (y) = 0/ and E`(y) (y) = 0.
/ Let i ← `(y) be the current level of y. We find the
minimum level j > i where E j (y) 6= 0.
/ Such a level j must exist since Wy > 0. We move the node y up to
level j by setting `(y) ← j. This does not change the weight of any edge. Furthermore, when the node was
in level i, we had `y (x, y) ≤ `(y) + 1 ≤ i + 1 ≤ j for every edge (x, y) ∈ E incident on y (see Invariant 3.4).
Hence, after the node moves up to level j, we have `y (x, y) = j = `(y) for every edge (x, y) ∈ E. In other
words, the node y is not supposed to have any up-marked edges incident on it just after moving to level j.
Accordingly, we set Mup (y) ← 0.
/ Then we terminate the subroutine.
Case 2-b. The node is unfit in state D OWN only due to the last constraint in row (2) of Table 1. Thus, we
have f (β ) ≤ Wy < 1 − 2/β , Mup (y) = 0,
/ E`(y) (y) \ Mdown (y) = 0/ and `(y) > K. Let i ← `(y) be the current
level of y. We first move the node down to level i − 1 by setting `(y) ← i − 1. We claim that this does
not change the level (and weight) of any edge. To see why the claim is true, consider any edge (x, y) ∈ E
incident on y. Since Mup (y) = 0,
/ we must have `y (x, y) ≤ i just before the node moves down to level (i − 1).
If `x (x, y) ≥ i, then the value of `(x, y) is determined by the other endpoint x and the level of such an edge
does not change as y moves down to level (i − 1). In contrast, if `x (x, y) < i, then we have (x, y) ∈ Mdown (y):
14

for otherwise the edge (x, y) will belong to the set Ei (y) \ Mdown (y) which we have assumed to be empty.
The level of such an edge remains equal to (i − 1) as the node y moves down from level i to level (i − 1).
This concludes the proof of the claim that the edge-weights do not change as y moves down from level i to
level (i − 1). Next, consider any edge (x, y) that was down-marked when the node y was at level i. At that
time, we had `y (x, y) = i − 1. Hence, after the node moves down to level i − 1, we get `y (x, y) = i − 1 = `(y).
Thus, the node cannot have any down-marked edge incident on it just after moving down to level i − 1.
Accordingly, we set Mdown (y) ← 0.
/ At this point, if we find that Ei−1 (y) = 0,
/ then we move the node further
down to the lowest level K, by setting `(y) ← K. This does not change the level and weight of any edge in
the graph. Finally, we terminate the subroutine.
Case 2-c. In every scenario other than 2-a and 2-b described above, our algorithm HALTS.
A note on the space complexity. In cases 2-a and 2-b of the above procedure, there is a step where
we set Mup (y) ← 0/ and Mdown (y) ← 0/ respectively. It is essential to execute this step in O(poly log n)
time: otherwise we cannot claim that the update time of our algorithm is O(poly log n) in the worst-case.
Unfortunately for us, there can be Ω(β `(y) ) many edges in the set Mup (y) or Mdown (y). Hence, it will take
Ω(β `(y) ) time to empty that set if we have to delete all those edges from the corresponding balanced search
tree. Note that β `(y) = Ω(n) for large `(y).
To address this concern, we maintain two pointers root[Mup (y)] and root[Mdown (y)] for each node y ∈ V .
They respectively point to the root of the balanced search tree for Mup (y) and Mdown (y). When we want to
set Mup (y) ← 0/ or Mdown (y) ← 0,
/ we respectively set root[Mup (y)] ← NULL or root[Mdown (y)] ← NULL.
This takes only constant time. The downside of this approach is that the algorithm now uses up a lot of junk
space in memory: This space is occupied by the balanced search trees that were emptied in the past. As
a result, the space complexity of the algorithm becomes O(t poly log n) for handling a sequence of t edge
insertions/deletions starting from an empty graph. This is due to the fact that our algorithm will be shown to
have a worst-case update time of O(poly log n). Hence, we can upper bound the total time taken to handle
these edge insertions/deletions by O(t poly log n), and this, in turn, gives a trivial upper bound on the amount
of junk space used up in the memory.
A standard way to bring down the space complexity is to run a clean-up algorithm in the background.
Each time an edge is inserted into or deleted from the graph, we visit O(poly log n) memory cells that
are currently junk and free them up. Thus, the worst case update time of the clean-up algorithm is also
O(poly log n), and this increases the overall update time of our scheme by only a O(poly log n) factor. The
size of all sets Mup (.) and Mdown (.) that exist at a given point in time is O(m). Hence, this clean-up algorithm
is at most O(m) space “behind”, i.e., the additional space requirement for junk space is O(m). For ease of
exposition, from this point onward we will simply assume that we can empty a balanced search tree in O(1)
time.
Lemma 4.1. The subroutine UPDATE-STATUS(y) takes O(log n) time.
Proof. Case 1 can clearly be implemented in O(1) time. In case 2-a, we have to find the minimum level
j > i where E j (y) 6= 0.
/ This operation takes time proportional to the number of levels, which is L − K + 1 =
O(log n). Everything else takes O(1) time. Finally, case 2-b and case 2-c also take O(1) time.
4.2

The subroutine PIVOT-UP(v, (u, v)).

This is described in Figure 3. This subroutine is called when the node v is dirty and it wants to increase its
shadow-level `v (u, v) with respect to the edge (u, v). There are two situations under which such an event can
take place: (1) S TATE[v] = U P and v wants to up-mark the edge (u, v), and (2) S TATE[v] = D OWN -B and v
wants to un-mark the edge (u, v). The subroutine PIVOT-UP(v, (u, v)) updates the relevant data structures,
decides whether the node u should become dirty because of this event, and returns T RUE if the event changes
the weight of the edge (u, v) and FALSE otherwise. Thus, if the subroutine returns T RUE, then this amounts
to an induced activation of the node u.
15

The subroutine MOVE-UP(v, (u, v)). Step (01) in Figure 3 calls another subroutine MOVE-UP(v, (u, v)).
This subroutine (described in Figure 4) updates the relevant data structures as the value of `v (u, v) increases
by one, and returns T RUE if the weight w(u, v) gets changed and FALSE otherwise. To see an example where
MOVE-UP(v, (u, v)) returns FALSE, consider a situation where S TATE[v] = D OWN -B, `(v) = i, `v (u, v) =
i − 1, and `u (u, v) = `(u) = i. In this instance, even after the node v increases the value of `v (u, v) by
un-marking the edge (u, v), the weight w(u, v) does not change.
The subroutine MOVE-UP(v, (u, v)) ensures that Invariant 3.7 remains satisfied. Specifically, after the
value of `v (u, v) increases we might have `v (u, v) > `(u), and then we must ensure that the edge (u, v) ∈
/
Mup (u) ∪ Mdown (u): otherwise Invariant 3.7 will be violated (set y = u and x = v in Invariant 3.7). If we end
up in this situation, then the subroutine MOVE-UP(v, (u, v)) removes the edge from Mup (u) ∪ Mdown (u).
01. Y ← MOVE-UP(v,(u, v))
// See Figure 4.
02. I F Y = T RUE and either S TATE[u] = U P -B or
(S TATE[u] = D OWN and `(u) > K)
03.
D[u] ← 1
04. UPDATE-STATUS(u)
05. RETURN Y .
Figure 3: PIVOT-UP(v, (u, v)).

01.
02.
03.
04.
05.
06.
07.
08.
09.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.

iv ← `v (u, v)
iu ← `u (u, v)
I F (u, v) ∈ Mdown (v)
Mdown (v) ← Mdown (v) \ {(u, v)}
E LSE
Mup (v) ← Mup (v) ∪ {(u, v)}
I F iv + 1 > `(u)
Mup (u) ← Mup (u) \ {(u, v)}
Mdown (u) ← Mdown (u) \ {(u, v)}
I F `(u, v) = max(iv + 1, iu )
RETURN FALSE
w(u, v) ← β −(`(u,v)+1)
Wu ← Wu − β −`(u,v) + β −(`(u,v)+1)
Wv ← Wv − β −`(u,v) + β −(`(u,v)+1)
E`(u,v) (u) ← E`(u,v) (u) \ {(u, v)}
E`(u,v)+1 (u) ← E`(u,v)+1 (u) ∪ {(u, v)}
E`(u,v) (v) ← E`(u,v) (v) \ {(u, v)}
E`(u,v)+1 (v) ← E`(u,v)+1 (v) ∪ {(u, v)}
`(u, v) ← `(u, v) + 1
RETURN T RUE
Figure 4: MOVE-UP(v, (u, v)).

Deciding if the node u becomes dirty. We now continue with the description of the subroutine PIVOTUP(v, (u, v)). After step (01) in Figure 3, it remains to decide whether the node u should become dirty. This
decision is made following the three rules specified in Section 3.3. Note that if we increase the value of
16

`v (u, v), then it can never lead to an increase in the weight Wu . Thus, if Y = T RUE, then it means that the
weight Wu dropped during the call to the subroutine MOVE-UP(v, (u, v)). On the other hand, if Y = FALSE,
then it means that the weight Wu did not change during the call to the subroutine MOVE-UP(v, (u, v)). In
this event, the node u never becomes dirty.
As per Rules 3.9 – 3.11, if the weight Wu gets reduced, then u becomes dirty iff either S TATE[u] = U P -B
or (S TATE[u] = D OWN, `(u) > K). Thus, the subroutine sets D[u] ← 1 iff two conditions are satisfied: (1)
Y = T RUE, and (2) either S TATE[u] = U P -B or (S TATE[u] = D OWN, `(u) > K).
Finally, just before terminating the subroutine PIVOT-UP(v, (u, v)) in Figure 3, we call the subroutine
UPDATE-STATUS(u). The reason for this call is explained in the beginning of Section 4.1.
Lemma 4.2. The subroutine PIVOT-UP(v, (u, v)) takes O(log n) time. It returns T RUE if the weight w(u, v)
gets changed, and FALSE otherwise. The node u becomes dirty only if the subroutine returns T RUE.
Proof. A call to the subroutine UPDATE-STATUS(y) takes O(log n) time, as per Lemma 4.1. The rest of
the proof follows from the description of the subroutine.
4.3

The subroutine PIVOT-DOWN(v, (u, v)).

This is described in Figure 5. This subroutine is called when the node v is dirty and it wants to decrease
its shadow-level `v (u, v) with respect to the edge (u, v). There are two situations under which such an event
can take place: (1) S TATE[v] = D OWN and v wants to down-mark the edge (u, v), and (2) S TATE[v] = U P -B
and v wants to un-mark the edge (u, v). The subroutine PIVOT-DOWN(v, (u, v)) updates the relevant data
structures, decides whether the node u should become dirty, and returns T RUE if the weight of the edge
(u, v) gets changed and FALSE otherwise. Thus, if the subroutine returns T RUE, then this amounts to an
induced activation of the node u. This subroutine, however, is not a mirror-image of the subroutine PIVOTUP(v, (u, v)). The difference between them is explained below.
In the subroutine PIVOT-DOWN(v, (u, v)), suppose that the node v has decreased the value of `v (u, v),
and this has increased the weight Wu . Furthermore, the node u is currently in a state where Rules 3.9 – 3.11
dictate that it should become dirty when its weight increases. If this is the case, then the node u attempts
to undo its weight-change by increasing the value of `u (u, v). To take a concrete example, suppose that just
before the subroutine PIVOT-DOWN(v, (u, v)) is called, we have S TATE[v] = U P -B, `(v) = i, `v (u, v) = i+1,
S TATE[u] = U P, `(u) = i and `u (u, v) = i. The node v now decreases the value of `v (u, v) by one, and unmarks the edge (u, v). Thus, the weight w(u, v) changes from β −(i+1) to β −i . This also increases the weight
Wu by an amount β −i − β −(i+1) . The node u will now undo this change by up-marking the edge (u, v),
which will increase `u (u, v) by one. This will bring the weight Wu back to its initial value. In contrast, the
subroutine PIVOT-UP(v, (u, v)) does not allow the node u to perform such “undo” operations. This “undo”
operation performed by u in PIVOT-DOWN(v, (u, v)) will be crucial in bounding the update time of our
algorithm.
The subroutine MOVE-DOWN(v, (u, v)).
Step (01) in Figure 5 calls MOVE-DOWN(v, (u, v)). This
subroutine (described in Figure 6) updates the relevant data structures as the value of `v (u, v) decreases
by one, and returns T RUE if the weight w(u, v) gets changed and FALSE otherwise. To see an example
where MOVE-DOWN(v, (u, v)) returns FALSE, consider a situation where S TATE[v] = D OWN, `(v) = i,
`v (u, v) = i, and `u (u, v) = `(u) = i. In this instance, even after the node v decreases the value of `v (u, v) by
down-marking the edge (u, v), the weight w(u, v) does not change.
Unlike the subroutine MOVE-UP(v, (u, v)), here we need not worry about Invariant 3.7 getting violated,
for the following reason. Set v = x and u = y in Invariant 3.7 just as we did while considering the subroutine
MOVE-UP(v, (u, v)). If `u (u, v) = `(u), the Invariant 3.7 clearly remains satisfied even as `v (u, v) decreases
by one. If `u (u, v) 6= `(u), then by Invariant 3.7 we have `v (u, v) ≤ `(u) just before the call to MOVEDOWN(v, (u, v)). In this case as well, Invariant 3.7 continues to remain satisfied even as `v (u, v) decreases
by one.
17

01. Y ← MOVE-DOWN(v, (u, v))
// See Figure 6.
02. I F S TATE[u] = U P
03. I F Y = T RUE
V
04.
I F (u, v) ∈
/ Mup (u) `(u) ≥ `v (u, v)
05.
MOVE-UP(u, (u, v))
06.
UPDATE-STATUS(u)
07.
RETURN FALSE
08.
E LSE
09.
D[u] ← 1
10.
UPDATE-STATUS(u)
11.
RETURN Y .
12. E LSE
13.
UPDATE-STATUS(u)
14.
RETURN Y .
15. E LSE IF S TATE[u] = D OWN -B
16. I F Y = T RUE, T HEN
V
17.
I F (u, v) ∈ Mdown (u) `v (u, v) < `(u)
18.
MOVE-UP(u, (u, v))
19.
UPDATE-STATUS(u)
20.
RETURN FALSE
21.
E LSE
22.
D[u] ← 1
23.
UPDATE-STATUS(u)
24.
RETURN Y .
25. E LSE
26.
UPDATE-STATUS(u)
27.
RETURN Y .
28. E LSE
29. UPDATE-STATUS(u)
30. RETURN Y .
Figure 5: PIVOT-DOWN(v, (u, v)). Steps (05) and (18) correspond to “undo” operations by the node u.

18

01.
02.
03.
04.
05.
06.
07.
08.
09.
10.
11.
12.
13.
14.
15.
16.
17.

iv ← `v (u, v)
iu ← `u (u, v)
I F (u, v) ∈ Mup (v)
Mup (v) ← Mup (v) \ {(u, v)}
E LSE
Mdown (v) ← Mdown (v) ∪ {(u, v)}
I F `(u, v) = max(iv − 1, iu )
RETURN FALSE
w(u, v) ← β −(`(u,v)−1)
Wu ← Wu − β −`(u,v) + β −(`(u,v)−1)
Wv ← Wv − β −`(u,v) + β −(`(u,v)−1)
E`(u,v) (u) ← E`(u,v) (u) \ {(u, v)}
E`(u,v)−1 (u) ← E`(u,v)−1 (u) ∪ {(u, v)}
E`(u,v) (v) ← E`(u,v) (v) \ {(u, v)}
E`(u,v)−1 (v) ← E`(u,v)−1 (v) ∪ {(u, v)}
`(u, v) ← `(u, v) − 1
RETURN T RUE

Figure 6: MOVE-DOWN(v, (u, v)).
Deciding if the node u becomes dirty. We continue with the description of PIVOT-DOWN(v, (u, v)).
After step (01) in Figure 5, it remains to decide whether (a) the node u is about to become dirty, and if the
answer is yes, then whether (b) the node can escape this fate by successfully executing an “undo” operation.
Decision (a) is taken following the Rules 3.9 – 3.11.
Since the subroutine PIVOT-DOWN(v, (u, v)) is called when the node v wants to decrease the value of
`v (u, v), this can never lead to a decrease in the value of Wu . In other words, step (01) in Figure 5 can only
increase the weight Wu . Specifically, if Y = T RUE, then the weight Wy increases. In contrast, if Y = FALSE,
then the weight Wu does not change at all. In the latter event, the node u never becomes dirty, and the question
of u attempting to execute an “undo” operation does not arise. In the former event, Rules 3.9 – 3.11 dictate
that the node u is about to become dirty iff S TATE[u] ∈ {U P, D OWN -B}. This is the only situation where we
have to check if the node u can execute a successful “undo” operation. This situation can be split into two
mutually exclusive and exhaustive cases (1) and (2), as described below. In every other situation, the node u
does not become dirty, it does not perform an undo operation, and the subroutine PIVOT-DOWN(v, (u, v))
returns the same value as Y . Finally, just before terminating the subroutine PIVOT-DOWN(v, (u, v)) we
always call UPDATE-STATUS(u). The reason for this step is explained in the beginning of Section 4.1.
Case 1: Y = T RUE and S TATE[u] = U P.
See steps (03) – (11) in Figure 5. In this case, either (u, v) ∈ Mup (u) or (u, v) ∈
/ Mup (u). In the former
event, the edge (u, v) has already been up-marked by u, and hence u cannot increase the value of `u (u, v) any
further. In the latter event, we have `u (u, v) = `(u). Before up-marking the edge (u, v), the node u should
ensure that it satisfies Invariant 3.7 (set u = y and v = x). Hence, we must have `v (u, v) ≤ `(u) if the node u
is to execute an undo operation. To summarise, we have to sub-cases.
Case 1-a: (u, v) ∈
/ Mup (u) and `v (u, v) ≤ `(u). In this event, increasing the value of `u (u, v) by one changes
the weight w(u, v) from β −`(u) to β −(`(u)+1) . This undo operation is performed by calling the subroutine
MOVE-UP(u, (u, v)).
Case 1-b: Either (u, v) ∈ Mup (u) and `v (u, v) > `(u). In this event, the node u cannot perform an undo
operation and becomes dirty as per Rule 3.9.
19

Case 2: Y = T RUE and S TATE[u] = D OWN -B.
See steps (16) – (24) in Figure 5. In this case, either (u, v) ∈ Mdown (u) or (u, v) ∈
/ Mdown (u). In the latter
event, the only way u can increase the value of `u (u, v) is by up-marking the edge (u, v). But this would
result in the set Mup (u) becoming non-empty, which in turn would violate a constraint in row (6) of Table 1.
Hence, the node u can perform an undo operation only if (u, v) ∈ Mdown (u). Further, if `v (u, v) ≥ `(u) and
(u, v) ∈ Mdown (u), then the weight w(u, v) remains equal to β −`v (u,v) even as the value of `u (u, v) changes
from `(u) − 1 to `(u). This prevents u from executing an undo operation. To summarise, there are two
sub-cases.
Case 2-a: We have (u, v) ∈ Mdown (u) and `v (u, v) < `(u). In this event, increasing the value of `u (u, v) by
one changes the weight w(u, v) from β −(`(u)−1) to β −`(u) . This undo operation is performed by calling the
subroutine MOVE-UP(u, (u, v)).
Case 2-b: Either (u, v) ∈ Mdown (u) or `v (u, v) ≥ `(u). In this event, the node u cannot perform an undo
operation and becomes dirty as per Rule 3.9.
Lemma 4.3. The subroutine PIVOT-DOWN(v, (u, v)) takes O(log n) time. It returns T RUE if the weight
w(u, v) gets changed, and FALSE otherwise. The node u becomes dirty only if the subroutine returns T RUE.
Proof. A call to the subroutine UPDATE-STATUS(y) takes O(log n) time, as per Lemma 4.1. The rest of
the proof follows from the description of the subroutine.

5

The subroutine FIX-DIRTY-NODE(v)

Note that the node v undergoes a natural activation when an edge (u, v) is inserted into or deleted from
the graph. In contrast, the node v undergoes an induced activation when some neighbour x of v calls the
subroutine PIVOT-UP(x, (x, v)) or PIVOT-DOWN(x, (x, v)), and that subroutine returns T RUE.
The subroutine FIX-DIRTY-NODE(v) is called immediately after the node v becomes dirty due to a
natural or an induced activation. Depending on the current state of v, the subroutine up-marks, down-marks
or un-marks some of its incident edges (u, v) ∈ E. This involves increasing or decreasing the shadow-level
`v (u, v) by one, for which the subroutine respectively calls PIVOT-UP(v, (u, v)) or PIVOT-DOWN(v, (u, v)).
We say that a given call to PIVOT-UP(v, (u, v)) or PIVOT-DOWN(v, (u, v)) is a success if the weight w(u, v)
gets changed due to the call (i.e., the call returns T RUE), and a failure otherwise (i.e., the call returns FALSE).
We ensure that one call to the subroutine FIX-DIRTY-NODE(v) leads to at most one success.
To summarise, the subroutine FIX-DIRTY-NODE(v) makes a series of calls to PIVOT-UP(v, (u, v)) or
PIVOT-DOWN(v, (u, v)). We terminate the subroutine immediately after the first such call returns T RUE.
We also make the node v clean just before the subroutine FIX-DIRTY-NODE(v) terminates. Hence, Lemmas 4.2, 4.3 imply the following observation.
Observation 5.1. The node v becomes clean at the end of the subroutine FIX-DIRTY-NODE(v). Furthermore, during a call to the subroutine FIX-DIRTY-NODE(v), at most one neighbour of the node v becomes
dirty.
We now describe the subroutine FIX-DIRTY-NODE(v) in a bit more detail. See Figure 7. Note that
the node v becomes dirty only if it experiences an activation, and the subroutine FIX-DIRTY-NODE(v)
is called immediately after the node v becomes dirty. Thus, Rule 3.11 and Corollary 3.12 imply that at
the beginning of the subroutine FIX-DIRTY-NODE(v) we must have: either (1) S TATE[v] = U P, or (2)
S TATE[v] = D OWN -B, or (3) S TATE[v] = D OWN and `(y) > K, or (4) S TATE[v] = U P -B. Accordingly,
we call one of the four subroutines: FIX-UP(v), FIX-DOWN-B(v), FIX-DOWN(v) and FIX-UP-B(v).
For the rest of Section 5, we focus on describing these four subroutines. Note that we call UPDATESTATUS(v) just before terminating the subroutine FIX-DIRTY-NODE(v), for a reason that is explained in

20

01.
02.
03.
04.
05.
06.
07.
08.
09.

I F S TATE[v] = U P
FIX-UP(v)
E LSE IF S TATE[v] = D OWN -B
FIX-DOWN-B(v)
E LSE IF S TATE[v] = D OWN and `(y) > K
FIX-DOWN(v)
E LSE IF S TATE[v] = U P -B
FIX-UP-B(v)
UPDATE-STATUS(v)
Figure 7: FIX-DIRTY-NODE(v).

the beginning of Section 4.1. We now give a bound on the runtime of the subroutine, which follows from
Lemmas 5.3, 5.4, 5.5, 5.6 and 4.1.
Lemma 5.2. The subroutine FIX-DIRTY-NODE(v) takes O(log2 n) time.
01. D[v] ← 0, i ← `(v)
02. Pick an edge (u, v) ∈ Ei (v).
03. PIVOT-UP(v, (u, v))
Figure 8: FIX-UP(v).
5.1

FIX-UP(v).

See Figure 8. This subroutine is called when a node v with S TATE[v] = U P becomes dirty due to an activation. This activation must have increased the weight Wv . See Rule 3.9 and Case (1) of its subsequent
justification. Let i = `(v) be the current level of the node. Since S TATE[v] = U P, we must have Ei (v) 6= 0/
as per row (1) of Table 1. The node v picks any edge (u, v) ∈ Ei (v) and up-marks that edge by calling the
subroutine PIVOT-UP(v, (u, v)). See the justification for Rule 3.9. Since (u, v) ∈ Ei (v) just before this step,
we must have `u (u, v) ≤ i. This means that increasing the shadow-level `v (u, v) from i to (i + 1) changes
the weight w(u, v) from β −i to β −(i+1) . In other words, the very first call to PIVOT-UP(v, (u, v)) becomes a
success. Thus, we terminate the subroutine. Lemma 5.3 now follows from Lemma 4.2.
Lemma 5.3. The runtime of FIX-UP(v) is O(log n).
5.2

FIX-DOWN-B(v).

See Figure 9. This subroutine is called when a node v with S TATE[v] = D OWN -B becomes dirty due to an
activation. This activation must have increased the weight Wv . See Rule 3.9 and Case (2) of its subsequent
justification. Since S TATE[v] = D OWN -B, we must have Mdown (v) 6= 0/ as per row (6) of Table 1.
The node v picks an edge (u, v) ∈ Mdown (v), and un-marks it by calling PIVOT-UP(v, (u, v)).
We keep repeating the above step until one of three events occurs: (1) The set Mdown (v) becomes empty. (2)
We make the β 5 -th call to PIVOT-UP(v, (u, v)). (3) We encounter the first call to PIVOT-UP(v, (u, v)) which
leads to a change in the weight w(u, v). We then terminate the subroutine. By Lemma 4.2, each iteration of
the W HILE loop in Figure 9 takes O(log n) time. This gives us the following lemma.
Lemma 5.4. The subroutine FIX-DOWN-B(v) takes O(β 5 log n) = O(log n) time, for constant β .

21

01. D[v] ← 0, k ← 0
02. W HILE k < β 5
03.
k ← k+1
04.
I F Mdown (v) = 0/
05.
BREAK
06.
Pick an edge (u, v) ∈ Mdown (v).
07.
X ← PIVOT-UP(v, (u, v))
08.
I F X = T RUE
09.
BREAK
Figure 9: FIX-DOWN-B(v).
01. D[v] ← 0, i ← `(v), k ← 0
02. W HILE k < β 5 L
03.
k ← k+1
04.
I F Ei (v) \ Mdown (v) = 0/
05.
BREAK
06.
Pick an edge (u, v) ∈ Ei (v) \ Mdown (v).
07.
X ← PIVOT-DOWN(v, (u, v))
08.
I F X = T RUE
09.
BREAK
Figure 10: FIX-DOWN(v).
5.3

FIX-DOWN(v).

See Figure 10. This subroutine is called when a node v with S TATE[v] = D OWN and `(v) > K becomes dirty
due to an activation. This activation must have decreased the weight Wv . See Rule 3.10 and Case (1) of
its subsequent justification. Let i = `(v) be the current level of the node v. Since S TATE[v] = D OWN and
`(y) > K, we must have Ei (v) \ Mdown (v) 6= 0/ as per row (2) of Table 1.
The node v picks an edge (u, v) ∈ Ei (v) \ Mdown (v), and down-marks it by calling PIVOT-DOWN(v, (u, v)).

We keep repeating the above step until one of three events occurs: (1) The set Ei (v) \ Mdown (v) becomes
empty. (2) We make the β 5 L-th call to PIVOT-DOWN(v, (u, v)). (3) We encounter the first call to PIVOTDOWN(v, (u, v)) which leads to a change in the weight w(u, v). We then terminate the subroutine.
We now explain how to select an edge from Ei (v) \ Mdown (v) in step (06) of Figure 10. Recall that
we maintain the sets Ei (v) and Mdown (v) as balanced search trees as per Section 3.4. Specifically, we
maintain the elements of Ei (v) in a particular order. This ordered list is partitioned into two disjoint blocks:
The first block consists of the edges in Ei (v) \ Mdown (v), and the second block consists of the edges in
Ei (v) ∩ Mdown (v). During a given iteration of the W HILE loop in Figure 10, we pick an edge (u, v) that
comes first in this ordering of Ei (v) and check if (u, v) ∈ Mdown (v). If yes, then we know for sure that
Ei (v) \ Mdown (v) = 0,
/ and hence we terminate the subroutine. Else if (u, v) ∈
/ Mdown (v), then v down-marks
the edge by calling PIVOT-DOWN(v, (u, v)). Now, consider two cases.
1. The call to PIVOT-DOWN(v, (u, v)) is a failure. It means that the weight and the level of the edge (u, v)
do not change during the call. Hence, at the end of the call we get: (u, v) ∈ Ei (v) and (u, v) ∈ Mdown (v).
At this point we delete the edge (u, v) from Ei (v). Immediately afterward we again insert the edge
(u, v) back to Ei (v), but this time (u, v) occupies the last position in the ordering of Ei (v). Hence, the
ordering of Ei (v) remains correctly partitioned into two blocks as described above.
22

2. The call to PIVOT-DOWN(v, (u, v)) is a success. It means that the weight and the level of the edge
(u, v) changes during the call. At the end of the call we get: (u, v) ∈
/ Ei (v) and (u, v) ∈ Mdown (v). At
this point we terminate the subroutine FIX-DOWN(v). By Lemma 4.3, an iteration of the W HILE
loop in Figure 10 takes O(log n) time. This implies the lemma below.
Lemma 5.5. The subroutine FIX-DOWN(v) takes O(β 5 L · log n) = O(log2 n) time, for constant β .
01. D[v] ← 0, i ← `(v), k ← 0
02. W HILE k < β 5
03.
k ← k+1
04.
I F Mup (v) = 0/
05.
BREAK
06.
Pick an edge (u, v) ∈ Mup (v).
07.
X ← PIVOT-DOWN(v, (u, v))
08.
If X = T RUE
09.
BREAK
Figure 11: FIX-UP-B(v).
5.4

FIX-UP-B(v).

See Figure 11. This subroutine is called when a node v with S TATE[v] = U P -B becomes dirty due to an
activation. This activation must have decreased the weight Wv . See Rule 3.10 and Case (2) of its subsequent
justification. Since S TATE[v] = U P -B, we must have Mup (v) 6= 0/ as per row (5) of Table 1.
The node v picks an edge (u, v) ∈ Mup (v), and un-marks it by calling PIVOT-DOWN(v, (u, v)).

We keep repeating the above step until one of three events occurs: (1) The set Mup (v) becomes empty. (2) We
make the β 5 -th call to PIVOT-DOWN(v, (u, v)). (3) We encounter the first call to PIVOT-DOWN(v, (u, v))
which leads to a change in the weight w(u, v). We then terminate the subroutine. By Lemma 4.3, each
iteration of the W HILE loop in Figure 11 takes O(log n) time. This gives us the following lemma.
Lemma 5.6. The subroutine FIX-UP-B(v) takes O(β 5 · log n) = O(log n) time, for constant β .

6

Handling the insertion or deletion of an edge

In this section, we explain how our algorithm handles the insertion/deletion of an edge in the input graph.
Insertion of an edge (u, v). We set `u (u, v) ← `(u), `v (u, v) ← `(v) and `(u, v) ← max(`u (u, v), `v (u, v)).
The newly inserted edge gets a weight w(u, v) ← β −`(u,v) . Hence, each of the node-weights Wu and Wv
also increases by β −`(u,v) . This amounts to a natural activation for each of the endpoints {u, v}. For every
endpoint x ∈ {u, v}, we now decide if x should become dirty due to this activation. This decision is taken as
per Rules 3.9 – 3.11. We now call the subroutine UPDATE-STATUS(x) for x ∈ {u, v}, for reasons explained
in the beginning of Section 4.1. Finally, we call the subroutine FIX-DIRTY(.) as described in Figure 12.
Deletion of an edge (u, v). Just before the edge-deletion, its weight was w(u, v). We first decrease each of
the node-weights Wu ,Wv by w(u, v). Then we delete all the data structures associated with the edge (u, v).
This amounts to a natural activation for each of its endpoints. For every node x ∈ {u, v}, we decide if x
should become dirty due to this activation, as per Rules 3.9 – 3.11. At this point, we call the subroutine
UPDATE-STATUS(x) for x ∈ {u, v}, for reasons explained in the beginning of Section 4.1. Finally, we call
the subroutine FIX-DIRTY(.) as per Figure 12.

23

W HILE there exists a dirty node x ∈ V :
FIX-DIRTY-NODE(x)
// See Section 5.
Figure 12: FIX-DIRTY(.).
Two assumptions. For ease of analysis, we will make two simplifying assumptions. At first glance, these
assumptions might seem highly restrictive. But we will explain how the analysis can be extended to the
general setting, where these assumptions need not hold, by slightly modifying our algorithm.
Assumption 6.1. The insertion or deletion of an edge (u, v) makes at most one of its endpoints dirty.
Justification. Consider a scenario where the insertion or deletion of an edge (u, v) is about to make both its
endpoints dirty. Without any loss of generality, suppose that the weight of v increases by δv due to this edge
insertion or deletion. Note that δv can also be negative. We reset the weight Wv to the value it had just before
the edge insertion or deletion took place, by setting Wv ← Wv − δv . In other words, the node v becomes blind
to the fact that its weight has changed. Clearly, after this simple modification, only the node u becomes dirty.
We now go ahead and call the subroutine FIX-DIRTY(.). Starting from the node u, this creates a chain of
calls to FIX-DIRTY-NODE(x) for different x ∈ V (see Observation 5.1). When this chain stops, we go back
and update the weight of the other endpoint v, by setting Wv ← Wv + δv . So the node v now wakes up and
experiences an activation. If the node v becomes dirty due to this activation, as per Rules 3.9 – 3.11, then
we again go ahead and call the subroutine FIX-DIRTY(.). Starting from the node v, this creates a second
chain of calls to the subroutine FIX-DIRTY-NODE(x) for different x ∈ V . When this second chain stops, we
conclude that we have successively handled the insertion or deletion of the edge (u, v).
Assumption 6.2. The weight Wu of a node u changes by at most β −(`(u)+1) due to a natural activation.
Justification. For any edge (u, v), we have: `(u, v) ≥ `u (u, v) ≥ `(u) − 1, and w(u, v) = β −`(u,v) . So the
weight of any edge incident on u is at most ∆u = β −(`(u)−1) . Now, suppose that Assumption 6.2 gets
violated. Specifically, the weight Wu changes by ∆0u due to a natural activation, where ∆0u > β −(`(u)+1) . To
handle this situation, we fix the node u in ru rounds, where ru = ∆0u /β −(`(u)+1) ≤ ∆u /β −(`(u)+1) ≤ β 2 . In
each round, we change the weight Wu by β −(`(u)+1) and call the subroutine FIX-DIRTY(.). This way the
node becomes oblivious to the fact that Assumption 6.2 gets violated. The update time increases by a factor
of ru , which is O(1) for constant β .
Analysis of our algorithm. Just before the insertion or deletion of the edge (u, v), every node in the graph
is clean, and every node satisfies the constraints corresponding to its current state as specified by Table 1. By
Assumption 6.1, at most one endpoint x ∈ {u, v} becomes dirty due to this edge insertion/deletion. Hence, at
most one node is dirty in the beginning of the call to the subroutine FIX-DIRTY(.). By Observation 5.1, we
get a chain of calls to the subroutine FIX-DIRTY-NODE(y) for y ∈ V . Each call to FIX-DIRTY-NODE(y)
makes at most one neighbour of y dirty, which is fixed at the next iteration of the W HILE loop in Figure 12.
Thus, at every point in time there is at most one dirty node in the entire graph. We now prove two theorems.
Theorem 6.3. While handling a sequence of edges insertions and deletions, our algorithm never HALTS
due to a call to the subroutine UPDATE-STATUS(y).
The proof of Theorems 6.3 appears in Section 7. Recall the discussion in the first paragraph of Section 4.1. To summarise that discussion, Theorem 6.3 ensures that throughout the duration of our algorithm,
every node satisfies the constraints corresponding to its current state as per Table 1. Hence, by Lemma 3.8,
conditions (2) and (3) of Definition 3.1 continue to remain satisfied all the time. This observation, along
with Corollary 3.5, implies that our algorithm successfully maintains a nice-partition as per Definition 3.1.
24

In Theorem 6.4, we bound the worst-case update time of our algorithm. The proof of this theorem
appears in Section 8. Intuitively, we show that after four consecutive calls to FIX-DIRTY-NODE(x) in
the W HILE loop of Figure 12, the value of `(x) decreases by at least one. Since `(x) ∈ [K, L] for every
node x ∈ V , there can be at most 4(L − K + 1) = O(log n) iterations of the W HILE loop of Figure 12. By
Lemma 5.2, each iteration of this W HILE loop takes O(log2 n) time. Accordingly, the subroutine FIXDIRTY(.) as described in Figure 12 takes O(log3 n) time, and this gives an upper bound on the worst-case
update time of our algorithm.
Theorem 6.4. Our algorithm handles an edge insertion or deletion in O(log3 n) worst-case time.
The main result of this paper (Theorem 3.3) follows from Theorems 6.3 and 6.4.
6.1

Recap of our algorithm.

During the course of our algorithm, the weight of a node x can change only under three scenarios:
• (1) An edge incident to x gets inserted or deleted.
• (2) A neighbour y of x makes a call to PIVOT-UP(y, (x, y)) or PIVOT-DOWN(y, (x, y)) and the call
returns T RUE. In this scenario, the weight-change occurs only during the call to MOVE-UP(y, (x, y))
or MOVE-DOWN(y, (x, y)).
• (3) The node x makes a call to FIX-DIRTY-NODE(x).
Note that scenarios (2) and (3) are symmetric: a call is made to the subroutine PIVOT-UP(y, (x, y)) or PIVOTDOWN(y, (x, y)) only when y itself is executing FIX-DIRTY-NODE(y). Scenarios (1) and (2) respectively
correspond to a natural and an induced activation of x. A node x can become dirty only due to a natural or
an induced activation, as per Rules 3.9– 3.11. Scenario (3) is the response of x after it becomes dirty. At the
end of the call to FIX-DIRTY-NODE(x) in scenario (3), the node x becomes clean again.
During the course of our algorithm, the shadow-level `y (x, y) of an edge (x, y) increases iff a call is made
to MOVE-UP(y, (x, y)), and decreases iff a call is made to MOVE-DOWN(y, (x, y)). These two subroutines
are defines in Sections 4.2 and 4.3. A call to MOVE-DOWN(y, (x, y)) is made only if we are executing
the subroutine PIVOT-DOWN(y, (x, y)). In contrast, a call to MOVE-UP(y, (x, y)) is made only if we are
executing either the subroutine PIVOT-UP(y, (x, y)) or the subroutine PIVOT-DOWN(x, (x, y)).

7

Proof of Theorem 6.3

Let U = {U P, D OWN, S LACK, I DLE, U P -B, D OWN -B} be the set of all possible states of a node (see Table 1). For the rest of this section, we assume that our algorithm HALTS at a time-instant (say) t1 due
to a call made to UPDATE-STATUS(x) for some node x ∈ V . Suppose that S TATE[x] = S at time t1 . To
prove Theorem 6.3, it suffices to derive a contradiction for all S ∈ U . These contradictions are derived in
Sections 7.1 – 7.6.
Let t0 < t1 be the unique time-instant such that: (1) S TATE[x] = S throughout the time-interval [t0 ,t1 ] and
(2) S TATE[x] 6= S just before time-instant t0 . During the time-interval [t0 ,t1 ], the node-weight Wx can change
due to three types of events: We classify these types as A, B and C, and specify each of them below.
• Type A: An activation of x increases the weight Wx .
• Type B: An activation of x decreases the weight Wx .
• Type C: We call the subroutine FIX-DIRTY-NODE(x).
Rules 3.9 – 3.11 dictate whether or not the node x becomes dirty after an event of Type A or B. A Type C
event occurs when x becomes dirty due to a Type A or Type B event. The node x becomes clean again before
the call to FIX-DIRTY-NODE(x) ends.
7.1

Deriving a contradiction for S = U P -B

The only way the node x can change its level is if we execute the steps in Case 2-a or 2-b during a call to
UPDATE-STATUS(x). This situation can never occur during the time-interval [t0 ,t1 ], throughout which we
have S TATE[x] = S = U P -B. Thus, the node x stays at the same level throughout the time-interval [t0 ,t1 ].
25

In Claims 7.1 and 7.2, we respectively bound the weight Wx at time-instants t0 and t1 . In Corollary 7.3,
we use these two claims to bound the change in the weight Wx during the time-interval [t0 ,t1 ].
Claim 7.1. Wx ≥ 1 − 1/β − 1/β K at time t0 .
Proof. The node x undergoes an activation at time t0 which changes its state to U P -B. As per the discussion
in Section 3.3, the only way this can happen is if S TATE[x] = U P just before time t0 and the activation at time
t0 decreases Wx (see Case 1 in the justification for Rule 3.9). Thus, row (1) in Table 1 gives us: Wx ≥ 1 − 1/β
just before time t0 . Since the weight of an edge is at most β −K , the activation of x at time t0 changes Wx by
at most β −K . So we get: Wx ≥ 1 − 1/β − 1/β K after the activation of x at time t0 .
Claim 7.2. Wx < 1 − 2/β and Mup (x) 6= 0/ at time t1 .
Proof. S TATE[x] = U P -B throughout the time-interval [t0 ,t1 ]. Just before time t1 , the node x undergoes
an activation, say, a*. Subsequent to the activation a*, our algorithm HALTS during a call to UPDATESTATUS(x) at time t1 . From row (5) of Table 1, we get: Mdown (x) = 0,
/ Mup (x) 6= 0/ and 1 − 2/β ≤ Wx <
1 − 1/β just before the activation a*. No edge gets inserted into the sets Mup (x) and Mdown (x) during the
activation a*. Since the algorithm HALTS at time t1 , the activation a* must have changed the weight Wx in
such a way that the node x violates the constraints for every state as defined in Table 1. This can happen
only if Wx < 1 − 2/β and Mup (x) 6= 0/ at time t1 .
Corollary 7.3. During the interval [t0 ,t1 ], the node-weight Wx decreases by at least 1/β − 1/β K .
Proof. Follows from Claims 7.1 and 7.2.
Claim 7.4. An event of Type A does not make the node x dirty. An event of Type B makes the node x dirty.
Proof. Throughout the time-interval [t0 ,t1 ], we have S TATE[x] = U P -B. So the claim follows from Rule 3.10.
In the next three claims, we bound the change in Wx that can result from an event of Type B or C.
Claim 7.5. The node-weight Wx decreases by at most ∆ = β −`(x) − β −`(x)−1 due to a Type B event.
Proof. If the Type B event occurs due a natural activation of x, then the claim follows from Assumption 6.2
since β −`(x)−1 ≤ β −`(x) − β −`(x)−1 as long as β ≥ 2. For the rest of the proof, suppose that the Type B
event occurs due to an induced activation. This means that the Type B event results from some neighbour
y of x increasing the value of `y (x, y) from, say, i to (i + 1). For this to change the weight w(u, v), we
must have `x (x, y) ≤ i. Since S TATE[x] = U P -B, row (5) of Table 1 implies that Mdown (x) = 0/ and hence
`(x) ≤ `x (x, y) ≤ i. It follows that the weight Wx decreases by β −i − β −(i+1) ≤ β −`(x) − β −(`(x)+1) .
Consider an event of Type C. This event occurs when we call the subroutine FIX-DIRTY-NODE(x).
Since S TATE[x] = U P -B, this in turn leads to a call to the subroutine FIX-UP-B(x). See Figures 7 and 11.
Hence, during a Type C event, the node x un-marks one or more incident edges (x, y) ∈ Mup (x) by calling
the subroutine PIVOT-DOWN(x, (x, y)). If the un-marking of an edge (x, y) changes its weight w(x, y), then
we say that the un-marking is a success; otherwise the un-marking is a failure. Figure 7 ensures that an
event of Type C leads to at most one success.
Claim 7.6. If a Type C event leads to a success, then it increases the node-weight Wx by ∆ = β −`(x) −
β −`(x)−1 .

26

Proof. Let the success correspond to the un-marking of the edge (x, y). Just before this un-marking, we have
(x, y) ∈ Mup (x) and hence `x (x, y) = `(x) + 1. The un-marking reduces the value of `x (x, y) from `(x) + 1 to
`(x). For this to change the weight w(x, y), the value of `(x, y) must also have decreased from `(x) + 1 to `(x)
due to the un-marking. This means that the weight w(x, y) increases by an amount ∆ = β −`(x) − β −`(x)−1
due to the un-marking. Since any Type C event leads to at most one success, the weight Wx also changes by
exactly ∆ during the Type C event under consideration.
Claim 7.7. If a Type C event does not lead to a success, then it does not change the weight Wx , and β 5 edges
get deleted from the set Mup (x) due to such a Type C event.
Proof. Consider a Type C event that does not lead to a success. During this event, each time the node x
un-marks an edge (x, y), it leads to a failure and does not change the weight w(x, y). Thus, the weight Wx
also does not change due to such an event of Type C.
Suppose that the Type C event under consideration leads to zero success and less than β 5 failures. This
implies that the subroutine FIX-UP-B(x) terminates due to step (05) in Figure 11, and thus Mup (x) = 0/ at
this point in time. Next, the subroutine FIX-DIRTY-NODE(x) calls UPDATE-STATUS(x) as per step (09)
in Figure 7, which in turn changes the state of the node x since we cannot simultaneously have S TATE[x] =
U P -B and Mup (x) = 0.
/ See row (5) of Table 1. However, this leads us to a contradiction, for we have
assumed that S TATE[x] = U P -B throughout the time-interval [t0 ,t1 ].
Let nB and nC respectively denote the number of Type B and Type C events during the time-interval
[t0 ,t1 ]. Let nCs (resp. nCf ) denote the number of Type C events during the time-interval [t0 ,t1 ] that lead (resp.
do not lead) to a success. Clearly, we have: nC = nCs + nCf . By Claim 7.4, every Type B event is followed by
a Type C event. Hence, we get: nB ≤ nC = nCs + nCf , which implies that:
nCf ≥ nB − nCs

(11)

Any change in the weight Wx during the time-interval [t0 ,t1 ] results from an event of Type A, B or C. Now,
an event of Type A increases the weight Wx , an event of Type B decreases the weight Wx by at most ∆ (see
Claim 7.5), an event of Type C that leads to a success increases the weight Wx by ∆ (see Claim 7.6), and an
event of Type C that does not lead to a success leaves the value of Wx unchanged (see Claim 7.7). Since the
weight Wx decreases by at least 1/β − 1/β K during the time-interval [t0 ,t1 ] (see Corollary 7.3), we get:
(nB − nCs ) · ∆ ≥ 1/β − 1/β K

(12)

Claim 7.5 gives: 1/∆ ≥ β `(x) . By eq (5), we have 1/β − 1/β K ≥ 1/β 2 . Thus, eq (11) and (12) give:
nCf ≥ (1/∆) · (1/β − 1/β K ) ≥ β `(x)−2

(13)

By Claim 7.7, for each Type C event that contributs to nCf , the node x deletes β 5 edges from Mup (x).
Hence, eq. (13) implies that during the time-interval [t0 ,t1 ], the node x deletes nCf · β 5 ≥ β `(x)+3 edges from
Mup (x). Furthermore, the node x never inserts an edge into the set Mup (x) during the time-interval [t0 ,t1 ],
for S TATE[x] = U P -B throughout this time-interval (see Figure 11 and Section 6.1). Thus, we have:
|Mup (x)| ≥ β `(x)+3 at time-instant t0 .

(14)

Note that every edge (x, v) ∈ Mup (x) has `x (x, v) = `(x) + 1 and `v (x, v) ≤ `(x) by Invariant 3.7. Thus, the
weight of every edge (x, v) ∈ Mup (x) is given by w(x, y) = β −`(x)−1 . By equation 14, we now derive that
Wx ≥ ∑(x,v)∈Mup (x) w(x, v) ≥ |Mup (x)| · β −`(x)−1 > 1 at time-instant t0 . This leads to a contradiction, since
S TATE[x] = U P -B at time t0 and hence row(5) of Table 1 requires that Wx < 1 − 1/β .
27

7.2

Deriving a contradiction for S = U P.

Just before time t1 , the node x has S TATE[x] = U P, Mdown (x) = 0,
/ E`(x) (x) 6= 0,
/ and 1 − 1/β ≤ Wx < 1. See
row (1) of Table 1. Consider the activation of x at time t1 that results in a call to UPDATE-STATUS(x)
during which the algorithm HALTS. There are two cases to consider here.
Case 1. The activation decreases the weight Wx . Recall case 1 in the justification for Rule 3.9. This
activation does not make the node x dirty. It either remains in state U P, or switches to state U P -B if
1 − 2/β ≤ Wx < 1 − 1/β after the activation. A call to UPDATE-STATUS(x) following this activation
will never make the algorithm HALT.
Case 2. The activation increases the weight Wx . If it is a natural activation, then by Assumption 6.2
this increases the weight Wx by at most β −(`(x)+1) ≤ β −`(x) − β −(`(x)+1) . See equation 5. Otherwise, the
activation is induced, and suppose that it happens because some neighbour y of x decreases the value of
`y (x, y) from i + 1 to i (say). Then this increases the weight Wx by β −i − β −(i+1) ≤ β −`(x) − β −(`(x)+1) .
The inequality holds since we must have i ≥ `(x). We conclude that regardless of whether the activation
of x is natural or induced, it increases the weight Wx by at most β −`(x) − β −(`(x)+1) . Immediately after
this activation, the node x becomes dirty (see Rule 3.9) and calls the subroutine FIX-DIRTY-NODE(x),
which in turn, calls the subroutine FIX-UP(x). See Figures 7 and 8. During the call to the subroutine FIXUP(x), the node x up-marks some edge (x, v) ∈ E`(x) (x). This up-marking reduces the weight Wx by exactly
β −`(x) − β −(`(x)+1) . Thus, this reduction in the value of Wx is sufficient to compensate for the increase in the
value of Wx due to the preceding activation. Hence, when the subroutine UPDATE-STATUS(x) eventually
gets called after the up-marking of the edge (x, y), we have Wx < 1. During the call to UPDATE-STATUS(x),
if we find out that 1 − 2/β ≤ Wx < 1 − 1/β , then we change the state of x to U P -B. Else if we find out that
1 − 1/β ≤ Wx < 1 and E`(x) (x) = 0,
/ then the node x moves to a higher level while remaining in state U P.
Finally, if we find out that 1 − 1/β ≤ Wx < 1 and E`(x) (x) 6= 0,
/ then the node x remains in the same level and
in the same state U P. Thus, under no situation does the call to UPDATE-STATUS(x) makes our algorithm
HALT.
7.3

Deriving a contradiction for S = I DLE.

Just before time t1 , the node x has S TATE[x] = I DLE, Mup (x) = Mdown (x) = 0,
/ and 1 − 2/β ≤ Wx < 1 − 1/β .
See row (4) of Table 1. Recall case 2 in the justification for Rule 3.11. The node x does not become dirty due
to the activation at time t1 . It either remains in state I DLE, or switches to state D OWN if f (β ) ≤ Wx < 1−1/β ,
or switches to state U P if 1 − 1/β ≤ Wx < 1. A call to UPDATE-STATUS(x) following this activation will
never make the algorithm HALT.
7.4

Deriving a contradiction for S = S LACK.

Just before time t1 , the node x has S TATE[x] = S LACK, Mup (x) = Mdown (x) = 0,
/ `(y) = K, and 0 ≤ Wx < f (β ).
See row (3) of Table 1. Recall case 1 in the justification for Rule 3.11. The node x does not become dirty
due to the activation at time t1 . It either remains in state S LACK, or switches to state D OWN if f (β ) ≤ Wx <
1 − 1/β . A call to UPDATE-STATUS(x) following this activation will never make the algorithm HALT.
7.5

Deriving a contradiction for S = D OWN -B.

The only way the node x can change its level is if we execute the steps in Case 2-a or 2-b during a call to
UPDATE-STATUS(x). This situation can never occur during the time-interval [t0 ,t1 ], throughout which we
have S TATE[x] = S = D OWN -B. Thus, the node x stays at the same level throughout the time-interval [t0 ,t1 ].
In Claims 7.8 and 7.9, we respectively bound the weight Wx at time-instants t0 and t1 . In Corollary 7.10,
we use these two claims to bound the change in the weight Wx during the time-interval [t0 ,t1 ].
Claim 7.8. Wx < 1 − 2/β + 1/β K at time t0 .
28

Proof. There is an activation of the node x at time t0 which changes its state to D OWN -B. As per the
discussion in Section 3.3, the only way this can happen is if S TATE[x] = D OWN just before time t0 and the
activation at time t0 increases Wx (see Case 1 in the justification for Rule 3.10). Thus, row (2) in Table 1
gives: Wx < 1 − 2/β just before time t0 . As the weight of an edge is at most β −K , the activation of x at time
t0 changes Wx by at most β −K . Hence, Wx < 1 − 2/β + 1/β K after the activation of x at time-instant t0 .
Claim 7.9. Wx ≥ 1 − 1/β and Mdown (x) 6= 0/ at time t1 .
Proof. S TATE[x] = D OWN -B throughout the time-interval [t0 ,t1 ]. Just before time t1 , the node x undergoes
an activation, say, a*. Subsequent to the activation a*, our algorithm HALTS during a call to UPDATESTATUS(x) at time t1 . From row (6) of Table 1, we get: Mdown (x) 6= 0,
/ Mup (x) = 0/ and 1 − 2/β ≤ Wx <
1 − 1/β just before the activation a*. No edge gets inserted into the sets Mup (x) and Mdown (x) during the
activation a*. Since the algorithm HALTS at time t1 , the activation a* must have changed the weight Wx in
such a way that the node x violates the constraints for every state as defined in Table 1. This can happen
only if Wx ≥ 1 − 1/β and Mdown (x) 6= 0/ at time t1 .
Corollary 7.10. During the interval [t0 ,t1 ], the node-weight Wx increases by at least 1/β − 1/β K .
Proof. Follows from Claims 7.8 and 7.9.
Claim 7.11. An event of Type B does not make the node x dirty. An event of Type A makes the node x dirty.
Proof. Throughout the time-interval [t0 ,t1 ], we have S TATE[x] = D OWN -B. The claim follows from Rule 3.9.
In the next three claims – 7.12, 7.13 and 7.14 – we bound the change in the weight Wx that can result
from an event of Type A or C.
Claim 7.12. The node-weight Wx increases by at most ∆ = β −`(x) − β −`(x)−1 due to a Type A event.
Proof. If the Type A event occurs due a natural activation of x, then the claim follows from Assumption 6.2
since β −`(x)−1 ≤ β −`(x) − β −`(x)−1 as long as β ≥ 2 (see equation 5). For the rest of the proof, suppose that
the Type A event occurs due to an induced activation. This means that the Type A event results from some
neighbour y of x decreasing the value of `y (x, y) from, say, (i + 1) to i. Now, we consider the following cases
depending on the values of i and `x (x, y).
• Case 1. i ≥ `(x).
In this case, it follows that the weight Wx increases by β −i − β −(i+1) ≤ ∆ due to this Type A event.
• Case 2. i = `(x) − 1 and `x (x, y) ≥ `(x).
In this case, the weight w(x, y) does not change as the value of `y (x, y) drops from (i + 1) to i.
• Case 3. i = `(x) − 1 and `x (x, y) = `(x) − 1.
Recall that the value of `y (x, y) drops from (i + 1) to i due to a call to the subroutine PIVOTDOWN(y, (x, y)), which is described in Figure 5. It is easy to check that in this case the call to
PIVOT-DOWN(y, (x, y)) executes the steps (16) – (20) in Figure 5, with v = y and u = x. Hence,
because of the undo operation performed by the node x the weight w(x, y) remains unchanged, and
the call to PIVOT-DOWN(y, (x, y)) returns FALSE in step (20) in Figure 5.
• Case 4. i < `(x) − 1.
Since `x (x, y) ≥ `(x) − 1, in this case the weight w(x, y) does not change as the value of `y (x, y)
decreases from (i + 1) to i.
Since `x (x, y) ≥ `(x) − 1, the above four cases cover all possible situations. It follows that only case 1 can
happen during a Type A event, for in every other case the weight Wx does not get changed. However, note
that in case 1 the weight Wx increases by at most ∆. This concludes the proof of the lemma.
29

Consider an event of Type C. This event occurs when we call the subroutine FIX-DIRTY-NODE(x).
Since S TATE[x] = D OWN -B, this in turn leads to a call to the subroutine FIX-DOWN-B(x). See Figures 7
and 9. Hence, during a Type C event, the node x un-marks one or more incident edges (x, y) ∈ Mdown (x) by
calling the subroutine PIVOT-UP(x, (x, y)). If the un-marking of an edge (x, y) changes its weight w(x, y),
then we say that the un-marking is a success; otherwise the un-marking is a failure. Figure 9 ensures that an
event of Type C leads to at most one success.
Claim 7.13. If a Type C event leads to a success, then it decreases the node-weight Wx by β −(`(x)−1) −β −`(x) ,
which is more than ∆ as defined in Claim 7.12.
Proof. Let the success correspond to the un-marking of the edge (x, y). Just before this un-marking, we have
(x, y) ∈ Mdown (x) and hence `x (x, y) = `(x) − 1. The un-marking increases the value of `x (x, y) from `(x) − 1
to `(x). For this to change the weight w(x, y), the value of `(x, y) must also have increased from `(x) − 1 to
`(x) due to the un-marking. This means that the weight w(x, y) decreases by an amount β −(`(x)−1) − β −`(x)
due to the un-marking. Since any Type C event leads to at most one success, the weight Wx also decreases
by exactly this amount during this Type C event.
Claim 7.14. If a Type C event does not lead to a success, then it does not change the weight Wx , and β 5
edges get deleted from the set Mdown (x) due to this Type C event.
Proof. Consider a Type C event that does not lead to a success. During this event, each time the node x
un-marks an edge (x, y), it leads to a failure and does not change the weight w(x, y). Thus, the weight Wx
also does not change due to such an event of Type C.
Suppose that the Type C event under consideration leads to zero success and less than β 5 failures. This
implies that the subroutine FIX-DOWN-B(x) terminates due to step (05) in Figure 9, and thus Mdown (x) = 0/
at this point in time. Next, the subroutine FIX-DIRTY-NODE(x) calls UPDATE-STATUS(x) as per step (09)
in Figure 7, which in turn changes the state of the node x since we cannot simultaneously have S TATE[x] =
D OWN -B and Mdown (x) = 0.
/ See row (6) of Table 1. However, this leads us to a contradiction, for we have
assumed that S TATE[x] = D OWN -B throughout the time-interval [t0 ,t1 ].
Let nA and nC respectively denote the number of Type A and Type C events during the time-interval
[t0 ,t1 ]. Let nCs (resp. nCf ) denote the number of Type C events during the time-interval [t0 ,t1 ] that lead (resp.
do not lead) to a success. Clearly, we have: nC = nCs + nCf . By Claim 7.11, every Type A event is followed
by a Type C event. Hence, we infer that nA ≤ nC = nCs + nCf . Rearranging the terms, we get:
nCf ≥ nA − nCs

(15)

Any change in the weight Wx during the time-interval [t0 ,t1 ] results solely from an event of Type A, B or
C. Now, an event of Type A increases the weight Wx by at most ∆ (see Claim 7.12), an event of Type B
decreases the weight Wx , an event of Type C that leads to a success decreases the weight Wx by more than ∆
(see Claim 7.13), and an event of Type C that does not lead to a success leaves the value of Wx unchanged
(see Claim 7.14). Since the weight Wx increases by at least 1/β − 1/β K during the time-interval [t0 ,t1 ] (see
Corollary 7.10), we get:
(nA − nCs ) · ∆ ≥ 1/β − 1/β K
(16)

Claim 7.12 gives: 1/∆ ≥ β `(x) . By eq (5), we have 1/β − 1/β K ≥ 1/β 2 . Thus, eq (15) and (16) give:
nCf ≥ (1/∆) · (1/β − 1/β K ) ≥ β `(x)−2

(17)

By Claim 7.14, during each Type C event that contributes to nCf , the node x deletes β 5 edges from the set
Mdown (x). Hence, equation 17 implies that during the time-interval [t0 ,t1 ], the node x deletes nCf ·β 5 ≥ β `(x)+3
30

edges from Mdown (x). Furthermore, the node x never inserts an edge into the set Mdown (x) during the timeinterval [t0 ,t1 ], for S TATE[x] = D OWN -B throughout the time-interval [t0 ,t1 ]. Thus, we have:
|Mdown (x)| ≥ β `(x)+3 at time-instant t0 .

(18)

Note that every edge (x, v) ∈ Mdown (x) has `x (x, v) = `(x) − 1 and `v (x, v) ≤ `(x) by Invariant 3.7. Thus,
the weight of every edge (x, v) ∈ Mdown (x) is given by w(x, y) ≥ β −`(x) . By equation 18, we get: Wx ≥
∑(x,v)∈Mdown (x) w(x, v) ≥ |Mup (x)|·β −`(x) > 1 at time-instant t0 . This leads to a contradiction, since S TATE[x] =
D OWN -B at time t0 and hence row(6) of Table 1 requires that Wx < 1 − 1/β .
7.6

Deriving a contradiction for S = D OWN.

Suppose that when the node x enters state D OWN at time t0 , we have `(x) = i > K. This means that the node
was either in state D OWN -B or in state I DLE just before time t0 (see the discussion in Section 3.3). Hence,
the weight Wx is very close to 1 − 2/β at time t0 .
If an adversary wants to ensure that our algorithm HALTS at time t1 , then her best bet is to apply the
following strategy. Keep reducing the weight Wx in a series of activations, and hope that by time t1 we reach
a scenario where: Wx < f (β ) = 1 − 3/β , `(x) = j > K and there are many edges (x, y) with `y (x, y) < j.
This prevents the node x from going down to level K and switch to state S LACK. Hence, the algorithm must
HALT at this point.
For the above strategy to work out as per plan, the adversary must be able to reduces the weight Wx from
being close to 1 − 2/β at time t0 to being less than f (β ) = 1 − 3/β at time t1 . In other words, by a series of
activations the adversary must be able to reduce the weight Wx by 1/β during the time-interval [t0 ,t1 ].
Each of these activations reduce the weight Wx by at most β −(`(x)−1) − β −`(x) : this bound is achieved
when an edge (x, y) ∈ Mdown (x) has the value of `y (x, y) increased from `(x) − 1 to `(x).3 After every such
activation, we call the subroutine FIX-DIRTY-NODE(x), which in turn calls FIX-DOWN(x). The call to
FIX-DOWN(x) consists of a series of down-markings of edges (x, y) ∈ E`(x) (x) \ Mdown (x) by the node
x. If a down-marking results in the weight Wx getting increased, then we say that the down-marking is a
success, else we say that the down-marking is a failure. Each call to FIX-DOWN(x) results in either one
success or β 5 L failures. In case of a success, the weight Wx increases by β −(`(x)−1) − β `(x) , for the level
of the edge being down-marked by x changes from `(x) to `(x) − 1. Note that in case of a success, the
amount by which Wx increases is sufficient to compensate for the decrease in Wx that lead to the call to
FIX-DOWN(x). To summarise, the adversary ensures that each activation of x reduces the weight Wx by
at most β −(`(x)−1) − β −`(x) . This is followed by a call to FIX-DOWN(x), which either brings the weight
Wx back to its initial value, or results in β 5 L failures. In other words, each time the weight Wx decreases
by β −(`(x)−1) − β −`(x) ≤ β −(`(x)−1) , the node x down-marks β 5 L many new edges from E`(x) (x) \ Mdown (x).
Initially, the node x cannot have more than β −`(x) many edges in E`(x) (x), for each such edge has weight
β −`(x) and the node-weight Wx clearly cannot exceed one. Thus, after β `(x) /(β 5 L) many such events, each
of which reduces the weight Wx by at most β −(`(x)−1) , we would have E`(x) (x) \ Mdown (x) = 0.
/ At that point
the node x will move down one level below. During this interval, the weight Wx would drop by at most
(β `(x) /(β 5 L)) · β −(`(x)−1) ≤ 1/(β 4 L).
Thus, we infer that each time the weight Wx drops by 1/(β 4 L), the level of x drops by one. Accordingly,
much before the weight Wx drops from 1 − 2/β to below f (β ) = 1 − 3/β , the node x would reach level K.
This leads to a contradiction.
3 This always results from an induced activation. By Assumption 6.2, a natural activation reduces the weight W by at most
x
β −(`(x)+1) ≤ β −(`(x)−1) − β −`(x) .

31

8

Proof of Theorem 6.4

We first introduce the concept of the down-level `∗ (x) of a node x ∈ V . This is defined below.
(
`(x) − 1 if Mdown (x) 6= 0;
/
∗
` (x) =
`(x)
otherwise.

(19)

Recall that if `(x) = K, then Mdown (x) = 0.
/ 4 Hence, we get: `∗ (x) ∈ [K, L] for every node x ∈ V . We will
prove the following lemma.
Lemma 8.1. After two consecutive iterations of the W HILE loop in Figure 12, the value of `∗ (x) decreases
by at least one.
Since there are (L − K + 1) possible values for `∗ (x), Lemma 8.1 implies that the W HILE loop in Figure 12 runs for at most 2(L − K + 1) = O(log n) iterations. By Lemma 5.2, each iteration of the W HILE loop
in Figure 12 takes O(log2 n). This gives a total worst-case update time of O(log3 n) for handling one edge
insertion or deletion in the input graph. We devote the rest of this section to the proof of Lemma 8.1.
Consider three consecutive iterations of the W HILE loop in Figure 12. For i ∈ {1, 2, 3}, let xi be the node
considered in the ith iteration. Furthermore, for i ∈ {1, 2, 3}, let `∗i be the value of `∗ (xi ) just before the call
to the subroutine FIX-DIRTY-NODE(xi ) in the ith iteration. We will show that `∗1 > `∗3 . As per Figure 7,
we must have S TATE[x1 ] ∈ {U P, D OWN -B, U P -B, D OWN} just before the 1st iteration of the W HILE loop in
Figure 12. In order to prove Lemma 8.1, we consider two mutually exclusive and exhaustive cases.
Case 1.

S TATE[x1 ] ∈ {U P, D OWN -B} just before the 1st iteration of the W HILE loop in Figure 12.

In this case, Lemma 8.2 implies that `∗1 ≥ `∗2 and S TATE[x2 ] ∈ {D OWN, U P -B} just before the 2nd iteration
of the W HILE loop in Figure 12. Now, applying Lemma 8.3, we get: `∗1 ≥ `∗2 > `∗3 .
Case 2.

S TATE[x1 ] ∈ {D OWN, U P -B} just before the 1st iteration of the W HILE loop in Figure 12.

In this case, Lemma 8.3 implies that `∗1 > `∗2 just before the 2nd iteration of the W HILE loop in Figure 12.
Now, applying Corollary 8.4, we again get: `∗1 > `∗2 ≥ `∗3 .
Lemma 8.2. Consider a call to FIX-DIRTY-NODE(v), and suppose that S TATE[v] ∈ {U P, D OWN -B} and
`∗ (v) = i just before the call. If a neighbour u of v becomes dirty because of this call, then `∗ (u) ≤ i and
S TATE[u] ∈ {U P -B, D OWN} at the termination of the subroutine FIX-DIRTY-NODE(v).
The proof of Lemma 8.2 appears in Section 8.1.
Lemma 8.3. Consider a call to FIX-DIRTY-NODE(v), and suppose that S TATE[v] ∈ {D OWN, U P -B} and
`∗ (v) = i just before the call. If a neighbour u of v becomes dirty because of this call, then `∗ (u) < i at the
termination of the subroutine FIX-DIRTY-NODE(v).
The proof of Lemma 8.3 appears in Section 8.2.
Corollary 8.4. Consider a call to FIX-DIRTY-NODE(v), and suppose that `∗ (v) = i just before the call. If
a neighbour u of v becomes dirty because of this call, then `∗ (u) ≤ i at the termination of the subroutine
FIX-DIRTY-NODE(v).
Proof. Since we have called FIX-DIRTY-NODE(v), we must have S TATE[v] ∈ {U P, D OWN -B, U P, D OWN}
as per Figure 7. The corollary now follows from Lemmas 8.2 and 8.3.
4 This

holds since every edge (x, y) ∈ Mdown (x) has `x (x, y) = `(x) − 1, and since `x (x, y) ∈ [K, L].

32

8.1

Proof of Lemma 8.2.

See Figures 8 and 9. Since S TATE[v] ∈ {U P, D OWN -B}, a neighbour u of v can become dirty only if we call
PIVOT-UP(v, (u, v)) during the execution of FIX-DIRTY-NODE(v). Recall that `∗ (v) = i, and consider two
possible cases.
Case 1. S TATE[v] = U P. In this case, we have Mdown (v) = 0/ as per row (1) of Table 1. So equation 19
implies that `(v) = i. In the call to PIVOT-UP(v, (u, v)), the node v up-marks the edge (u, v) by increasing the
value of `v (u, v) from i to (i + 1). By Claim 8.5, the node u becomes dirty only if `∗ (u) ≤ i and S TATE[u] ∈
{D OWN, U P -B}.

Case 2. S TATE[v] = D OWN -B. In this case, we have Mdown (v) 6= 0/ as per row (6) of Table 1. So equation 19
implies that `(u) = i+1. In the call to PIVOT-UP(v, (u, v)), the node v un-marks the edge (u, v) by increasing
the value of `v (u, v) from i to (i+1). By Claim 8.5, the node u becomes dirty only if `∗ (u) ≤ i and S TATE[u] ∈
{D OWN, U P -B}.
Lemma 8.2 follows as we terminate the subroutine FIX-DIRTY-NODE(v) just after u becomes dirty.
Claim 8.5. Consider a call to the subroutine PIVOT-UP(v, (u, v)) as in Figure 3. Suppose that `v (u, v)
increase from j to ( j +1) during step (01). If u becomes dirty during this call, then `∗ (u) ≤ j and S TATE[u] ∈
{U P -B, D OWN} at the end of the subroutine.
Proof. Suppose that the node u becomes dirty during the execution of the subroutine PIVOT-UP(v, (u, v)).
This can happen only due to the execution of step (03) in Figure 3. Thus, step (02) in Figure 3 ensures
that Y = T RUE and {either S TATE[u] = U P -B or (S TATE[u] = D OWN and `(u) > K)}. It follows that the
weight w(u, v) and the level `(u, v) change during the execution of step (01), which increases `v (u, v) from
j to ( j + 1). Hence, we must have `u (u, v) ≤ j just before step (01). Since `(u) ≤ `u (u, v) + 1, we also infer
that `(u) ≤ j + 1 just before step (01). We consider two cases, depending on the values of `(u) and `u (u, v).
Case 1. `(u) ≤ j just before step (01). The value of `(u) does not change during the execution of PIVOTUP(v, (u, v)). Hence, even at the end of the subroutine, we have `∗ (u) ≤ `(u) ≤ j.
Case 2. `(u) = j + 1 and `u (u, v) = j just before step (01). In this case, the increase in the value of `v (u, v)
from j to ( j + 1) during step (01) does not lead to any change in the value of `u (u, v). In other words, since
`(u) remains larger than or equal to `v (u, v) even after the increase in the value of `v (u, v), steps (08) – (09)
in Figure 4 do not get executed. Hence, even after step (01) in Figure 3, we continue to have `(u) = j + 1 and
`u (u, v) = j. In fact, we continue to have `(u) = j + 1 and `u (u, v) = j till the end of the subroutine. At that
point in time, we conclude that Mdown (u) 6= 0/ since (u, v) ∈ Mdown (u), and hence `∗ (u) = `(u) − 1 = j.

8.2

Proof of Lemma 8.3.

See Figures 10 and 11. Since S TATE[v] ∈ {D OWN, U P -B}, a neighbour u of v can become dirty only if
we call PIVOT-DOWN(v, (u, v)) during the execution of the subroutine FIX-DIRTY-NODE(v). Recall that
`∗ (v) = i. We now consider two possible cases.
Case 1. S TATE[v] = D OWN. In this case, equation 19 implies that `(v) ∈ {i, i + 1}. In the call to PIVOTDOWN(v, (u, v)), the node v down-marks the edge (u, v). Let j be the new value of `v (u, v) after this
down-marking, i.e., the value of `v (u, v) drops from ( j + 1) to j. Then we clearly have: j ≤ i. By Claim 8.6,
u becomes dirty only if `∗ (u) < j ≤ i.

Case 2. S TATE[v] = U P -B. In this case, we have Mdown (v) = 0/ as per row (5) of Table 1. Hence, equation 19 implies that `(v) = i. In the call to PIVOT-DOWN(v, (u, v)), the node v un-marks the edge (u, v) by
decreasing the value of `v (u, v) from (i + 1) to i. By Claim 8.6, u becomes dirty only if `∗ (u) < i.
Lemma 8.3 follows as we terminate the subroutine FIX-DIRTY-NODE(v) just after u becomes dirty.
33

Claim 8.6. Consider a call to the subroutine PIVOT-DOWN(v, (u, v)) as in Figure 5, and let step (01)
decrease `v (u, v) from ( j + 1) to j. If u becomes dirty due to this call, then `∗ (u) < j at the end of the
subroutine.
Proof. Suppose that the node u becomes dirty during the call to the subroutine PIVOT-DOWN(v, (u, v)).
Depending on the state of the node u in the beginning of Figure 5, we consider three possible cases.
Case 1. S TATE[u] = U P.
Here, the node u can become dirty only due to the execution of step (09) in Figure 5. For the rest of this
paragraph, we assume that step (09) gets executed. Thus, in step (03) we get Y = T RUE, and this ensures
that the call to MOVE-DOWN(v, (u, v)) in step (01) changes the weight of the edge (u, v). Recall that during
step (01) the value of `v (u, v) changes from ( j + 1) to j. For this event to change the weight w(u, v), we get:
`u (u, v) ≤ j just before step (01). Since S TATE[u] = U P, we must have `(u) ≤ `u (u, v) ≤ j at the same point
in time. Now, there are two possibilities. Either `(u) = j or `(u) < j just before step (01).
1. Suppose that `(u) = j just before step (01). Since `(u) ≤ `u (u, v) ≤ j at the same point in time, we
infer that `(u) = `u (u, v) = j = `v (u, v) just after step (01). This, in turn, implies that (u, v) ∈
/ Mup (u)
and `(u) ≥ `v (u, v) just after step (01). It follows that due to step (04) we would never execute step
(09). This leads to a contradiction. Hence, it cannot be the case that `(u) = j.
2. The only remaining possibility is that `(u) < j. In this case, we have `∗ (u) ≤ `(u) < j.
To summarise, if S TATE[u] = U P, then u becomes dirty only if `∗ (u) < j at the end of the subroutine.
Case 2. S TATE[u] = D OWN -B.
Here, the node u can become dirty only due to the execution of step (22) in Figure 5. For the rest of this
paragraph, we assume that step (22) gets executed. Thus, in step (16) we get Y = T RUE, and this ensures
that the call to MOVE-DOWN(v, (u, v)) in step (01) changes the weight of the edge (u, v). Recall that step
(01) changes the value of `v (u, v) from ( j + 1) to j. For this event to change the weight of the edge (u, v),
we must have `u (u, v) ≤ j just before step (01). Since `(u) ≤ `u (u, v) + 1, we infer that `(u) ≤ j + 1 and
`u (u, v) ≤ j just before step (01). Accordingly, we consider the following possibilities.
1. `(u) = j + 1 and `u (u, v) = j. In this case, we have (u, v) ∈ Mdown (u) and `v (u, v) = j < `(u) during
step (17). Hence, step (22) never gets executed, and we reach a contradiction.
2. `(u) = j. In this case, since S TATE[u] = D OWN -B, we must have `∗ (u) = `(u) − 1 < j.
3. `(u) < j. In this case, we have `∗ (u) ≤ `(u) < j.
To summarise, if S TATE[u] = D OWN -B, then u becomes dirty only if `∗ (u) < j at the end of the subroutine.
Case 3. S TATE[u] ∈ {U P -B, D OWN, I DLE, S LACK}.
Here, steps (28)-(30) ensure that u never becomes dirty.

References
[1] A. Abboud and V. V. Williams. Popular conjectures imply strong lower bounds for dynamic problems.
In FOCS 2014. 1
[2] S. Baswana, M. Gupta, and S. Sen. Fully dynamic maximal matching in O(log n) update time. In
FOCS 2011. 1
[3] A. Bernstein and C. Stein. Faster fully dynamic matchings with small approximation ratios. In SODA
2016. 1
[4] A. Bernstein and C. Stein. Fully dynamic matching in bipartite graphs. In ICALP 2015. 1
[5] S. Bhattacharya, M. Henzinger, and G. F. Italiano. Design of dynamic algorithms via primal-dual
method. In ICALP 2015. 1
34

[6] S. Bhattacharya, M. Henzinger, and G. F. Italiano. Deterministic fully dynamic data structures for
vertex cover and matching. In SODA 2015. 1, 2, 3
[7] S. Bhattacharya, M. Henzinger, and D. Nanongkai. New deterministic approximation algorithms for
fully dynamic matching. In STOC 2016. 1
[8] C. Demetrescu and G. F. Italiano. A new approach to dynamic all pairs shortest paths. In STOC 2003.
1
[9] G. N. Frederickson. Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees. In FOCS 1991.
[10] G. N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications.
In STOC 1983. 1
[11] M. Gupta and R. Peng. Fully dynamic (1 + ε)-approximate matchings. In FOCS 2013. 1
[12] M. He, G. Tang, and N. Zeh. Orienting dynamic graphs, with applications to maximal matchings and
adjacency queries. In ISAAC 2014. 1
[13] M. Henzinger and V. King. Randomized fully dynamic graph algorithms with polylogarithmic time
per operation. J. ACM, 46(4):502–516, 1999. 1
[14] M. Henzinger, S. Krinninger, D. Nanongkai, and T. Saranurak. Unifying and strengthening hardness
for dynamic problems via the online matrix-vector multiplication conjecture. STOC, pages 21–30,
2015. 1
[15] J. Holm, K. de Lichtenberg, and M. Thorup. Poly-logarithmic deterministic fully-dynamic algorithms
for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4), 2001. 1
[16] B. M. Kapron, V. King, and B. Mountjoy. Dynamic graph connectivity in polylogarithmic worst case
time. In SODA 2013. 1
[17] T. Kopelowitz, R. Krauthgamer, E. Porat, and S. Solomon. Orienting fully dynamic graphs with worstcase time bounds. In ICALP 2014. 1
[18] T. Kopelowitz, S. Pettie, and E. Porat. Higher lower bounds from the 3SUM conjecture. In SODA,
2016. to appear. 1
[19] O. Neiman and S. Solomon. Simple deterministic algorithms for fully dynamic maximal matching. In
STOC 2013. 1
[20] K. Onak and R. Rubinfeld. Maintaining a large matching and a small vertex cover. In STOC 2010. 1
[21] P. Sankowski. Faster dynamic matchings and vertex connectivity. In SODA 2007. 1
[22] S. Solomon. Fully dynamic maximal matching in constant update time. In FOCS 2016. 1
[23] M. Thorup. Worst-case update times for fully-dynamic all-pairs shortest paths. In STOC 2005. 1
[24] C. Wulff-Nilsen. Faster deterministic fully-dynamic graph connectivity. In SODA 2013. 1

35

