Approximate Distance Oracles Algorithm for Min-cut
Explore the Approximate Distance Oracles Algorithm for finding min-cuts in graphs efficiently. Learn about all-pairs shortest paths, data structures, and solving the All-Pairs Approximate Shortest Paths Problem. Discover a truly magical result in algorithm design.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Randomized Algorithms CS648 Lecture 18 Approximate Distance Oracles Algorithm for Min-cut : part 1 1
All-Pairs Shortest Paths Notations and Terminologies : A graph ? = (?,?)on ? = |?| vertices ? = |?| edges ?:? ?+ A path from ? to ?: a sequence (? =)??, ??, ,??(= ?)where (??,??+?) ? Length of a path ? : sum of the weights on the edges of path ?. Shortest path from ? to ?: the path of smallest length from ? to ?. Distance from ? to ?: the length of the shortest path from ? to ?. ?(?,?): Distance from ? to ? 3
All-Pairs Shortest Paths Problem Definition: Given a graph ? = (?,?), build a compact data structure so that for any ?,? ?, ?(?,?)can be reported in ?(?) time Shortest path from ? to ? can be reported in optimal time. Results known: ?(??)size data structure (Distance matrix and Witness matrix) ?(?? + ????? ?)preprocessing time (Dijkstra s algorithm from each vertex) Current-state-of-the-art RAM size: 8 GBs Can t handle graphs with even ???vertices (with RAM size) 4
All-Pairs Approximate Shortest Paths Problem Definition: Given a graph ? = (?,?), build a compact data structure so that for any ?,? ?, it reports ?(?,?)in ?(?) time satisfying ? ?,? ?(?,?) ? ?(?,?) ?: stretch. Aim: To achieve Sub-quadratic space. Sub-cubic preprocessing time. With ?(?) query time. Many elegant results have been invented for undirected graphs 5
A truly magical result Approximate Distance Oracles ?:Stretch Space Query time Preprocessing time ?(??+? ? ?) ? ?) ? ?(?) ?) ?(?? ?(??+? ?(??+? ?(?) ?(?? ? ?) ? ?) ?? ? ?(?) ?) ?(? ?? Mikkel Thorup and Uri Zwick: Approximate Distance Oracles for graphs, Journal of ACM (4), 2005 6
INSPIRATION FROM OUR DAILY LIFE 7
Air/Road Network ??????? ????? ?????? ????????? 8
The Idea Given a graph ? = (?,?), Compute a small set ? of Landmark vertices. From each vertex ? ?\?, store distance to vertices present in its locality. From each vertex ? ?, store distance to all vertices in the graph. Questions: What is the formal notion of locality ? How to retrieve distance from? to a far away vertex ? What is the guarantee of stretch ? How to compute the desired set ? efficiently ? 9
Formal notion of locality ????(?,?,?)= {? ?| ? ?,? < ? ?,?(?) } ?(?) ? ????(?,?,?) 11
Reporting distance from ? ? ?,?(?) ? ?,? Report ? ?,?(?) + ? ?(?),? ? ? ?(?) ? ????(?,?,?) 12
stretch ? What is the stretch ? ? ?,?(?) ? ?,? ?? ? ?,? + ? ?,?(?) ?? ?,? ? ?(?) ? ????(?,?,?) 13
3-approximate distance oracle Preprocessing-algorithm(?) { Compute set ? suitably; For each ? ? store distance to all vertices; For each ? ?\? compute ????(?,?,?); Build a hash table storing distances from ? to ????(?,?,?); } Global distance info. Local distance info. Query(?,?) { If ? ????(?,?,?) return ? ?,? ; else return ? ?,?(?) + ? ?(?),? ; } 14
The real challenge left How to compute set ? such that ? is small. ????(?,?,?) is small for each ? ?\?. Fact1: It is difficult, if not impossible, to compute such a set deterministically. Fact2: The structure of graph (the edges and weights) can be arbitrary and more complex than planar road/air networkk. 15
The real challenge left ?(?) ? ????(?,?,?) 16
Conquering the challenge Let ? > ? be a fraction to be fixed later on. Computing? : { ? ; For each ? ? Add ? to ? independently with probability ?; return ?; } Expected size of ? : ? ?? ?: random variable for |????(?,?,?)| 17
Expected size of ????(?,?,?) ????(?,?,?) ? ?? ?? ?? ?? ? Increasing order of distance from ? ??= ? if ?? is present in ????(?,?,?) ? otherwise None of ??, ,?? is present in ? ? = ? ?<??? ?[?] = ? ?<??[??] = ? ?<??(??= ?) = ? ?<??(?? is present in ????(?,?,?)) = ? ?<?? ??+? <? ? ? =? ? ? 18
Expected space of 3-approximate distance oracle Space for Global distance information: = ? ?|?| = ? ? ?? = ? ??? Space for Local distance information: ? ? = ? ?\? Each vertex in ?\? keeps a Ball) ? ? =? To minimize the total space: (Balance the two terms) ? ? = ? Expected space: ?(??+? ?) 19
Theorem: An undirected weighted graph can be processed to build a data structure of expected size ?(??+? between any pair of vertices in ? ?time. ?) that can report 3-approximate distance Homework: Convert to a Las Vegas algorithm with high probability bound on space. Show that expected preprocessing time is ? ? ? + ?? 20
5-APPROXIMATE DISTANCE ORACLE Meant for only those (hopefully nonzero no. of) students whose aim is more than just a good grade in this course. 21
5-approximate distance oracle ?? ?? ? 23
5-approximate distance oracle ??(?) ??(?) ? ????(?,?,??) ????(?,??,??) 24
PROBLEM 2 MIN-CUT 25
Min-Cut ? = (?,?) : undirected connected graph Definition (cut): A subset ? ? whose removal disconnects the graph. Definition (min-cut): A cut of smallest size. Problem Definition: Design algorithm to compute min-cut of a given graph. 26
Min-Cut Deterministic Algorithms: ? ?? ??????? ?time - Designed in 1997, - Quite complex to analyze and implement Randomized Algorithms: ?(?? ??????? ?)time Monte Carlo [1993] ?(? ??????? ?)time Monte Carlo [1996] - Both are much simpler and easier to implement. 27
Min-Cut Question: How many cuts ? Answer: ?? ? ? Question : what is relation between degree(?) and size of min-cut ? Answer: size of min-cut degree(?) Question : If size of min-cut is ?, what can be minimum value of ? ? Answer:?? ? 29
Contract(?,?) ? ? ? ? ? ? ? ? ? Contract(?,(?,?)) ? ? ? ? ?? ? ? ? 30
Contract(?,?) Contract(?,?) { Let ? = (?,?); Merge the two vertices ? and ? into one vertex; Preserve multi-edges; Remove the edge ?,? ; Let ? be the modified graph; return ? ; } Time complexity of Contract(?,?): ?(?) 31
Contract(?,?) Let ? be the size of min-cut of ?. Let ? be any min-cut of ?. Let ? be the graph after Contract(?,?). Observation: Every cut of ? is also a cut of ?. Question: Under what circumstance ?is a cut of ? ? Answer: if ? ?. Question: If ?is selected randomly uniformly, what is the probability that ?is preserved in ? ? ? Answer: ? ? ??/? ? ? 32
Contract(?,?) Let ? be the size of min-cut of ?. Let ? be any min-cut of ?. Lemma: If edge ?to be contracted is selected randomly uniformly, ?is preserved with probability at least 1 ? ?. Let ? ??; ? Contract(?,?). Let ? ?? ; ? Contract(? ,?). Question: What is probability that ? is preserved in ? ? Answer: 1 ? ?. 1 ? ? ? 33
Algorithm for min-cut Min-cut(?): { Repeat { } return the edges of multi-graph ?; } ?? times ? ? Let ? ??; ? Contract(?,?). Running time: ?(??) 34
Algorithm for min-cut Question: What is probability that ? is preserved during the algorithm ? Answer: 1 ? ?. 1 ? ? ? 3 ? 5.2 4.1 ? ?. 1 3 ? ? ? ? ? ? ?. ? ? ? ? 3 5.2 4.1 . = 3 = ? ? ?. ? ? >? ?? 35
Algorithm for min-cut Min-cut-high-probability(?): { Repeat Min-cut(?) algorithm ???log? and report the smallest cut computed; } Running time: ?(?? ??? ?) times ?????? ? ? ?? Error Probability : ? < ? ?? 36
