On problems concerning (arc-)disjoint structures in a digraph

Graphs, Hypergraphs, and Computing

16 January 14:00 - 15:00

Joergen Bang-Jensen - University of Southern Denmark

We consider the following type of problems for given properties P and P' Given a digraph H, decide whether H contains (arc)-disjoint subdigraphs D,D' such that D has property P and D' has property P'. The properties P and P' can be many things, e.g. having an out-branching, being connected, containing a (directed) path with prescribed end vertices, being strongly connected, containing a (directed) cycle, etc. We will survey a number of results in this area, some of which mix properties of graphs and digraphs. One example of such a problem is the following: Given a digraph D; does its underlying undirected graph UG(D) contain two disjoint cycles, C,C' such that C is also a directed cycle in D, while C' does not have to respect the orientation of the arcs in D? The complexity of this problem and its arc-disjoint analogue was recently characterized by the speaker in joint works with Kriesell, Maddaloni and Simonsen. We will also give a number of open problems in the lecture.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to