Research Seminar on Current Topics of Logic and Algorithmic Graph Theory

Welcome on the webpage of the LaS research seminar!
If you want to give a talk, contact us. To reveive our annoucements, you can subscribe to our mailing list.
Summer term 2019
Wednesday 22.05 at 14:00 in room 716
Meike Hatzel TU Berlin
The grid theorem, originally proved by Robertson and Seymour in 1986 [RS10, Graph Minors V], is one of the most central results in the study of graph minors and has found many algorithmic applications, especially in the analysis of routing problems. The relation between treewidth and grid minors is particularly tight for planar graphs, as every planar graph of treewidth at least 6k contains a grid of order k as a minor [RST94]. This polynomial, in fact linear, bound on the size of grid minors has enabled many important consequences, such as sublinear separators and subexponential algorithms for many NP-hard problems on planar graphs. In the mid-90s, Reed and Johnson, Robertson, Seymour and Thomas proposed a notion of directed treewidth and conjectured an excluded grid theorem for directed graphs. This theorem was proved in 2015 [KK15] by the latter two authors but the function relating directed treewidth and grid minors is very big, even in the planar case.
Directed grids have found several algorithmic applications such as low-congestion routing. See e.g. [CE15, CEP16, KKK14, EMW16, AKKW16]. However, in the undirected case the polynomial, in fact linear, bound on the size of grid minors in planar graphs have made this tool so extremely successful. Consequently, the lack of polynomial bounds for directed grid minors in planar digraphs has so far prevented further applications of this technique in the directed setting. The main result of this paper is to close this gap and to establish a polynomial bound for the directed grid theorem on planar digraphs. We are optimistic that this will enable further applications of directed treewidth and its dual notion of directed grids in the context of planar digraphs.
Towards the end, we also give “treewidth sparsifier” for directed graphs, which has been already considered in undirected graphs. This result allows us to obtain an Eulerian subgraph of bounded degree in D that still has high directed treewidth. We believe this result is of independent interest for structural graph theory.
Wednesday 15.05 at 14:00 in room 716
Sebastian Wiederrecht TU Berlin
A colouring of a digraph as defined by Erdős and Neumann-Lara in 1980 is a vertex-colouring such that no monochromatic directed cycles exist. The minimal number of colours required for such a colouring of a loopless digraph is defined to be its dichromatic number. This quantity has been widely studied in the last decades and can be considered as a natural directed analogue of the chromatic number of a graph. A digraph D is called even if for every 0-1-weighting of the edges it contains a directed cycle of even total weight. We show that every non-even digraph has dichromatic number at most 2 and an optimal colouring can be found in polynomial time. We strengthen a previously known NP-hardness result by showing that deciding whether a directed graph is 2-colourable remains NP-hard even if it contains a feedback vertex set of bounded size.
Joint work with Marcelo Garlet Millani and Raphael Steiner.
p-centered colorings of planar graphs
Wednesday 08.05 at 14:00 in room 716
Piotr Micek Jagiellonian University, Kraków
A p-centered coloring of a graph G is a coloring of its vertices such that for every connected subgraph H of G either H receives more than p colors or there is a color that appears exactly once in H. Very recently, we have shown that every planar graph admits a p-centered coloring with O(p^3 log(p)) colors. This improves an O(p^{19}) bound by Pilipczuk&Siebertz. We also know that some planar graphs require Omega(p^2 log(p)) colors. We have tight bounds for outerplanar graphs, stacked triangulations, and graphs of bounded treewidth.
Well-quasi-order in classes of directed graphs
Wednesday 03.04 at 14:00 in room 716
Irene Muzi TU Berlin
A set Q is well-quasi-ordered by a relation ⩿ if for every sequence q1, q2, ... of elements of Q there exist i < j such that qi ⩿ qj. In their Graph Minors series, Robertson and Seymour prove that graphs are well-quasi-ordered by the minor relation. This result, which is known as the Graph Minor Theorem, is considered one of the deepest results in graph theory and has several algorithmic applications. The same is not true for directed graphs and the relation of butterfly minor. In particular, we can easily identify two infinite antichains. We can then ask if classes of graphs that exclude these antichains are well-quasi-ordered by the butterfly minor relation. We prove that this is the case while at the same time providing a structure theorem for these graph classes. This is joint work with M. Chudnovsky, S-il Oum, P. Seymour and P. Wollan.
Wednesday 27.03 at 14:00 in room 716
Sebastian Wiederrecht TU Berlin
A graph G is called matching covered if it is connected and every edge is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition that can be considered a generalisation of directed treewidth. We show that the perfect matching width of every bipartite matching covered graph is within a factor of 2 of the perfect matching width of its braces. Moreover, we give characterisations for braces of perfect matching width in terms of edge maximal graphs similar to k-trees for undirected treewidth and elimination orderings. The latter allows us to identify braces of perfect matching width 2 in polynomial time and provides an algorithm to construct an optimal decomposition.
This is joint work with Archontia C. Giannopoulou and Meike Hatzel.
Wednesday 20.02 at 13:00 in room 716
Jean-Florent Raymond TU Berlin
In 1990, Thomas proved that every graph admits a tree decomposition of minimum width that additionally satisfies a certain connectivity condition called leanness [A Menger-like property of tree-width: The finite case. Journal of Combinatorial Theory, Series B, 48(1):67 – 76, 1990]. This result had many uses and has been extended to several other decompositions. On the other hand, tree-cut decompositions are graph decompositions that have been introduced by Wollan as a possible edge-version of tree decompositions and that behave nicely with respect to graph immersions [The structure of graphs not admitting a fixed immersion. Journal of Combinatorial Theory, Series B, 110:47 – 66, 2015].
In this seminar, I will talk about leanness for tree-cut decompositions and present recent results obtained jointly with Archontia Giannopoulou, O-joung Kwon, and Dimitrios Thilikos.
The Directed Tangle Decomposition Lemma
Wednesday 06.02 at 14:00 in room 716
Stephan Kreutzer TU Berlin
The canonical decomposition theorem for undirected graphs is another of the main steps in the proof of the undirected structure theorem. Informally it says that any graph has a tree decomposition distinguishing its maximal tangles, or somewhat more formally, it has a tree decomposition such that for any maximal tangle in the graph there is a unique node of the decomposition whose bag contains the tangle and any pair of distinguishable tangles is contained in different bags of the decomposition. In the statement of the structure theorem (large clique minor, small tree width or a tree decomposition into pieces almost embeddable on a surface into which the graph itself does not embed) this lemma is an important part of obtaining the claimed tree decomposition into almost embeddable pieces.

