Lemma 1: Consider any graph $G\in \text{allowed}(\mathcal{G}_{\text{conn}})$ and any non-empty set $S$ of potential edges to be added to $G$ and smoothing value $k\leq n/16$ with $k|S| \leq n^2/2$. Then with probability at least $c_1 k |S|/n^2$, the $k$-smoothed graph $G'$ of $G$ contains at least one edge from $S$, for some constant $c_1 > 0$.
So what is this lemma saying? Suppose that we select the set of edges $S$ to be a set of helpful edges, i.e. having them would help our algorithms terminate faster. Then this lemma claims that it is fairly probable for $G'$ to include at least one of these helpful edges.
proof sketch. We first note that $k$-smoothing $G$ is the same as replacing it with a graph $G'$ sampled uniformly from $\text{editdist}(G, k) \cap \text{allowed}(\mathcal{G}_{\text{conn}})$.
If we denote $B$ as the event where $G'$ is connected and $A$ as the event where $G'$ contains at least one edge from $S$, then we are looking for $\mathbb{P}(A|B)$. So we want to lower bound this probability. We can do this using the following inequality $\mathbb{P}(A|B) \geq \mathbb{P}(A \cap B)$.
We split the proof into two cases. Either $G$ contains an edge $e\in S$ or it does not.
Case 1: $G$ contains an edge $e\in S$.
We want to find the probability that $e$ remains in $G'$, but also we need $G'$ to be connected. Thus consider "any old" spanning tree of $G$, call it $T$. We denote the event that $G'$ contains $T\cup \{e\}$ as $C$. If $C$ occurs then $G'$ is connected and includes an edge from $S$. Hence $\mathbb{P}(A \cap B) \geq \mathbb{P}(C)$. Our new aim is then to lower bound $\mathbb{P}(C)$.
Consider the process of $k$-smoothing $G$. It is essentially the same as choosing up to $k$ distinct edges from the ${n \choose 2}$ possible edges to toggle. When toggling the first of the $k$ edges we have an $n/{n \choose 2}$ chance of toggling an edge in $T\cup \{e\}$. For the second toggle we have at most $n/({n \choose 2}-1)$ probability of toggling an edge in $T\cup \{e\}$. So taking a union bound over the events that the $i^{\text{th}}$ edge toggled is part of $T\cup \{e\}$ we have at most $\sum_{i=0}^{k-1}{n/({n \choose 2}-i)}$ probability of toggling at least one edge in $T\cup \{e\}$.
Obs 1: $\sum_{i=0}^{k-1}{n/({n \choose 2}-i)} \leq 2kn/{n \choose 2}$ for $k \leq {n \choose 2}/2$.
Hence we have $\mathbb{P}(\text{not } C) \leq 2kn/{n \choose 2}$. Thus $\mathbb{P}(C) \geq 1-2kn/{n \choose 2} \geq 1/2$ for $k\leq n/16$.
Case 2: $G$ does not contain an edge $e\in S$.
As before, let $T$ be any spanning tree of $G$ and let $D$ denote the event that $G'$ contains $T$. Now $\mathbb{P}(A \cap B) \geq \mathbb{P}(A\cap D)=\mathbb{P}(A|D)\mathbb{P}(D)$. Observe that $\mathbb{P}(D) \geq \mathbb{P}(C) \geq 1/2$ since the scenario where $G'$ contains $T$ includes the scenario where $G'$ contains $T\cup \{e\}$. Hence $\mathbb{P}(A\cap D)\geq\mathbb{P}(A|D)/2$. Finally, we notice that if we are given that $D$ occured then we have ${n \choose 2}-(n-1)$ edges to choose $e$ from, whereas if we are not given $D$, then we have ${n \choose 2}$ edges to choose $e$ from. Thus $\mathbb{P}(A|D)\geq\mathbb{P}(A)$, and so we have the inequality chain
$$\mathbb{P}(A \cap B) \geq \mathbb{P}(A\cap D)\geq\mathbb{P}(A|D)/2\geq \mathbb{P}(A)/2$$
So our new aim to lower bound $\mathbb{P}(A)$. When $k$-smoothing $G$, we toggle up to $k$ of the possible ${n \choose 2}$ edges of $G$. If we end up toggling $i$ edges we have
$$\mathbb{P}(\text{not }A | \text{ toggle }i \text{ edges})=\left(1-\frac{|S|}{{n \choose 2}}\right)\left(1-\frac{|S|}{{n \choose 2}-1}\right)...\left(1-\frac{|S|}{{n \choose 2}-(i-1)}\right)\leq \left(1-\frac{|S|}{{n \choose 2}}\right)^i$$
If we knew $\mathbb{P}(\text{toggle } i \text{ edges})$, then we could use the following to finish the proof
$$\mathbb{P}(A)\geq\mathbb{P}(A\cap \text{toggle } i \text{ edges})=(1-\mathbb{P}(\text{not }A | \text{ toggle }i \text{ edges}))\mathbb{P}(\text{toggle } i \text{ edges})$$
By $k$-smoothing $G$, we have $\sum_{i=0}^{k}{{{n \choose 2}\choose i}}$ possible $k$-smoothed graphs $G'$ we could get. Observe that for $k\leq {n\choose 2}/2$ the terms in this summation are increasing. Thus we have that
$$2\sum_{i=\lceil{k/2\rceil}}^{k}{{{n \choose 2}\choose i}}\geq \sum_{i=0}^{k}{{{n \choose 2}\choose i}}$$
This means that at least half the possible graphs $G'$ have $k/2\leq i\leq k$ toggles. Hence $\mathbb{P}(\text{toggle } \geq k/2 \text{ edges})\geq 1/2$. Hence if we toggle at least $k/2$ edges, we have
$$\mathbb{P}(\text{not }A | \text{ toggle } \geq k/2 \text{ edges})\leq \left(1-\frac{|S|}{{n \choose 2}}\right)^{k/2}\leq 1-\frac{(k/4)|S|}{{n \choose 2}}$$
and so
$$\mathbb{P}(A | \text{ toggle } \geq k/2 \text{ edges}) \geq \frac{(k/4)|S|}{{n \choose 2}}$$
Then
$$\mathbb{P}(A)\geq\mathbb{P}(A \cap (\text{ toggle } \geq k/2 \text{ edges})\geq (1/8)k|S|/{n \choose 2} \geq (1/8)k|S|/n^2$$
which concludes the proof.
Below is a similar lemma to lemma 1, which states that it is unlikely that a helpful edge $e\in S$ will be removed from $G$ during $k$-smoothing.
Lemma 2: There exists constant $c_2 > 0$ such that the following holds. Consider any graph $G = (V, E)\in\text{allowed}(\mathcal{G}_{\text{conn}})$. Consider also any nonempty set $S \subseteq E$ of edges in the graph and
smoothing value $k \leq n/16$. Then with probability at most $c_2k|S| /n^2$, the $k$-smoothed graph $G′$ removes an edge from $S$.
Finally, we have a final lemma which will be useful when arguing for $k$-smoothed lower bounds.
Lemma 3: There exists constant $c_3 > 0$ such that the following holds. Consider any graph $G = (V, E)\in\text{allowed}(\mathcal{G}_{\text{conn}})$. Consider also any set $S$ of edges and smoothing value $k \leq n/16$ such
that $S \cap E = \emptyset$. Then with probability at most $c_3k|S|/n^2$ , the $k$-smoothed graph $G'$ of $G$ contains
an edge from $S$.
Lemma 1 says that with probability at least $c_1 k |S|/n^2$, $G'$ will contain some edge from $S$, and lemma 3 just says that with probability at most $c_3k |S|/n^2$, $G'$ will contain some edge from $S$. So lemma 1 intuitively implies that it is likely a helpful edge will be added during smoothing, but lemma 3 says that it is not too likely.
[Din+15] Michael Dinitz et al. “Smoothed Analysis of Dynamic Networks”.
In: Proceedings of the 29th International Symposium on Distributed
Computing - Volume 9363. DISC 2015. Tokyo, Japan: Springer-
Verlag, 2015, pp. 513–527. isbn: 9783662486528. doi: 10.1007/
978- 3- 662- 48653- 5_34. url: https://doi.org/10.1007/978-3-662-48653-5_34.
No comments:
Post a Comment