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:05 pm - 4:20 pm in North Building 311
We will use Piazza for all discussions and course correspondence.

Announcements

12/6/2019: The project presentations will be on Monday, 12/16 at 10 am - 12 pm in North 306.
12/2/2019: Prof. Panigrahi will hold an office hour today at 3 - 4 pm in his office.
11/23/2019: Prof. Panigrahi will hold an office hour on Monday, 11/25 at 3 - 4 pm in his office.
11/18/2019: The homework problems have been posted. The solutions are due on December 16 and must be submitted to the instructor by email.
If you cannot access the Piazza page, please email the TA.

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:

Flows: Augmenting paths; blocking flows; push-relabel; scaling; randomization; electrical flows and spectral techniques
Cuts: Duality with flows; Gomory-Hu trees; graph smoothing; global min-cut algorithms: randomized contractions, cut and spectral sparsification
Network Design: Steiner trees: LP formulations and iterative rounding; Steiner forests: primal dual; metric embeddings; group Steiner rounding; iterative rounding for SNDP; node-weighted and directed Steiner tree; online network design algorithms

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:

Homework problems (no collaboration): 30% weight
Class participation: 10% weight
Grading a homework problem: 10% weight
Project (in groups of 2-3): 50% weight (10% presentation, 40% outcome)

Course Plan

	Date	Contents	References	Remarks	Scribe notes¹	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 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
Lecture 24	Fri Nov 15	Sparsest Cut (cont.)	see Lectures 6-7		Notes
Lecture 25	Wed Nov 20	ARV algorithm for Sparsest Cut	Arora-Rao-Vazirani paper		Notes
Lecture 26	Fri Nov 22	ARV algorithm for Sparsest Cut (cont.)	see above		see above

¹ Disclaimer: The scribe notes have not been reviewed for correctness.