CS369: Advanced Graph Algorithms

Instructor: Tim Roughgarden (Office hours: Thursdays 1-2 PM in Gates 462)

Teaching Assistant: Shaddin Dughmi (Office hours: Tue 1:15-2:15 PM and Wed 11-Noon in Gates 460; Email: shaddin "at" cs)

Time/location: 2:15-3:30 PM on Tuesdays and Thursdays in Gates B12.

Course description: Fast algorithms for fundamental graph optimization problems, including maximum flow, minimum cuts, minimum spanning trees, nonbipartite matching, planar separators and applications, and shortest paths. Data structures including Fibonacci heaps, splay trees, and dynamic trees. Tools from linear programming, matroid theory, minmax theorems, polytope theory, and random sampling. Pre- or corequisite: CS261 or equivalent.

Course requirements: 4 problem sets and a take-home final. Students taking the course for credit should attempt 4 of 5 problems on each. Students taking the course pass/fail should attempt 2 of 5 problems on each. No late assignments accepted.

• Problem Set #1 (Out Thu 1/10, due in class Thu 1/24.)
• Problem Set #2 (Out Thu 1/24, due in class Thu 2/7.)
• Problem Set #3 (Out Thu 2/7, due in class Thu 2/21.)
• Problem Set #4 (Out Thu 2/21, due in class Thu 3/6.)
• Take-Home Final (Out Thu 3/6, due by 10 PM on Thu 3/20.)

General references: The following are on two-hour reserve at the Math-CS library.

• Cook/Cunningham/Pulleyblank/Schrijver, Combinatorial Optimization.
• Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms.
• Korte/Vygen, Combinatorial Optimization.
• Kozen, Design and Analysis of Algorithms.
• Papadimitriou/Steiglitz, Combinatorial Optimization.
• Schrijver, Combinatorial Optimization: Polyhedra and Efficiency.
• Tarjan, Data Structures and Network Algorithms.

• Tue 1/8: Review of Prim's MST Algorithm. Binomial heaps. Textbook references:
  • Kozen Chapter 8; CLRS Chapter 19.
  Historical references:
  • Graham/Hell, On the History of the Minimum Spanning Tree Problem, Annals of the History of Computing, 7:43-57, 1985.
  • Vuillemin, A data structure for manipulating priority queues, CACM 21:309-314, 1978

• Thu 1/10: Fibonacci heaps. O(m + n log n) and O(m log* n) MST algorithms. Textbook references:
  • Kozen Chapter 9; CLRS Chapter 20.
  • See also Section 5 and Appendix A of the marvelous suvey by Eisner, State-of-the-Art Algorithms for Minimum Spanning Trees: A Tutorial Discussion, 1997.
  Historical references:
  • Fredman/Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, JACM 34(3):596 - 615, 1987.
  • For a refinement with a running time of O(m log(log* n)), which we won't cover, see Gabow/Galil/Spencer/Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica '86. The main idea is not unlike that in HW #1, Problem #3. See also Section 5 of Eisner.

• Tue 1/15: Boruvka's algorithm. The Karger-Klein-Tarjan algorithm. Textbook references:
  • Motwani/Raghavan, Randomized Algorithms, Section 10.3.
  • Section 7 of Eisner, State-of-the-Art Algorithms for Minimum Spanning Trees: A Tutorial Discussion, 1997.
  Historical references:
  • Karger/Klein/Tarjan, A randomized linear-time algorithm to find minimum spanning trees, JACM '95.

• Thu 1/17: MST Verification with only linear comparisons. Textbook references:
  • Section 6 of Eisner, State-of-the-Art Algorithms for Minimum Spanning Trees: A Tutorial Discussion, 1997.
  Historical references:
  • The first linear bound in the number of comparisons needed for MST verification is from Komlos, Linear verification for spanning trees , Combinatorica '85.
  • The first linear-time implementation is due to Dixon/Rauch/Tarjan, Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time, SICOMP '92.
  • A simplification (partially covered in class) is due to King, A Simpler Minimum Spanning Tree Verification Algorithm, Algorithmica '97.
  • See also Knuth, Pre-Fascicle 1a: Bitwise Tricks and Techniques (from Volume 4), for an exposition of the linear-time LCA algorithm (of Schieber and Vishkin) used by King.
  For the state-of-the-art in deterministic MST algorithms, see:
  • Fredman/Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, JCSS '94.
  • Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, JACM '00.
  • Chazelle, The soft heap: an approximate priority queue with optimal error rate, JACM '00.
  • Pettie, Finding Minimum Spanning Trees in O(m alpha(m,n)) Time, '99 tech report.
  • Pettie/Ramachandran, An optimal minimum spanning tree algorithm, JACM '02.

• Tue 1/22: Introduction to shortest paths. Start Goldberg's O(\sqrt{n}m log C) algorithm for single-source shortest paths with negative edge lengths.
  • Goldberg, Scaling Algorithms for the Shortest Paths Problem, SICOMP '95.

• Thu 1/24: Finish Goldberg's algorithm.

• Tue 1/29: Seidel's O(M(n) log n) algorithm for all-pairs shortest-paths in undirected unweighted graphs.
  • Seidel, On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs, JCSS '95.

• Thu 1/31: The planar separator theorem. Textbook references:
  • Kozen Chapters 14-15.
  Original paper:
  • Lipton/Tarjan, A Separator Theorem for Planar Graphs , SIAM J on Applied Math '79.

