# Algorithms on Digraphs

## Basic Information

Given by: Saeed Amiri and Will Rosenbaum (Featured guest lecture given by Eunjin Oh), TA: Eunjin Oh. Monday 10:00- 12:00, TA session (initial setting): Wednesday 14:00-15:00 024 (lecture), 023 (TA session) October 22th. 5 credit points 50% final exam + 50 % exercises (25% solutions to the homework and 25 percent productive appearance in the exercise sessions) 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.

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