CS 594 Graph Algorithms
Fall, 2019
Intructors:
Anastasios Sidiropoulos
Time:
Tue Thu, 2:003:15pm
Location:
LC A3
Office hours:
1:002:00pm, SEO 1240
Syllabus
Scribe list
Relevant textbooks

T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms.

R. Ahuja, L. Magnanti and J. Orlin, Network Flows: Theory, Algorithms, and Applications.

B. Mohar and C. Thomassen, Graphs on Surfaces.
Description of the intended student audience
The course will be accessible to students with some knowledge of algorithms, graph theory, discrete mathematics, and probability theory. Programming experience is not necessary.
Homework
Homework 1
Project
Suggested topics
Lectures
Graph cuts

Aug 27, 2019. Lecture 1:
MinCut and kCut.
[Lecture notes by Ario Salmasi]

Aug 29, 2019. Lecture 2:
Multiway Cut.
[Lecture notes by Austin Antoniou]

Sep 3, 2019. Lecture 3:
Algorithms on dense graphs and Szemeredi's Regularity Lemma.
[Lecture notes by Dhanvi Sriram Athmakuri], [Lecture notes by Jason Bello], [Lecture notes by Timothy Carpenter]
Matching
TSP

Sep 12, 2019. Lecture 6.
Christofides algorithm for TSP.
Treewidth

Sep 17, 2019. Lecture 7:
Treewidth and dynamic programming.
[Lecture notes by Francisco Martinez]

Sep 19, 2019. Lecture 8:
Baker's technique.
[Jottings]
[Lecture notes by Ryan Slechta], [Lecture notes by Ross Vasko]

Sep 24, 2019. Lecture 9.
Planar separators.

Sep 26, 2019. Lecture 10.
Subexponentialtime algorithms on planar graphs.

Oct 1, 2019. Lecture 11.
The disjointpaths problem.

Robertson, N., Seymour, P. D.
Graph Minors XIII. The disjoint paths problem.
JCTB, 1995.

Kawarabayashi, K., Kobayashi, Y., Reed, B.
The disjoint paths problem in quadratic time.
JCTB, 2012.

Grohe, M.
Computing crossing numbers in quadratic time.
JCCS, 2004.

Kawarabayashi, K., Mohar, B., Reed, B.
A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded TreeWidth.
FOCS, 2008.
Algorithms on large graphs

Oct 3, 2019. Lecture 12.
Approximate transitive closure.

Oct 8, 2019. Lecture 13.
Streaming graph algorithms.

Feigenbaum, F., Kannan, S., McGrefor, A., Suri, S., and Zhang, J.
Graph Distances in the Data Stream Model.
SICOMP, 2008.

Oct 10, 2019. Lecture 14.
Streaming graph algorithms (cont.).

Oct 15, 2019. Lecture 15.
Graph property testing.
Divide and conquer

Oct 17, 2019. Lecture 16.
Divide and conquer via sparse cuts.

Oct 22, 2019. Lecture 17.
Computing sparse cuts.

Oct 24, 2019. Lecture 18.
Computing sparse cuts (cont.).

Oct 29, 2019. Lecture 19.
Spectral partitioning.
Graph Neural Networks

Oct 31, 2019. Lecture 20.
Graph Neural Networks.

Gori, M., Monfardini, G., Scarselli, F.
A new model for learning in graph domains.
IJCNN, 2005.

Dai, H., Khalil, E., Zhang, Y., Dilkina, B., Song, L.
Learning Combinatorial Optimization Algorithms over Graphs.
NIPS, 2017.

Nov 5, 2019. Lecture 21.
Pointer Networks.

Vinyals, O., Fortunato, M., Jaitly, N.
Pointer Networks.
NIPS, 2015.

Smith, W. D., Wormald, N. C.
Geometric separator theorems and applications.
FOCS, 1998.

Arora, S.
Nearly linear time approximation schemes for Euclidean TSP and other geometric problems.
FOCS, 1997.
Simplification of graphs

Nov 7, 2019. Lecture 22.
Random embeddings.

Nov 12, 2019. Lecture 23.
Random embeddings (cont.).

Nov 14, 2019. Lecture 24.
Random embeddings that preserve capacities.