• Tue 2/5: More planar graph algorithms. Linear-time 5-coloring; quadratic-time planarity testing. Textbook reference:
  • Mehlhorn, Section 4.10 of Data Structures and Algorithms.
  The first linear-time planarity test:
  • Hopcroft/Tarjan, Efficient Planarity Testing, JACM '74.
  • Turing award lectures: Hopcroft and Tarjan.
  The most recent linear-time planarity testing algorithm:
  • Boyer/Myrvold, On the Cutting Edge: Simplified O(n) Planarity by Edge Addition, Journal of Graph Algorithms and Applications, 8(3):241-273, 2004

• Thu 2/7: Edmonds's maximum-cardinality (nonbipartite) matching algorithm. Textbook references:
  • Section 5.2 of the Cook et al book; Section 9.3 of Tarjan's book.
  Original paper (stop by if you want a copy):
  • Edmonds, "Paths, Trees, and Flowers", Canadian Journal of Mathematics, 17:449-467, 1965.

• Tue 2/12: Fast implementation of Edmonds via Union-Find. Same references as above and also:
  • Hopcroft/Ullman, Set Merging Algorithms, SICOMP '73.

• Thu 2/14: Optimal Union-Find:
  • Textbook treatments in Kozen, Lectures 10-11 and Tarjan Chapter 2.
  • Original reference: Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, JACM '75.
  • There is also a matching lower bound for any data structure for this problem: Fredman/Saks, The cell probe complexity of dynamic data structures, STOC '89.
  The original O(m\sqrt{n}) algorithm for maximum matching:
  • Micali/Vazirani, "An O(\sqrt{|v|}|E|) Algorithm for Finding Maximum Matching in General Graphs", FOCS '80.
  • Gabow/Tarjan, A linear-time algorithm for a special case of disjoint set union, JCSS '85.
  • Vazirani, A Theory of Alternating Paths and Blossoms for Proving Correctness of the O(\sqrt{V}E) General Graph Maximum Matching Algorithm, Combinatorica '94.
  A newer algorithm with the same run time:
  • Gabow/Tarjan, Faster scaling algorithms for general graph matching problems, JACM '91.
  Randomized algorithms based on the Tutte matrix:
  • Motwani/Raghavan, Randomized Algorithms, Sections 7.2, 7.3, and 12.4.
  • For a derandomization, see: Geelen, An Algebraic Matching Algorithm, Combinatorica '00.

• Tue 2/19: State-of-the-art in randomized maximum matching algorithms.
  • Rabin/Vazirani, Maximum matchings in general graphs through randomization, Journal of Algorithms '89.
  • Mucha/Sankowski, Maximum Matchings via Gaussian Elimination, FOCS '04.
  • Mucha, PhD thesis, Warsaw University, 2005.
  • Harvey, Algebraic Algorithms for Matching and Matroid Problems, FOCS '06.

• Thu 2/21: Fast Gaussian elimination.
  • Textbook treatment: Aho/Hopcroft/Ullman, The Design and Analysis of Computer Algorithms, Sections 6.3-6.5.
  • Original reference: Strassen, Gaussian Elimination is not Optimal, Numerische Mathematik '69.
  • And: Bunch/Hopcroft, Triangular factorization and inversion by fast matrix multiplication, Mathematics of Computation '74.
  A primal-dual approach to minimum-cost perfect matching.
  • For example, Section 5.3 of the Cook et al. book.

• Tue 2/26: Edmonds's algorithm for min-cost perfect matching. Original reference:
  • Edmonds, "Maximum matching and a polyhedron with 0,1-vertices", Journal of Research of the National Bureau of Standards, Series B, '65.
  Textbook treatments:
  • For example, Section 5.3 of Cook et al. or Section 11.3 of Papadimitriou/Steiglitz.

• Thu 2/28: Gomory-Hu trees. Original reference:
  • Gomory/Hu, Multi-terminal network flows, SIAM Journal '61.
  Textbook treatments:
  • For example, Section 3.5 of Cook et al. or Section 15.4 of Schrijver.

• Tue 3/4: Deterministic and randomized graph sparsification. Applications to s-t cuts and flows.
  • Nagamochi/Ibaraki, A linear-time algorithm for finding a sparsek-connected spanning subgraph of a k-connected graph, Algorithmica '92.
  • Nagamochi/Ibaraki, Computing Edge-Connectivity in Multigraphs and Capacitated Graphs, SIDMA '92.
  • Benczur/Karger, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, combined full version of STOC '96 and SODA '98 papers.

• Thu 3/6: Finish random sparsification and applications. Main reference: the Benczur-Karger paper above. For more applicatons of the Compression Theorem to computing s-t cuts and flows, see both the Benczur-Karger paper and also:
  • Karger/Levine, Random Sampling from Residual Graphs, STOC '02.

• Tue 3/11: The Goldberg-Rao maximum flow algorithm. Primary reference:
  • Goldberg/Rao, Beyond the Flow Decomposition Barrier, JACM '99.
  Historical references:
  • Even/Tarjan, Network Flow and Testing Graph Connectivity, SICOMP '75.
  • Sleator/Tarjan, A data structure for dynamic trees, JCSS '93.
  • Goldberg/Tarjan, Finding Minimum-Cost Circulations by Successive Approximation, Math of OR '90.

• Thu 3/13: Finish the Goldberg-Rao algorithm. (Same references as last lecture.)