In this talk I will speak about the directed version of this theorem. Note that this is a cakeless theorem.
The Directed Flat Wall Theorem
Wednesday 30.01 at 14:00 in room 716
Archontia Giannopoulou TU Berlin
At the core of the Robertson-Seymour theory of graph minors lies a powerful structure theorem which captures, for any fixed graph H, the common structural features of all the graphs not containing H as a minor. An important step toward this structure theorem is the flat wall theorem, which has a lot of algorithmic applications (for example, the minor-testing and the disjoint paths problem with fixed number terminals). In this talk, we discuss the proof of the "directed" analogue of the flat wall theorem. Our result builds on the recent "directed" grid theorem by Kawarabayashi and Kreutzer.

Joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and O-joung Kwon.
The Infinite Lucchesi-Younger Conjecture
Wednesday 23.01 at 14:00 in room 716
Karl Heuer TU Berlin
Lucchesi and Younger proved the following min-max theorem for digraphs: For any weakly connected finite digraph D the maximum number of disjoint dicuts of D, i.e., cuts of D all whose edges are directed to one common side of the cut, equals the minimum size of an edge set which intersects all dicuts of D.

In this talk we shall look at a new and open conjecture stating a structural extension to infinite digraphs of this theorem in an Erdős-Menger-like way. We shall discuss special cases for which the conjecture is verified, and a reduction of the conjecture to countable digraphs.

