Towards graph minors for directed graphs – University of Copenhagen

Towards graph minors for directed graphs

Talk by Ken-Ichi Kawarabayashi, Professor at The National Institute of Informatics

Abstract

The seminal graph minor theory is one of the deepest results in all of mathematics, but it only works for undirected graphs. What about directed graphs?

Researchers come to know that there is a big difference. So the first step would be to show "the excluded grid theorem" for digraphs.  For undirected graphs, this was  originally proved by Robertson and Seymour in Graph Minors V, and is one of the most central results in the study of graph minors. It has found numerous applications in algorithmic graph structure theory.

Reed, and  Johnson, Robertson, Seymour and Thomas (in 1997) conjectured an analogous theorem for directed graphs, i.e. the existence of a function f(k) such that every digraph of directed tree-width at least f(k) contains a directed grid of order k. In an unpublished manuscript from 2001, Johnson, Robertson, Seymour and Thomas give a proof of this conjecture for planar digraphs.

In this talk, we shall report recent progress (joint work with Stephan Kreutzer). We shall discuss the following:

  1. The excluded grid theorem for directed graphs with no H-minor
  2. The half-integral grid theorem.
  3. Some applications to the disjoint paths problem.


Bio

Ken-ichi Kawarabayashi received his B.S., M.S. and Ph. D from Keio University in 1998, 2000 and 2001 respectively. After spending a few years in U.S.A., he joined Tohoku Univ. as an assistant professor in 2003. He moved to National Institute of Informatics in 2006 as an associated professor, and in 2009, he was promoted to a full professor. From 2012 October, he leads > $15M grant project for 5 years.  He obtained a few prizes, including Japan Academy Medal in 2013. He also obtained a few best paper awards for prestigious international conferences, including SODA’13 (best paper) and KDD’14 (best paper runner-up).