Advanced Graph Algorithms

URL study guide

https://studiegids.vu.nl/en/courses/2025-2026/XM_0173

Course Objective

The goal of this course is to use techniques and tools in algorithms and theoretical computer science and apply them to the domain of graph algorithms. Graph algorithms provide the fundamental primitives for a wide range of applications in computer science from network routing, to data analytics, computing systems, machine learning, etc. A deeper and systematic understanding of these algorithms will help students develop their problem solving, algorithmic and analytical skills and to apply these skills to solving computational tasks in various areas. In addition to the fundamentals of graph algorithms, this course will also cover some of the recent algorithmic trends. In particular, we discuss graph algorithms in classic and modern computational models that represent distributed and parallel settings. This course also provides the foundations for research in algorithms and combinatorial optimization. Efficient algorithms for fundamental computational tasks on graphs (knowledge and understanding)Modelling computational tasks as graph problems (understanding and applying knowledge)Formal analysis of various computational resources and models (understanding)Using optimization techniques for solving hard problems (knowledge and understanding)Theoretical modeling graph analysis tasks on modern computational systems (understanding)

Course Content

Problems related to reachability, shortest-paths, maximum flow and bipartite matching in classic and distributed/parallel settings. Algebraic approaches (matrix multiplication) for graph algorithms and probabilistic algorithms. Computationally hard graph problems and applying optimization techniques such as local search, integer programming, etc.

Teaching Methods

There will be two in-person lectures per week. In addition there will be weekly interactive problem solving sessions.

Method of Assessment

The final grade will be based on one final exam (8 points out of 10) and several assignments (2 points out of 10). Each assignment gets a fail or pass grade, and students get a grade out of 2 based on the number of passed assignments. In other words, the final grade is 0.8
- (score in the final exam)+ 0.2*(number of passed assignments). There will be one re-sit replacing the exam portion of the grade (8 points), but there will be no resit for the assignment portion of the grade.

Literature

Reading material (including online resources such as lecture notes and textbooks) will be provided via canvas.

Target Audience

Masters in Computer Science

Recommended background knowledge

Data Structure and Algorithms, Discrete Mathematics, Basics of Probability Theory and experience with mathematical proofs is required. Further recommended background: Linear Algebra.