Course description

Topics Covered and Additional Reading Material

• 3/28: Introduction to Graph Minor Theory; definitions of several types of graph minors; Wagner's conjecture; forbidden minors and Structure Theorem for them. Additional material:
  • A survey of László Lovász
  • David Johnson's column
  • Jeff Erickson's lecture notes


• 3/30: Forbidden minors continued: Separator Theorem and its use in obtaining PTAS for Independent Set in minor-free graphs; minor-closed family of graphs; obstructions; negative result of Fellows and Langston on computing obstructions. Additional material:
  • Separator theorem for minor-free graphs: the Alon-Seymour-Thomas paper; an exposition of the proof in lecture notes of Uri Feige; another proof with somewhat different parameters by Plotkin, Rao and Smith.
  • The Fellows-Langston paper (see Theorem 16).
  • Paul Seymour's survey on Hadwiger's conjecture


• 4/4: Treewidth: definition and basic properties. Algorithms for coloring and Node-Disjoint Paths in bounded-treewidth graphs. Additional reading:
  • Lecture notes by Uri Feige
  • A survey by Bruce Reed (the survey mostly focuses on brambles and tangles which we did not cover, but also talks about treewidth and its properties).
  • A survey of Robertson and Seymour on the algorithm for the Node-Disjoint Paths problem (in a book called "Paths, Flows, and VLSI-Layout").


• 4/6: Definition of pathwidth; Baker's technique (including for excluded-minor graphs) and its uses for designing 2-approximation for Coloring and PTAS for weighted Independent Set; proof of Baker's decomposition for planar graphs. Additional reading:
  • Baker's original paper
  • An exposition of the proof in Uri Feige's lecture notes
  • The paper proving the partitioning theorem for excluded-minor graphs.


• 4/11: Different versions of sparsest cut (both in edge-cut and vertex-cut settings); definition of expanders; several types of well-linkedness and connections to sparsest cut. Additional reading:
  • There are extensive discussions on sparsest cut in most books / lecture notes on approximation algorithms. See for example Vazirani's book, and Williamson-Shmoys book.
  • Node well-linkedness is a standard concept in graph theory; its relationship to treewidth is explored e.g. in Bruce Reed's survey.
  • The weaker edge-based well-linkedness concept was mainly used in work on routing problems (see e.g. this paper and this paper). The boosting theorem that connects the two well-linkedness notions was proved in this paper.


• 4/13: proof of the theorem connecting node-well-linkedness to treewidth; proof of the boosting theorem for well-linkedness.


• 4/18: statement of the Excluded Grid theorem for general and excluded-minor graphs; its uses in bidimensionality theory; high-level description of Robertson-Seymour's algorithm for Node-Disjoint Paths. Additional reading:
  • A paper that shows linear dependence between treewidth and grid-minor size in excluded-minor graphs.
  • A survey on bidimensionality theory.
  • An outline of Robertson and Seymour of their algorithm for the disjoint paths problem in this book.
  • Best current proof of the Flat Wall Theorem.
  • A simpler proof of the Unique Linkage Theorem (also explains how this theorem is used in the algorithm).


• 4/20: Proof of the Excluded Grid Theorem, based on this paper.


• 4/25: Iterative rounding technique, its use for finding exact algorithm for weighted bipartite matching; started bounded-degree spanning trees. Additional reading:
  • Lecture notes of Ola Svensson.


• 4/27: Bounded-degree spanning trees. Additional reading:
  • The paper of Singh and Lau.
  • Chapter 11 in Williamson-Shmoys book.
  • Lecture notes of Ola Svensson.
  • A book of Lau, Ravi and Singh on iterative methods.
  
  
• 5/2: End of bounded-degree spanning trees; start survivable network design.


• 5/4: Survivable network design. Additional reading:
  • The paper of Kamal Jain.
  • Chapter 11 in Williamson-Shmoys book.
  • Lecture notes of Chandra Chekuri.
  • A book of Lau, Ravi and Singh on iterative methods.
  
  
• 5/9: Proof of algorithmic Lovasz Local Lemma, based on this paper of Moser and Tardos.


• 5/11: Guest lecture by Madhur Tulsiani on Sum of Squares. Additional reading:
  • Madhur's survey with Eden Chlamtac.
  • Lecture notes of Boaz Barak.
  • A survey of Barak and Steurer.
  • A blog post by Boaz Barak.
  • A survey by Thomas Rothvoss.
  • Also, check out this workshop at Northwesern U, May 16-17


• 5/16: Poof of Lovasz Local Lemma - continued. Application to packet routing, based on this paper.


• 5/18 Application of Asymmetric Lovasz Local Lemma to frugal coloring. Congestion minimization: randomized rounding, constant approximation for grid graphs, negative example. Additional reading:
  • Alistair Sinclair's lecture notes discuss the frugal coloring application
  • Randomized Rounding technique is due to Raghavan and Thompson. See also lecture notes by James Lee
  • A paper related to congestion minimization in grids.
  • A better algorithm for congestion minimization when all paths are short via LLL (together with the negative example) can be found in this paper
  • This famous paper of Leighton and Rao gives many important results, and also shows that one can get near-optimal routing on expanders via short paths. If there is one paper you want to study on cuts an flows, it should be this one.
  
  
• 5/23 Oblivious routing: based on this paper by Harald Räcke. Additional reading:
  • Chapter 15 in Williamson-Shmoys book.
  • An interesting interpretation of the result in Andersen-Feige paper.
  • Another paper of Räcke with slightly different guarantees, but the routing is based on a single tree. This paper also gives a hierarchical decomposition of trees into "expander of expanders"-like structure, that has found many other uses.


• 5/25 Approximation of minimum bisection via oblivious routing; started routing problems (Node-Disjoint Paths/Edge-Disjoint Paths): greedy algorithm; multicommodity-flow LP and its integrality gap; hardness of approximation for directed graphs; overview of known results for various special cases.


• 6/1 Edge-Disjoint Paths on expanders; polylog(n)-approximation for Edge-Disjoint Paths in general graphs with constant congestion. Based on these papers.




---

Course requirements

There will be 3 homework assignments.

Homework Assignments

• Homework 1 Due: Apr 27 in class.
• Homework 2 Due: May 16 in class.
• Homework 3 Due: June 1 in class. There will be no extensions!