Topics in Graph Algorithms

Course Summary

Old and more recent topics in graph algorithms. Focus will be on connections to linear algebraic methods broadly interpreted including polyhedral techniques, matrix multiplication based algorithms, semi-definite programming, and spectral methods.

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

Lecture schedule: Wed/Fri 9.30-10.45am, Siebel

Teaching assistants: None!

Office hours: Siebel 3rd floor theory lounge. Fri 1:00-2:00pm

Grading policy: Homework + Scribing + Project (details TBD)

Prerequisites: CS 473 or comparable understanding and facility with algorithms, probability, and linear algebra.

Links: Piazza;  Gradescope (enroll using code M35XW7)

Projects: Instructions and paper list (to be posted later)

Homework

• Homework 1. Due 2/10 10am. 
• Homework 2. Due 2/26 10am.
• Homework 3. Due 3/27 10am.
• Homework 4. Due 4/20 10am.
• Homework 5. Due 5/08 10am.

Lecture Schedule

• Wednesday, Jan 22. Introduction and algorithms via matrix multiplication (triangle counting, transitive closure, APSP).
  • Tablet notes and scribed notes
  • Uri Zwick's slides on graph algorithms via matrix multiplication which is the basis for the lecture
  • Triangle counting and applications; see notes of Tim Roughgarden here and here which refer to relevant papers
  • Webpage of Virginia Vassilevksa Williams has several papers, talks and surveys on recent developments on matrix multiplication and fine grained complexity
  • A survey on matrix multiplication algorithms by Markus Blaser.
• Friday, Jan 24. Matchings via determinants (to be continued next lecture)
  • Tablet notes and scribed notes
  • See Uri Zwick's slides
  • Algebraic Structures and Algorithms for Matchings and Matroid Problems by Nick Harvey.
  • Fast matrix rank algorithms and applications by Cheung et al. 
• Wednesday, Jan 29. Parallel algorithm for matchings via determinants. Matchings via blossom contraction
  • A different proof of the isolation lemma by a high-school student
  • CACM article on recent developments on deterministic parallel algorithms for matchings
  • Notes on non-bipartite matchings from Chandra's past course on combinatorial optimization
• Friday, Jan 31. Finish Edmonds algorithm for max cardinality matching. Start proof of integrality of matching polytope
  • Notes on non-bipartite matchings from Chandra's past course on combinatorial optimization
• Wednesday, Feb 5. Finish integrality of matching polytope
• Friday, Feb 7. Stable matchings, Gale-Shapley algorithm, and related problems, polytopes for stable matchings.
  • Tablet notes and scribed notes
  • Chapter 1 of Algorithm Design by Kleinberg and Tardos.
  • The Stable Marriage Problem: Structure and Algorithms by Gusfield and Irving.
  • Algorithmics of Matching under Preferences by Manlove.
• Wednesday, Feb 12. Stable matching polytope. Application of stable matching to disjoint paths
  • Tablet notes
  • The Geometry of Fractional Stable Matchings and Its Applications by Teo and Sethuraman
  • An Elementary Integrality Proof of Rothblum's Stable Matching Formulation by Konemann et al. 
  • Reconstructing edge-disjoint paths by Conforti, Hassin and Ravi and an improvement in run time by Chao Xu.
• Friday, Feb 14. Spanning tree and matroids. 
  • Intro to matroids: notes from Chandra's course on combinatorial optimization
• Wednesday, Feb 19. Matroid polytopes
  • Matroid base and independence polytopes: notes1, notes2
• Friday, Feb 21. Bounded degree spanning trees via iterated rounding
  • Singh and Lau paper 
  • Notes from Jan Vondrak's course 
  • Furer-Raghavachar paper on unweighted case via local search. See also Sec 9.3 in Williamson-Shmoys book.
  • Generalization to matroids and submodular flows by Kiraly, Lau, Singh.
  • Iterative methods in Combinatorial Optimization by Lau, Ravi and Singh.
• ​Wednesday, Feb 26. Finish BD MST. 
• Friday, Feb 28. Matrix tree theorem.
  • Notes from David Williamson's course
