Computer Science 163/265, Winter 2025: Graph Algorithms

General Course Information

The two courses CS 163 (for undergraduates) and CS 265 (for graduate students) are co-located: they will have the same lectures, but different exam problems. They will have their lectures on Monday, Wednesday, and Fridays, 2:00 – 2:50, MOVED FROM ORIGINAL LOCATION, now Parkview 1100. The final exam will be in the same place at the scheduled time: Friday, March 21, 1:30PM – 3:30PM. Lectures and exams will only be offered in-person. The instructor is David Eppstein, and we also have three teaching assistants, Yubin Kim, Parnian Shakhar, and Stelios Stavroulakis. There is an online discussion forum on Ed Discussion, linked from Canvas.

For both courses, I will assign weekly practice problem sets at the start of each week, covering that week's material, and I strongly recommend that all students do these, but they will not be collected and graded. Instead, solutions will be posted at the end of the week to "Resources" in Ed Discussion, and you can expect to see similar problems (or even in some cases the same problems) on the exams. There will be three exams (two midterms and a final) each covering the material from roughly one third of the class (not comprehensive), each equally weighted in the overall course grade. Exams will be closed book, closed notes, and closed friends.

The lecture notes are linked online, starting from last year's lecture notes, and are subject to change until the start of each lecture (possibly also including minor corrections after the lecture). This web page will also include weekly additional reading for the graduate course, related to the topic of each week's material but going beyond the lectures. Undergraduates are welcome to try reading this material as well, but will not be tested on it. I will try to link free copies when I can find them, but you may need to use a UCI internet address to gain access to some of the readings.

The text we will be using is Graph Algorithms, a collection of readings compiled from Wikipedia (unfortunately, there is no published textbook that covers this material with the same depth and focus as this course). The lecture slides will be linked online here, prior to each lecture.

Office hours:

• David Eppstein: Mondays, 3:30PM – 4:30PM, Bren Hall 4082
• Yubin Kim: Tuesdays and Thursdays, 3:00PM – 4:00 PM, ICS 458B until week 8, MOVED to DBH 3015 starting week 9
• Parnian Shakhar: Tuesdays, 4:30PM – 6:30PM, Bren Hall 4099
• Stelios Stavroulakis: Wednesdays 5:30PM – 7:30PM, Java City outside Bren Hall (because Bren Hall will be locked by that time)

Tentative Schedule of Topics

Week 1 (January 6 – January 10):

 

Extracting information from graph structure: Web search engines and the PageRank algorithm.

Computer representation of graphs and the decorator pattern.

Web crawler case study; review of breadth-first search.

Depth-first search and Tarjan's algorithm for strongly connected components.

 

Practice problem set 1

Lecture notes: Monday, Wednesday, Friday

Graduate reading: "Implicit representation of graphs", S. Kannan, M. Naor, and S. Rudich, SIAM J. Discrete Math. 1992.

 

Week 2 (January 13 – January 17):

 

Maze and river network simulation via invasion percolation case study. Minimum spanning trees and their properties.

Prim-Dijkstra-Jarnik algorithm, Boruvka's algorithm, and Kruskal's algorithm.

Spreadsheet and critical path scheduling case studies. DAGs and topological ordering.

 

Practice problem set 2

Lecture notes: Monday, Wednesday, Friday,

Graduate reading: "Simplifying activity-on-edge graphs", D. Eppstein, D. Frishberg, and E. Havvaei, SWAT 2020.

 

Week 3 (January 20 – January 24):

 

Holiday Monday, January 20: Martin Luther King, Jr. Day

 

Road map path planning case study. Shortest paths, relaxation, Dijkstra, and Bellman-Ford.

Reweighting: Johnson's algorithm, Suurballe's algorithm, A*, and Landmark-based distance estimation.

 

Practice problem set 3

Lecture notes:Wednesday, Friday

Graduate reading: "Negative-weight single-source shortest paths in near-linear time", A. Bernstein, D. Nanongkai, and C. Wulff-Nilsen, FOCS 2022.

 

