Algorithms on Digraphs
Advanced Course 2+1
Basic Information
Given by:  Saeed Amiri and Will Rosenbaum (Featured guest lecture given by Eunjin Oh), TA: Eunjin Oh. 

Time:  Monday 10:00 12:00, TA session (initial setting): Wednesday 14:0015:00 
Room:  024 (lecture), 023 (TA session) 
First Meeting:  October 22th. 
Credits:  5 credit points 
Grade formula:  50% final exam + 50 % exercises (25% solutions to the homework and 25 percent productive appearance in the exercise sessions) 
Prerequisites:  The course will assume a basic background in graph theory and the analysis of algorithms, but we will not presume any specific experience with directed graphs. 
News
 The final exam announcement is now online.
 Slides for Lecture 9 are available here!
 Three updates to Homework 4:
 In the construction for Exercises 1 and 2, it is emphasized that G' doesn't contain edges to A or from B
 The definition of "vertex cut" for Exercise 2 was fixed to include the possibility that X intersects A or B
 An additional hypothesis was added to Exercise 4: assume that there are no edges into A or out of B.
 Two typos were fixed in Homework 2:
 In exercise 2, your algorithm should find a colorful path of length k (if one exists).
 In exercise 4, the path P should have length k.
Description
Algorithmic graph theory is one of the oldest and beststudied subjects in computer science. The classical theory assumes edges, i.e., connections between nodes, are symmetric: if there is an edge connecting $v$ to $u$, then the same edge connects $u$ to $v$. However, in many physical systems, connections are inherently asymmetric. Such systems are best modeled by directed graphs (digraphs). Unfortunately, many problems that are straightforward to solve for undirected graphs become difficult or intractible for digraphs. In many cases, methods for dealing with digraphs are intrinsically different from the corresponding methods for undirected graphs.
In this course we will cover some recently developed techniques for designing algorithms on digraphs. We will focus on three main topics:
1. Separators and cuts, with applications to the feedback vertex set and multiway cut problems.
2. Routing problems such as the disjoint paths problem, finding long paths, and packet scheduling and routing.
3. Structural properties of digraphs, in particular directed treewidth.
Additionally, there will be guest lectures by Eunjin Oh, who will discuss related problems arising in computational geometry.
The course will assume a basic background in graph theory and the analysis of algorithms, but we will not presume any specific experience with directed graphs.
Mailing List
If you are interested in taking this course, please join our mailing list by clicking on this link.
Schedule
Moday 1012 in E4 1 room 024 for main course and every second Wednesday 1416 in room 023 for the TA session. Final exam is an oral exam and we will announce the exam date later.
Topic  Date  Homework  Lecturer  TA session 
Intro and FVS on Tournaments  22.10.2018  Sheet 1  Saeed  31.10.2018 
Long directed cycles and Color Coding  27.10.2018  Sheet 2  Will  31.10.2018 
Directed Tree Width  05.11.2018  Sheet 3  Saeed  14.10.2018 
Disjoint Paths Problem  12.11.2018  Sheet 4  Will  14.10.2018 
Erdos Posa Property I (Undirected Graphs)  19.11.2018  Sheet 5  Saeed  28.11.2018 
Erdos Posa Property II (Directed Graphs)  26.11.2018  Sheet 6  Saeed  28.11.2018 
Static Routing  03.12.2018  Will  19.12.2018  
Static and Dynamic Routing  12.12.2018  Sheet 7/8  Will  19.12.2018 
Dynamic Routing  17.12.2018  Sheet 9  Will  
Important Cuts I  07.01.2019  Sheet 10  Saeed  23.01.2019

Important Cuts II  14.01.2019  Sheet 11  Saeed  23.01.2019 
Directed grids in planar graphs  21.01.2019  Sheet 12  Will  
Geometric Graphs I  28.01.2019  Eunjin  
Geometric Graphs II  04.02.2019  Eunjin 
Textbooks
There is no single text that covers the material presented in this course. However, we will use sections from the following books:
 Classes of Directed Graphs by BangJensen and Gutin
 Parameterized Algorithms by Cygan et al.
Both books are on reserve in the informatics library. Digital copies are available using this link from the MPI or UdS network.