Based on joint work with J. Pascal Gollin.
Winter term 2018/2019
Wednesday 12.09 at 14:00 in room 716
Adrian Alic and Felix Herron TU Berlin
Wednesday 10.10 at 14:00 in room 716
Jean-Florent Raymond TU Berlin
Wednesday 31.10 at 14:00 in room 716
Jean-Florent Raymond TU Berlin
Wednesday 7.11 at 14:00 in room 716
Jakub Gajarsky TU Berlin
Summer term 2018
Wednesday 09.05 at 13:00 in room 716
Nishad Kothari University of Vienna
Wednesday 23.05 at 13:00 in room 716
Marcelo Garlet Millani TU Berlin
Wednesday 06.06 at 14:00 in room 716
Meike Hatzel TU Berlin
Wednesday 13.06 at 14:00 in room 716
Jakub Gajarsky TU Berlin
Wednesday 22.08 at 14:00 in room 716
Sebastian Wiederrecht TU Berlin
Winter term 2017/18
27 October, 2017 / 02:00 p.m. / room TEL 716
Prof. Dr. Daniel Král University of Warwick
Summer term 2017
Wednesday, 1st of March, 2017, 1:00 p.m., room TEL 716
Lucas Heimberg
Wednesday, 8th of March, 2017, 1:00 p.m., room TEL 716
Jean-Florent Raymond
Wednesday, 15th of March, 2017, 1:00 p.m., room TEL 716
Seongmin Ok
Winter term 2016/17
Wednesday, 9th of November, 14:00 - 16:00 room TEL 716
Dr. Roman Rabinovich Technische Universität Berlin
Wednesday, 16th of November, 14:00 - 16:00 room TEL 716
Prof. Dr. Stephan Kreutzer Technische Universität Berlin
TBA
Wednesday, 23rd of November, 14:00 - 16:00 room TEL 716
Dr. Saeed Akhoondian Amiri Technische Universität Berlin
TBA
Wednesday, 30th of November, 14:00 - 16:00 room TEL 716
Dr. Sebastian Siebertz Technische Universität Berlin
Wednesday, 7th of December, 2016, 1:00 p.m., room TEL 716
Dr. Saeed Akhoondian Amiri Technische Universität Berlin
Summer term 2016
Research Colloquium on Current Topics in Logic and Graph Theory
Wednesday, 10:00 - 12:00 room TEL 716 (in irregular intervals, we will give concrete announcements)
Prof. Dr. Stephan Kreutzer Technische Universität Berlin
Wednesday, 20th July 2016, 2:00 p.m., room TEL 716
Dr. Eun Jung Kim Texas A & M University
Wednesday, 29th June 2016, 1:00 p.m., room TEL 716
Daniel A. Quiroz London School of Economics and Political Science
Thursday, 30th June 2016, 1:00 p.m., room TEL 716
Prof. Jan van den Heuvel London School of Economics and Political Science
Winter term 2014/15
Friday, 5th December 2014, 1:00 p.m., room TEL 716
Dr. Roman Rabinovich Technische Universität Berlin
Wednesday, 10th December 2014, 1:15 p.m., room TEL 716
Prof. Dr. Stephan Kreutzer Technische Universität Berlin
Wednesday, 10th December 2014, 2:30 p.m., room TEL 716
Viktor Engelmann Technische Universität Berlin
Winter term 2013/14
Friday, 8th November 2013, 10:00 a.m., room TEL 716
Technische Universität Berlin
Winter term 2012/13
Friday, 19th October 2012, 11:00 a.m., room TEL 716
Humboldt-Universität zu Berlin
Friday, 26th Oktober 2012, 11:00 a.m., room TEL 716
Technische Universität Berlin
Friday, 9th November 2012, 11:00 a.m., room TEL 716
University of Oxford
Friday, 23th November 2012, 11:00 a.m., room TEL 716
University of Cambridge
Friday, 7th Dezember 2012, 11:00 a.m., room TEL 716
Humboldt Universiät zu Berlin
Friday, 8th February 2013, 11:00 a.m., room TEL 716
Technische Universität Berlin
Monday, 11th March 2013, 1:00 p.m., room TEL 716
Technische Universität Berlin
Tuesday, 16th July 2013, 10:00 a.m., room TEL 716
Goethe-Universiät Frankfurt am Main
Summer term 2012
Monday, 27th August 2012, 2:00 pm, room TEL 512
Technische Universität Wien
Monday, 13th August 2012, 2:00 pm, room TEL 512
Technische Universität Berlin
Tuesday, 3rd July 2012, 1:00 pm, room TEL 512
Karlsuniversität Prag
Friday, 29th June 2012, 9:00 am, room TEL 512
Technische Universität Berlin
Tuesday, 12th June 2012, 9:00 am, room TEL 512
Technische Universität Berlin