Fall 2019 - COMPSCI 638 - Graph Algorithms

Administration

Instructor
Debmalya Panigrahi
D203, LSRC
Email: debmalya@cs.duke.edu
Office Hours: By appointment (send me an email)

Teaching Assistant (TA)
Kevin Sun
D227, LSRC
Email: ksun@cs.duke.edu
Office Hours: By appointment (send me an email)

Lectures: Wednesdays and Fridays 3:05pm- 4:20pm in North Building 311
We will use Piazza for all discussions and course correspondence.

Announcements

Synopsis

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:

Prerequisites

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.

Grading

The course grades will be determined based on:

Course Plan

Date Contents References Remarks Scribe notes1                       Scribe
Network Flows
Lecture 1 Wed Aug 28 Introduction and administrivia
Ford-Fulkerson
Maxflow-Mincut theorem
Ford-Fulkerson paper Notes
Lecture 2 Fri Aug 30 LP Duality of Maxflow-Mincut
Edmonds-Karp
Edmonds-Karp paper Notes
Lecture 3 Wed Sep 4 Blocking Flows, Dinitz's Algorithm
Push-Relabel (Goldberg-Tarjan)
Dinitz's algorithm
Goldberg-Tarjan paper
Notes
Lecture 4 Fri Sep 6 Maximum Multicommodity Flow
Garg-Könemann
Garg-Könemann paper Notes
Cuts and Rounding
Lecture 5 Wed Sep 11 Multiway Cut, Multicut
CKR Rounding
Calinescu-Karloff-Rabani paper Notes
Lecture 6 Fri Sep 13 Multicut (cont.), Sparsest Cut
GVY Rounding
Garg-Vazirani-Yannakakis paper Notes
Lecture 7 Wed Sep 18 Sparsest Cut (cont.) Leighton-Rao paper
Linial-London-Rabinovich paper
Notes
Global Min Cuts and Applications
Lecture 8 Fri Sep 20 The Contraction Algorithm
Recursive Contraction
Karger paper (randomized contraction)
Karger-Stein paper
Notes
Lecture 9 Wed Sep 25 Uniform Sampling for Cut Sparsification
Connectivity parameters
Karger paper (random sampling)
Benczúr-Karger paper
Notes
Lecture 10 Fri Sep 27 Cut Sparsification via Edge Strengths same as above Notes
Lecture 11 Wed Oct 2 Network Reliability Karger paper (network reliability)
Karp-Luby-Madras paper
Notes
Network Design
Lecture 12 Fri Oct 4 Metric TSP, Christofides algorithm
Metric Steiner Tree/Forest
Agarwal-Klein-Ravi paper
Goemans-Williamson paper (Steiner forest)
Notes
Lecture 13 Wed Oct 9 Primal-Dual algorithm for Steiner Forest
Generalized Steiner Forest
same as above Notes
Lecture 14 Fri Oct 11 Iterative Rounding for
Generalized Steiner Forest
Jain's paper Notes
Lecture 15 Wed Oct 16 Online Steiner Tree Imase-Waxman paper Notes
Lecture 16 Fri Oct 18 Online Steiner Forest Awerbuch-Azar-Bartal paper
Berman-Coulston paper
Notes
Spectral Graph Theory Lecture notes: Dan Spielman, Lap Chi Lau
Lecture 17 Wed Oct 23 Introduction and Preliminaries see above Notes
Lecture 18 Fri Oct 25 Electrical Flows see above Notes
Lecture 19 Wed Oct 30 Spectral Sparsification via Effective Resistances Spielman-Srivastava paper Notes
Multiplicative Weight Update Arora-Hazan-Kale survey
Lecture 20 Fri Nov 1 Weighted/Randomized Majority Algorithm see above Notes
Lecture 21 Wed Nov 6 MWU for Packing LPs, Maximum Flow Christiano-Kelner-Mądry-Spielman-Teng Notes
Semidefinite Programming
Lecture 22 Fri Nov 8 Maximum Cut Goemans-Williamson paper (maximum cut) Notes
Lecture 23 Wed Nov 13 Graph Coloring Wigderson paper
Blum paper
Karger-Motwani-Sudan paper
Notes
1 Disclaimer: The scribe notes have not been reviewed for correctness.