• Wednesday, Mar 4. Finish matrix tree. Discuss expanders and sparsest cut
• Friday, Mar 6. Intro to cuts and flow-cut gaps via s-t cut, multicut, non-uniform sparsest cut
  • Chapters 8 and 15 in William-Shmoys book on approximation
  • Old notes from Chandra's courses on multicut and sparsest cut (not very polished)
• Wednesday, Mar 11. Sparsest cut via l_1 embedding
  • See refs from previous lecture
  • References on metric embeddings. Matousek's lecture notes, Moses Charikar's course and pointers therein.
• Friday, Mar 13. Bourgain's l_1 embedding (start of online Zoom lectures due to Covid-19 pandemic)
  • Tablet notes
  • Chapter 21 in Vazirani book on approximation, Chapter 15 in Williamson-Shmoys books
• Wed, Mar 18, Fri Mar 20. Spring break
• Wednesday,  Mar 25. Lower bound for flow-cut gap and l_1 embeddings
  • See refs from previous lecture
• Friday, Mar 27. Intro to tree embeddings and Cheeger inequaltiy
• Wednesday, April 1st. No lecture, April fool's day! Some relevant linear algebra
  • Lap Chi Lau's notes (1 and 2) from course on spectral graph theory
  • Spielman's book part I.
  • Luca Trevisan's notes (1 and 2) from his course  on graph partitioning
• Friday, April 3rd. Cheeger's inequality
  • Tablet notes
  • Lap Chi Lau's notes
  • Luca Trevisan's notes (3 and 4) from his course 
  • Chapters 20, 21 in Spielman's book
• Wednesday, April 8th. Finish Cheeger's inequality
• Friday, April 10th. Random walks and spectral gap
  • Tablet notes
  • Lap Chi Lau's notes
  • Chapter 10 in Spielman's book
• Wednesday, April 15th. Finish random walks
• Friday, April 17th.  Resistor networks and Laplacian
  • Tablet notes
  • Lap Chi Lau's notes
  • Chapters 11 and 12 in Spielman's book
• Wednesday, April 22nd. Random walks and effective resistance. 
• Friday, April 24th. Cut sparsification
  • Lap Chi Lau's notes for basic idea
  • Debmalya Panigrahi notes on uniform and non-uniform sampling
  • Benczur-Karger paper and general sparsfication framework paper of Fung et al
  • Nick Harvey's notes
• Wednesday, April 27th. Spectral sparsification by random sampling
  • Tablet notes
  • Lap Chi Lau's notes
  • Nick Harvey's notes on sparsification, matrix chernoff bound 
  • Chapter 32 in Spielman book
• Friday, April 29th. Linear-sized spectral sparsifiers
  • Tablet notes
  • Chapter 33 in Spielman book
  • Lap Chi Lau notes
• Wednesday, May 6. Review and wrap up 

References and study material

• Uri Zwick's slides on matrix multiplication based graph algorithms
• Dan Spielman's course on spectral graph theory and book on same topic
• Luca Trevisan's course on graph partitioning, expanders and spectral methods. Notes in one file.
• Lap Chi Lau's course on spectral graph theory
• Nisheeth Vishnoi's web page with several courses and manuscripts on spectral methods and applications
• David Williamson's course on bridging discrete and continuous optimization
• Algebraic Graph Theory by Godsil and Royle
• Approximation Algorithms and Semidefinite Programming by Gartner and Matousek (free inside UIUC network)
• Iterative Methods in Combinatorial Optimization by Lau, Ravi and Singh.
• Books on approximation algorithms: Williamson and Shmoys and Vazirani
• Combinatorial Optimization by Schrijver
• Topics in Combinatorial Optimization: Chandra (UIUC), Spring 2010
• Survey on expanders by Hoory, Linial and Wigderson.
• Books on randomization: Probability and Computing (Mitzenmacher-Upfal), Randomized Algorithms (Motwani-Raghavan), The Probabilistic Method (Alon-Spencer), Concentration of Measure (Dubhashi-Panconesi)
• A survey on concentration inequalities by Fan Chung and Linyuan Li.
• Probabilistic Tools for the Analysis of Randomized Optimization Heuristics by Benjamin Doerr