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:00-15: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 best-studied 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 10-12 in E4 1 room 024 for main course and every second Wednesday 14-16 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 Bang-Jensen 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.