Spring 2017 - COMPSCI 590.5 - Graph Algorithms

Administration

Instructor
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.

Announcements

01/11: Please sign up as a student of this course on Piazza. If you have not received the invitation yet, please email the instructor.

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:

6 out of 10-15 problems given through the course of the semester (due one week after last lecture, no collaboration). (30% weight)
Homework Problems
Course project (in groups of 2-3). (40% weight)
Scribing (due the day after lecture). (20% weight)
Templates: tex, ref, pdf
Class participation. (10% weight)

Course Plan

	Date	Contents	References	Remarks	Scribe notes¹	Scribe
		Network Flows
Lecture 1	Wed Jan 11	Introduction and administrivia Ford-Fulkerson 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.) Preflows
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		Notes
Lecture 7	Wed Feb 8	Connectivity parameters			Notes
Lecture 8	Mon Feb 13	Cut sparsification via connectivity sampling (Fung-Hariharan-Harvey-Panigrahi)	Fung-Hariharan-Harvey-Panigrahi paper Benczur-Karger paper		Notes
Lecture 9	Wed Feb 15	Deterministic contraction (Nagamochi-Ibaraki)	Nagamochi-Ibaraki paper (unit capacity) Nagamochi-Ibaraki paper (capacitated)		Notes
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		Notes
		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		Notes Notes
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 (Alon-Awerbuch-Azar-Buchbinder-Naor) Online Node-weighted Steiner tree (Naor-Panigrahi-Singh)	Alon et al. paper (online set cover) Alon et al. paper (online network design) Naor-Panigrahi-Singh paper Liaghat-Hajiaghayi-Panigrahi paper		Notes Notes
Lecture 22	Mon Mar 27	Generalized Steiner Forest: primal dual algorithms	Williamson-Goemans-Mihail-Vazirani paper Goemans et al. paper		Notes
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)	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(log² n) stretch, O(log n loglog n) stretch Fakcharoenphol-Rao-Talwar paper
	Wed Apr 12
	Mon Apr 17
	Wed Apr 19	Project presentations

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