Spring 2015 - COMPSCI 590.01 - Advanced Topics in Computer Science: Graph Algorithms


Debmalya Panigrahi
D203, LSRC
Email: debmalya@cs.duke.edu

Lectures: Tuesdays and Thursdays 11:45am- 1pm in LSRC D106
Office Hours: By appointment (send me an email)

We will use Piazza for all discussions and course correspondence.



This course is intended to be an advanced course in theoretical computer science covering some of the most influential work in graph algorithms over the last two decades. The current installment will focus on graph connectivity. This includes:


COMPSCI 532 (or an equivalent graduate course in algorithms). Talk to the instructor if you have never taken such a course but are comfortable with analytical reasoning and have taken at least one course (at any level) each in algorithms and discrete mathematics.


The course grades will be determined based on:

Course Plan

Date Contents References Remarks Scribe notes1                       Scribe
Network Flows
Lecture 1 Thurs Jan 8 Introduction and administrivia
Maxflow-Mincut theorem
Ford-Fulkerson paper
Edmonds-Karp paper
Lecture 2 Tues Jan 13 Blocking Flows (Dinitz) Dinitz's algorithm
Lecture 3 Thurs Jan 15 Blocking Flows (contd.)
Capacity Scaling
Beyond flow decomposition (Goldberg-Rao)
Goldberg-Rao paper
Lecture 4 Tues Jan 20 Beyond flow decomposition (contd.)
Lecture 5 Thurs Jan 22 Push-Relabel (Goldberg-Tarjan) Goldberg-Tarjan paper
Global Mincuts
Lecture 6 Tues Jan 27 The contraction algorithm (Karger)
Uniform sampling theorem (Karger)
Contraction algorithm
Uniform sampling
Notes Yuhao
Lecture 7 Thurs Jan 29 Connectivity parameters Notes Jiangwei
Lecture 8 Tues Feb 3 Cut sparsification via connectivity sampling
Fung-Hariharan-Harvey-Panigrahi paper
Benczur-Karger paper
Notes Allen
Lecture 9 Thurs Feb 5 Deterministic contraction (Nagamochi-Ibaraki) Nagamochi-Ibaraki paper (unit capacity)
Nagamochi-Ibaraki paper (capacitated)
Notes Janardhan
Lecture 10 Tues Feb 10 Recursive contraction (Karger-Stein)
Near-linear time min-cut algorithm (Karger)
Karger-Stein paper
Karger's near-linear time algorithm
Gabow's min-cut algorithm
Notes Brandon
Back to Flows Notes
Lecture 11 Thurs Feb 12 Randomized maxflow algorithm (Karger-Levine) Karger-Levine paper Notes Nadi
Tues Feb 17 School closed due to snow
Lecture 12 Thurs Feb 19 Introduction to Spectral Graph Theory Lecture notes: Dan Spielman, Lap Chi Lau Notes Yan
Lecture 13 Tues Feb 24 Electrical Flows Same as above Notes Stavros
Thurs Feb 26 School closed due to snow
Tues Mar 3 Cancelled due to instructor travel
Lecture 14 Thurs Mar 5 Maximum Flows using Electrical Flows Christiano et al. paper Notes Abhishek
Tues Mar 10 Spring break
Thurs Mar 12 Spring break
Network Design
Lecture 15 Tues Mar 17 Minimium Spanning Tree Karger-Klein-Tarjan paper Notes Allen
Thurs Mar 19 Cancelled due to departmental event
Lecture 16, 17, 18
(Extended makeup lecture)
Sun Mar 22 Steiner tree: approximation via MST
Steiner forest: primal dual algorithm
(Agarwal-Klein-Ravi, Goemans-Williamson)
Online Steiner tree (Imase-Waxman)
Online Steiner forest
(Awerbuch-Azar-Bartal, Berman-Coulston)
Agarwal-Klein-Ravi paper
Goemans-Williamson paper
Imase-Waxman paper
Awerbuch-Azar-Bartal paper
Berman-Coulston paper
Yuhao, Nat
Lecture 19 Tues Mar 24 Node-weighted Steiner tree/forest (Klein-Ravi) Klein-Ravi paper Notes Xiangyu
Lecture 20, 21
(Extended makeup lecture)
Wed Mar 25 Online set cover and non-metric facility location
Online Node-weighted Steiner tree
Alon et al. paper (online set cover)
Alon et al. paper (online network design)
Naor-Panigrahi-Singh paper
Liaghat-Hajiaghayi-Panigrahi paper
Abhinandan, Rupert
Lecture 22 Thurs Mar 26 Generalized Steiner Forest: primal dual algorithms Williamson-Goemans-Mihail-Vazirani paper
Goemans et al. paper
Notes Sam
Lecture 23 Tues Mar 31 Generalized Steiner Forest: iterative rounding Jain's paper Notes Brandon
Thurs Apr 2 Cancelled due to instructor travel
Lecture 24 Tues Apr 7 Maximum cut: SDP relaxation
Goemans-Williamson paper Notes Xi
Lecture 25 Thurs Apr 9 Group Steiner tree (Garg-Konjevod-Ravi) Garg-Konjevod-Ravi paper Notes Ios
Lecture 26 Tues Apr 14 Metric embeddings Bartal's papers:
O(log2 n) stretch, O(log n loglog n) stretch
Fakcharoenphol-Rao-Talwar paper
Tues Apr 21 Project presentations
1 Disclaimer: The scribe notes have not been reviewed for correctness.