Spring 2017 - COMPSCI 590.5 - Graph Algorithms


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

Lectures: Mondays and Wednesdays 3:05pm- 4:20pm in  French Science 2237
Office Hours: By appointment (send me an email)

We will use Piazza for all discussions and course correspondence.



This course covers some of the most influential work in graph algorithms over the last two decades, with a 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 Wed Jan 11 Introduction and administrivia
Maxflow-Mincut theorem
Ford-Fulkerson paper
Edmonds-Karp paper
Mon Jan 16 No class. Martin Luther King, Jr. Holiday.
Wed Jan 18 Instructor travel. Lecture rescheduled.
Lecture 2 Mon Jan 23 Blocking Flows (Dinitz) Dinitz's algorithm
Lecture 3 Wed Jan 25 Blocking Flows (contd.)
Capacity Scaling
Beyond flow decomposition (Goldberg-Rao)
Goldberg-Rao paper
Lecture 4 Mon Jan 30 Beyond flow decomposition (contd.)
Lecture 5 Wed Feb 1 Push-Relabel (Goldberg-Tarjan) Goldberg-Tarjan paper
Global Mincuts
Lecture 6 Mon Feb 6 The contraction algorithm (Karger)
Uniform sampling theorem (Karger)
Contraction algorithm
Uniform sampling
Lecture 7 Wed Feb 8 Connectivity parameters Notes
Lecture 8 Mon Feb 13 Cut sparsification via connectivity sampling
Fung-Hariharan-Harvey-Panigrahi paper
Benczur-Karger paper
Lecture 9 Wed Feb 15 Deterministic contraction (Nagamochi-Ibaraki) Nagamochi-Ibaraki paper (unit capacity)
Nagamochi-Ibaraki paper (capacitated)
Lecture 10 Mon Feb 20 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
Back to Flows Notes
Lecture 11 Wed Feb 22 Randomized maxflow algorithm (Karger-Levine) Karger-Levine paper Notes
Lecture 12 Mon Feb 27 Introduction to Spectral Graph Theory Lecture notes: Dan Spielman, Lap Chi Lau Notes
Lecture 13 Wed Mar 1 Electrical Flows Same as above Notes
Lecture 14 Wed Mar 8 Maximum Flows using Electrical Flows Christiano et al. paper Notes
Mon Mar 13 Spring break
Wed Mar 15 Spring break
Network Design
Lecture 15 Mon Mar 20 Minimium Spanning Tree Karger-Klein-Tarjan paper Notes
Lecture 16, 17, 18
(Extended makeup lecture)
? 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
Lecture 19 Wed Mar 22 Node-weighted Steiner tree/forest (Klein-Ravi) Klein-Ravi paper Notes
Lecture 20, 21
(Extended makeup lecture)
? 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
Lecture 22 Mon Mar 27 Generalized Steiner Forest: primal dual algorithms Williamson-Goemans-Mihail-Vazirani paper
Goemans et al. paper
Lecture 23 Wed Mar 29 Generalized Steiner Forest: iterative rounding Jain's paper Notes
Lecture 24 Mon Apr 3 Maximum cut: SDP relaxation
Goemans-Williamson paper Notes
Lecture 25 Wed Apr 5 Group Steiner tree (Garg-Konjevod-Ravi) Garg-Konjevod-Ravi paper Notes
Lecture 26 Mon Apr 10 Metric embeddings Bartal's papers:
O(log2 n) stretch, O(log n loglog n) stretch
Fakcharoenphol-Rao-Talwar paper
Wed Apr 12
Mon Apr 17
Wed Apr 19 Project presentations
1 Disclaimer: The scribe notes have not been reviewed for correctness.