Algorithm 2:st-connectivity
Algorithm 2: st-connectivity
st-Connectivity Problem:Given a graph G and two vertices s and t on it,decide whether they are connected. o BFS/DFS(starting at s)solves the problem in linear time. But uses linear space as well. Question:Can we use much less space?
st-Connectivity ◼ Problem: Given a graph G and two vertices s and t on it, decide whether they are connected. ◼ BFS/DFS (starting at s) solves the problem in linear time. ◼ But uses linear space as well. ◼ Question: Can we use much less space?
Simple random walk algorithm A randomized algorithm takes O(log n)space. 0 Starting at s,perform the random walk for O(n3) steps.If ever see t,output YES and stop. aoutput NO. Why it works?H(s,t)=O(n3). If s can reach t,then we should see it within O(n3) time
Simple random walk algorithm ◼ A randomized algorithm takes O(log n) space. ❑ Starting at s, perform the random walk for O(n3 ) steps. If ever see t, output YES and stop. ❑ output NO. ◼ Why it works? H(s,t) = O(n3 ). ❑ If s can reach t, then we should see it within O(n3 ) time
Key parameter 2:Mixing time
Key parameter 2: Mixing time
Convergence Now let's study the probability distribution of the particle after a long time. What do we observe? W The distribution converges to t 0 1 0 1/2 0 1/2 uniform... 1 2 1/4 214 1/4 o wherever it starts. 3 3/8 2/8 3/8 4 5/16 6/16 5/16 5 11/32 10/32 11/32 O:Does this hold in general? 6 21/64 22/64 21/64
Convergence ◼ Now let’s study the probability distribution of the particle after a long time. ◼ What do we observe? ❑ The distribution converges to uniform… ❑ wherever it starts. ◼ Q: Does this hold in general? u v w t 0 1 0 1 1/2 0 1/2 2 1/4 2/4 1/4 3 3/8 2/8 3/8 4 5/16 6/16 5/16 5 11/32 10/32 11/32 6 21/64 22/64 21/64