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

  • 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.

TopicDateHomeworkLecturerTA session
Intro and FVS on Tournaments22.10.2018Sheet 1Saeed31.10.2018
Long directed cycles and Color Coding27.10.2018Sheet 2Will31.10.2018
Directed Tree Width05.11.2018Sheet 3Saeed14.10.2018
Disjoint Paths Problem12.11.2018Sheet 4Will14.10.2018
Erdos Posa Property I (Undirected Graphs)19.11.2018Sheet 5Saeed28.11.2018
Erdos Posa Property II (Directed Graphs)26.11.2018Sheet 6Saeed28.11.2018
Static Routing03.12.2018 Will19.12.2018
Static and Dynamic Routing12.12.2018Sheet 7/8Will19.12.2018
Dynamic Routing17.12.2018 Will 
Important Separators I07.01.2019 Saeed 
Important Separators II14.01.2019 Saeed 
Directed grids in planar graphs21.01.2019 Will 
Geometric Graphs I28.01.2019 Eunjin 
Geometric Graphs II04.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.

Papers