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
Adam Mickiewicz University
Technical University of Denmark, DTU