CS 598: Topics in Graph Algorithms, Fall 2024

Course Summary

The course will cover selection of topics in graph algorithms with an emphasis on recent developments on fast algorithms for a variety of problems such as shortest paths, flows, cuts, and matchings. Structural results and connections to past ideas and results will also be discussed. This is an exploratory seminar-style course. A tentative list of topics (a superset of what we can cover).

  • New developments on shortest path algorithms with negative lengths, low-diameter graph decompositions, spanners etc
  • Global and Steiner mincut: tree packing, isolating cuts
  • Multiplicative weight updates and applications via fast data structures
  • Multicommodity flows, flow-cut gap, sparsest cut, cut-matching game
  • Expanders, well-linked sets, expander and well-linked decomposition, and applications
  • Making graphs look like trees: metrics, flows, separators
  • Graph Sparsification
  • Faster flow algorithms
  • Local algorithms for flows/cuts
  • Dynamic Data Structures for Matchings
  • Palette coloring and faster graph coloring algorithms
  • Connections to hypergraphs and submodularity
  • Gomory-Hu Trees

Administrative Information

Lectures: Tue, Thu 11-12.15pm in Siebel Center 0216.

Instructor:  Chandra Chekuri, 3228 Siebel Center, (chekuri at)

Office Hours (Chandra): Friday 1-2pm in 3228 Siebel, or by appointment

Grading Policy: 80% homework, 20% project.

Attendance policy: at least 65% of lectures for a grade. The revolution will not be televised, it will be live.

Prerequisites: This is a graduate level class on recent developments. Background in algorithms at the level of CS 473 is necessary and expected. Familiarity with basics of linear programming and randomization, and knowledge of standard graph algorithms is necessary. Most important is mathematical maturity and comfort with formal proofs and arguments and interest in the topic. Consult the instructor if you have questions.

Mental health support at UofI: Diminished mental health, including significant stress, mood changes, excessive worry, substance/alcohol abuse, or problems with eating and/or sleeping can interfere with optimal academic performance, social development, and emotional wellbeing. The University of Illinois offers a variety of confidential services including individual and group counseling, crisis intervention, psychiatric services, and specialized screenings at no additional cost. If you or someone you know experiences any of the above mental health concerns, it is strongly encouraged to contact or visit any of the University's resources provided below. Getting help is a smart and courageous thing to do -- for yourself and for those who care about you.
Counseling Center: 217-333-3704, 610 East John Street, Champaign, IL 61820
McKinley Health Center: 217-333-2700, 1109 South Lincoln Avenue, Urbana, Illinois 61801
University wellness center
Please do not hesitate to contact the instructor if you need help or assistance.

Student code: All students are expected to be aware of the university's student code, in particular the academic integrity policies

CS Code of Conduct: See here for important information on the code of conduct guidelines of the Siebel School of CS.

References

Electronic versions of several books from Cambridge University, Springer, Wiley and other publishers are available free to Univ of Illinois students via the library.

 

 

Ed (sign up at link), Gradescope (R7KJRX)  


Homework

Lectures

  • Lecture 1: 8/27/2024, Introduction, MST, linear-time randomized algorithm

  • Lecture 2: 8/29/2024, Tree packing, fractional version of Tutte-Nash-Williams theorem, towards mincut
    • Draft notes
    • Paper of C, Quanrud, Xu
    • Karger's tree packing based mincut paper, different from his random contraction based paper with Stein
    • Comb opt/graph theory refs for tree/matroid packing

  • Lecture 3: 9/03/2024, Mincut and bounding (approximate) mincuts via tree packing

  • Lecture 4: 9/05/2024, Steiner mincut via Isolating Cuts

  • Lecture 5: 9/10/2024, Start of metric methods, s-t cut, Mulitcut via metric decomposition
    • Draft notes
    • Chapters 14, 15, 16 in Chandra's approximation algorithms notes and pointers there
    • CMU notes (see also older notes) on low-stretch spanning tree embeddings and pointers there

  • Lecture 6: 9/12/2024, Low-diameter decompositions and low-stretch metric tree embeddings
    • Draft notes
    • CMU notes (see also older notes) on low-stretch spanning tree embeddings and pointers there

  • Lecture 7: 9/17/2024, Sparsest cut
    • Draft notes
    • Books on approximation, Vazriani (Chapter 21), Williamson-Shmoys (Chapters 8, 15).
    • Matousek's lecture notes on metric embeddings
    • Survey on expanders

  • Lecture 8: 9/19/2024, Expander decomposition and well-linked decomposition

  • Lecture 9: 9/24/2024, Oblivious routing
    • Draft notes
    • Quanrud's notes (Chapter 10)
    • Williamson-Shmoys approximation book (Chapter 15 )

  • Lecture 10: 9/26/2024, Catch up lecture

  • Lectures 11/12: 10/01/2024 and 10/03/2024, Cut-based hierarchical decomposition
    • Draft notes
    • Video of talk by Harald Raecke on fast algorithm for decomposition

  • Lectures 13/14: 10/08/2024 and 10/10/2024, Beating Bellman-Ford for Shortest Paths with Negative Lengths

  • Lectures 15/16: 10/15/2024 and 10/17/2024, Shortest Paths with Negative Weights --- Near-linear time scaling algorithm

  • Lecture 17/18: 10/22/2024 and 10/24/2024, MWU for approximating LPs, and applications
    • Draft notes
    • Paper of C, Jayram, Vondrak (see up to 3.1)
    • Survey of Arora, Hazan and Kale on MWU
    • Kent Quanrud's thesis (see Chapters 1 and 2 in particular)
    • Di Wang's thesis
    • CMU course resources (see 2023/24)

  • 10/29/2024, No lecture due to FOCS in Chicago

  • Lecture 19: 10/31/2024, Speeding up MWU (explicit packing LPs and Tree Packing)
    • Slides from a talk of Chandra
    • Paper of Neal Young on mixed packing and covering
    • Paper of C-Quanrud on tree packing
    • Kent Quanrud's thesis

  • Lecture 20: 11/04/2024, Cut-Matching Game for Fast Sparsest Cut
      • Draft notes
    • Quanrud's notes (Chapter 7)
    • Paper of Khandekar, Rao and Vazirani
    • Improved cut-matching game, paper of Orecchia et al.

  • Lecture 21: 11/06/2024, Finish previous lecture, discuss treewidth at high-level
      • Slides from a tutorial talk of Chandra on treewidth

  • 11/12/2024 and 11/14/2024, No lectures due to instructor travel.

  • Lecture 22: 11/19/2024, Blocking flows and discussion of link-cut trees
    • Notes from MIT (David Karger)
    • David Williamson network flows book
    • Bob Tarjan's book on data structures and network algorithms

  • Lecture 23: 11/21/2024, Push-Relabel for maxflow
    • Notes from Quanrud (Chapter 3), and video
    • David Williamson network flows book