CS 594 Graph Algorithms

Relevant textbooks

• T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms.
• R. Ahuja, L. Magnanti and J. Orlin, Network Flows: Theory, Algorithms, and Applications.
• B. Mohar and C. Thomassen, Graphs on Surfaces.

Description of the intended student audience

The course will be accessible to students with some knowledge of algorithms, graph theory, discrete mathematics, and probability theory. Programming experience is not necessary.

Homework

Homework 1

Project

Suggested topics

Lectures

Graph cuts

• Aug 27, 2019. Lecture 1: Min-Cut and k-Cut. [Lecture notes by Ario Salmasi]
  • Karger, D.R. Global Min-cuts in RNC, and Other Ramifications of a Simple Min-Cut Algorithm. SODA, 1993.
• Aug 29, 2019. Lecture 2: Multiway Cut. [Lecture notes by Austin Antoniou]
  • Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D. and Yannakakis, M. The complexity of multiterminal cuts. SICOMP, 1994.
• Sep 3, 2019. Lecture 3: Algorithms on dense graphs and Szemeredi's Regularity Lemma. [Lecture notes by Dhanvi Sriram Athmakuri], [Lecture notes by Jason Bello], [Lecture notes by Timothy Carpenter]
  • Frieze, A. and Kannan, R. The regularity lemma and approximation schemes for dense problems. FOCS, 1996.

Matching

• Sep 5, 2019. Lecture 4: Maximum Bipartite Matching. [Jottings] [Lecture notes by Sherif ElAzzouni]
• Sep 10, 2019. Lecture 5: Maximum Matching. [Jottings] [Lecture notes by Elena Farahbakhsh]
  • Edmonds, J. Paths, trees, and flowers. Canadian Journal of mathematics, 1965.

TSP

• Sep 12, 2019. Lecture 6. Christofides algorithm for TSP.
  • Christofides, N. Worst-case analysis of a new heuristic for the travelling salesman problem. No. RR-388. CMU Management Sciences Research Group. 1976.

Treewidth

• Sep 17, 2019. Lecture 7: Treewidth and dynamic programming. [Lecture notes by Francisco Martinez]
  • H. L. Bodlaender. A tourist guide through treewidth. Acta Cybernetica, 1993.
• Sep 19, 2019. Lecture 8: Baker's technique. [Jottings] [Lecture notes by Ryan Slechta], [Lecture notes by Ross Vasko]
  • Baker, B. Approximation algorithms for NP-complete problems on planar graphs. JACM, 1994.
  • Bodlaender, H. L. A partial k-arboretum of graphs with bounded treewidth. TCS, 1998.
• Sep 24, 2019. Lecture 9. Planar separators.
  • Har-Peled, S. A Simple Proof of the Existence of a Planar Separator, 2016.
• Sep 26, 2019. Lecture 10. Subexponential-time algorithms on planar graphs.
  • Demaine, E., Fomin, F., Hajiaghayi and M., Thilikos, D. Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs. JACM, 2005.
• Oct 1, 2019. Lecture 11. The disjoint-paths problem.
  • Robertson, N., Seymour, P. D. Graph Minors XIII. The disjoint paths problem. JCTB, 1995.
  • Kawarabayashi, K., Kobayashi, Y., Reed, B. The disjoint paths problem in quadratic time. JCTB, 2012.
  • Grohe, M. Computing crossing numbers in quadratic time. JCCS, 2004.
  • Kawarabayashi, K., Mohar, B., Reed, B. A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width. FOCS, 2008.

Algorithms on large graphs

• Oct 3, 2019. Lecture 12. Approximate transitive closure.
  • Cohen, E. Size-Estimation Framework with Applications to Transitive Closure and Reachability. JCCS, 1997.
• Oct 8, 2019. Lecture 13. Streaming graph algorithms.
  • Feigenbaum, F., Kannan, S., McGrefor, A., Suri, S., and Zhang, J. Graph Distances in the Data Stream Model. SICOMP, 2008.
• Oct 10, 2019. Lecture 14. Streaming graph algorithms (cont.).
• Oct 15, 2019. Lecture 15. Graph property testing.
  • Goldreich, O. Introduction to Testing Graph Properties.

Divide and conquer

• Oct 17, 2019. Lecture 16. Divide and conquer via sparse cuts.
  • Leighton, T., Rao, S. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. JACM, 1999.
• Oct 22, 2019. Lecture 17. Computing sparse cuts.
• Oct 24, 2019. Lecture 18. Computing sparse cuts (cont.).
• Oct 29, 2019. Lecture 19. Spectral partitioning.
  • Lecture Notes on Graph Partitioning, Expanders and Spectral Methods. Luca Trevisan.

Graph Neural Networks

• Oct 31, 2019. Lecture 20. Graph Neural Networks.
  • Gori, M., Monfardini, G., Scarselli, F. A new model for learning in graph domains. IJCNN, 2005.
  • Dai, H., Khalil, E., Zhang, Y., Dilkina, B., Song, L. Learning Combinatorial Optimization Algorithms over Graphs. NIPS, 2017.
• Nov 5, 2019. Lecture 21. Pointer Networks.
  • Vinyals, O., Fortunato, M., Jaitly, N. Pointer Networks. NIPS, 2015.
  • Smith, W. D., Wormald, N. C. Geometric separator theorems and applications. FOCS, 1998.
  • Arora, S. Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. FOCS, 1997.

Simplification of graphs

• Nov 7, 2019. Lecture 22. Random embeddings.
  • Fakcharoenphol, J., Rao, S., Talwar, S. A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics. JCSS, 2004.
  • Bartal, Y. Probabilistic Approximation of Metric Spaces and its Algorithmic Applications. FOCS, 1996.
• Nov 12, 2019. Lecture 23. Random embeddings (cont.).
• Nov 14, 2019. Lecture 24. Random embeddings that preserve capacities.
  • Andersen, R., Feige, U. Interchanging distance and capacity in probabilistic mappings. ArXiv, 2009.
  • Racke, H. Optimal Hierarchical Decompositions for Congestion Minimization in Networks. STOC, 2008.