Week 4 (January 27 – January 31):

 

Midterm Monday, January 27

 

Preference voting case study and the widest path problem.

Transportation scheduling case study. Euler tours and the traveling salesperson problem.

 

Practice problem set 4

Lecture notes: Wednesday, Friday

Graduate reading: "Fast Schulze voting using quickselect", A. Arora, D. Eppstein, and R. L. Huynh, 2024.

 

Week 5 (February 3 – February 7):

 

Approximation algorithms and the approximation ratio, MST-doubling heuristic, Christofides' heuristic.

Exponential-time dynamic programming for the traveling salesperson problem.

Social network analysis case study. Erdős numbers, the Oracle of Bacon, and the Milgram small-world experiment.

Social network properties: sparsity, small world property, power laws.

Methods for generating synthetic networks: Erdős–Rényi model, ERGM, random graphs with fixed degrees, Barabási-Albert (preferential attachment), Kleinberg's model.

 

Practice problem set 5

Lecture notes: Monday, Wednesday, Friday

Graduate reading: "TSP escapes the $O(2^n{n}^2)$ curse", M. Stoian, 2024.

 

Week 6 (February 10 – February 14):

 

Centrality, degeneracy and k-cores.
Cliques, Moon-Moser bound on maximal cliques, Bron-Kerbosch algorithm.

Register allocation case study. Strahler number, graph coloring, greedy coloring, interval graphs.

 

Practice problem set 6

Lecture notes: Monday, Wednesday, Friday

Graduate reading: "Arboricity and subgraph listing algorithms", N. Chiba and T. Nishizeki, SIAM J. Comput. 1985.

 

Week 7 (February 17 – February 21):

 

Holiday Monday, February 17: Presidents' Day

 

Chordal graphs, and perfect graphs and using Lexicographic breadth-first search to find an elimination ordering.

Pathwidth, treewidth, the logic of graphs, and Courcelle's theorem.

 

Practice problem set 7

Lecture notes: Wednesday, Friday

Graduate reading: "Geometric graphs with unbounded flip-width", D. Eppstein and R. McCarty, CCCG 2023.

 

Week 8 (February 24 – February 28):

 

Midterm Monday, February 24

 

Baseball elimination case study. Maximum flow problem, minimum cut problem, max-flow min-cut theorem.

Augmenting path (Ford-Fulkerson) algorithm. New fast algorithms for integer flows.

 

Practice problem set 8

Lecture notes: Wednesday, Friday

Graduate reading: "Learning-augmented maximum flow", A. Polak and M. Zub, Inf. Proc. Lett. 2024.

 

Week 9 (March 3 – March 7):

 

Matchings, Bipartite graphs, formulating bipartite maximum matching as a flow problem.
Using matchings to find vertex covers and independent sets, partition into a minimum number of rectangles.

The assignment problem and the Hungarian algorithm.

Medical school residency assignment case study, stable matching, Gale-Shapley algorithm for stable matching.

 

Practice problem set 9

Lecture notes: Monday, Wednesday, Friday

Graduate reading: "Matching is as easy as the decision problem, in the NC model", N. Amari and V. Vazirani, ITCS 2020.

 

Week 10 (March 10 – March 14):

 

Planar graphs; review of planarity-related topics from earlier weeks.

Road maps, spanning trees of grid graphs, graph coloring and the four-color theorem.

Duality, duality of Euler tours and bipartiteness, Euler's formula.

Planarity testing and the cycle-based planarity testing algorithm.

Fáry's theorem and Schnyder woods.

 

Practice problem set 10

Lecture notes: Monday, Wednesday, Friday

Graduate reading: "Beyond Planar Graphs: Introduction", Seoh-Hee Hong, NII Shonan Meeting on Beyond Planar Graphs, 2020.

 

Material from Previous Course Offerings

Midterm I, Midterm II, and Final from Winter 2024.