# 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 receive our annoucements, you can subscribe to our mailing list.

Winter term 2020/21

Constant Congestion Brambles

Wednesday 10.01 at 14:00 on Zoom

Meike Hatzel
TU Berlin

In this talk I will present a result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk, Pawel Komosa and Manuel Sorge.

A bramble in an undirected graph G is a family of connected subgraphs of G such that for every two subgraphs H_1 and H_2 in the bramble either V(H_1) intersects V(H_2) or there is an edge of G with one endpoint in V(H_1) and the second endpoint in V(H_2). The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble.

Brambles are objects dual to treewidth: As shown by Seymour and Thomas,the maximum order of a bramble in an undirected graph G equals one plus the treewidth of G. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree n-vertex expander a bramble of order Ω(n^{1/2+δ}) requires size exponential in Ω(n^{2δ}) for any fixed δ ∈ (0,1/2]. On the other hand, the combination of results of Grohe and Marx, and Chekuri and Chuzhoy shows that a graph of treewidth k admits a bramble of order \widetilde{Ω}(k^{1/2}) and size \widetilde{O}(k^{3/2}). (\widetilde{Ω} and \widetilde{O} hide polylogarithmic factors and divisors, respectively.)

We first sharpen the second bound by proving that every graph G of treewidth at least k contains a bramble of order \widetilde{&Omega}(k^{1/2}) and congestion 2, i.e., every vertex of G is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we provide a tight upper bound for the lower bound of Grohe and Marx: For every δ ∈ (0,1/2], every graph G of treewidth at least k contains a bramble of order \widetilde{Ω}(k^{1/2+δ}) and size 2^{\widetilde{O}(k^{2δ})}.

A bramble in an undirected graph G is a family of connected subgraphs of G such that for every two subgraphs H_1 and H_2 in the bramble either V(H_1) intersects V(H_2) or there is an edge of G with one endpoint in V(H_1) and the second endpoint in V(H_2). The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble.

Brambles are objects dual to treewidth: As shown by Seymour and Thomas,the maximum order of a bramble in an undirected graph G equals one plus the treewidth of G. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree n-vertex expander a bramble of order Ω(n^{1/2+δ}) requires size exponential in Ω(n^{2δ}) for any fixed δ ∈ (0,1/2]. On the other hand, the combination of results of Grohe and Marx, and Chekuri and Chuzhoy shows that a graph of treewidth k admits a bramble of order \widetilde{Ω}(k^{1/2}) and size \widetilde{O}(k^{3/2}). (\widetilde{Ω} and \widetilde{O} hide polylogarithmic factors and divisors, respectively.)

We first sharpen the second bound by proving that every graph G of treewidth at least k contains a bramble of order \widetilde{&Omega}(k^{1/2}) and congestion 2, i.e., every vertex of G is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we provide a tight upper bound for the lower bound of Grohe and Marx: For every δ ∈ (0,1/2], every graph G of treewidth at least k contains a bramble of order \widetilde{Ω}(k^{1/2+δ}) and size 2^{\widetilde{O}(k^{2δ})}.

Even Circuits in Oriented Matroids

Wednesday 03.01 at 14:00 on Zoom

Karl Heuer
TU Berlin

In this talk I will state a generalisation of the even directed cycle problem, which asks whether a given digraph contains a directed cycle of even length, to orientations of regular matroids.

Motivated by this problem, I will define non-even oriented matroids generalising non-even digraphs, which played a central role in resolving the computational complexity of the even dicycle problem.

Then I will present and discuss our two recent results regarding these notions:

First we shall see that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids.

Second and with the main focus for this talk, we shall characterise the class of non-even oriented bond matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen.

The second result makes use of a new concept of minors for oriented matroids, which generalises butterfly minors for digraphs to oriented matroids.

The part of my talk regarding the second result will be mostly graph theoretical and does not require much knowledge about Matroid Theory.

This talk is about joint work [1] with Raphael Steiner and Sebastian Wiederrecht.

K. Heuer, R. Steiner and S. Wiederrecht, Even Circuits in Oriented Matroids, arxiv:2010.08988

Motivated by this problem, I will define non-even oriented matroids generalising non-even digraphs, which played a central role in resolving the computational complexity of the even dicycle problem.

Then I will present and discuss our two recent results regarding these notions:

First we shall see that the problem of detecting an even directed circuit in a regular matroid is polynomially equivalent to the recognition of non-even oriented matroids.

Second and with the main focus for this talk, we shall characterise the class of non-even oriented bond matroids in terms of forbidden minors, which complements an existing characterisation of non-even oriented graphic matroids by Seymour and Thomassen.

The second result makes use of a new concept of minors for oriented matroids, which generalises butterfly minors for digraphs to oriented matroids.

The part of my talk regarding the second result will be mostly graph theoretical and does not require much knowledge about Matroid Theory.

This talk is about joint work [1] with Raphael Steiner and Sebastian Wiederrecht.

K. Heuer, R. Steiner and S. Wiederrecht, Even Circuits in Oriented Matroids, arxiv:2010.08988

A matching theoretic approach to structural digraph theory

Wednesday 20.01 at 14:00 on Zoom

Sebastian Wiederrecht
TU Berlin

The theory of butterfly minors in digraphs which is closelinked to the notion of directed treewidth has become an active field of research in the past years. Many great advancements have been made such as a directed version of the famous Grid Theorem and several other generalisations of great results from the Graph Minors Series of Robertson and Seymour.

However, many of these results appear flawd when first encountered: The Erdos-Posa property of butterfly minors does not appear to be linked to a topological property, and the directed version of the Flat Wall is not actually flat.

In this talk we identify two possible reasons for these flaws and show how recent advancements in the area of structural matching theory can be used, by rethinking the way we handle butterfly minors and unavoidable infinite anti-chains of them, to achieve much nicer results.

However, many of these results appear flawd when first encountered: The Erdos-Posa property of butterfly minors does not appear to be linked to a topological property, and the directed version of the Flat Wall is not actually flat.

In this talk we identify two possible reasons for these flaws and show how recent advancements in the area of structural matching theory can be used, by rethinking the way we handle butterfly minors and unavoidable infinite anti-chains of them, to achieve much nicer results.

Winter term 2019/20

Differential analysis of FO logic of graphs

Thursday 27.02 at 14:00 in room 716

Jakub Gajarsky
TU Berlin

We propose a new framework for studying FO logic of graphs based on differential games, a newly introduced variant of Ehrenfeucht-Fraisse games. We believe that our approach can lead to new techniques useful for designing efficient algorithms for the FO model checking problem.

Half-integral linkages in highly connected directed graphs

Wednesday 19.02 at 14:00 in room 716

Irene Muzi
TU Berlin

We study the half-integral k-Directed Disjoint Paths Problem (1/2 kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to instances where k=2, and the input graph is L-strongly connected, for any L >= 1. We show that when the integrality condition is relaxed to allow each vertex to be used in two paths, the problem becomes efficiently solvable in highly connected digraphs (even with k as part of the input).

Specifically, we show that there is an absolute constant c such that for each k >= 2 there exists L(k) such that 1/2 kDDPP is solvable in time O(|V(G)|^c) for a L(k)-strongly connected directed graph G. As the function L(k) grows rather quickly, we also show that 1/2 kDDPP is solvable in time O(|V(G)|^f(k)) in (36k^3+2k)-strongly connected directed graphs. We show that for each epsilon <1, deciding half-integral feasibility of kDDPP instances is NP-complete when k is given as part of the input, even when restricted to graphs with strong connectivity epsilon k. This is joint work with Katherine Edwards and Paul Wollan.

Specifically, we show that there is an absolute constant c such that for each k >= 2 there exists L(k) such that 1/2 kDDPP is solvable in time O(|V(G)|^c) for a L(k)-strongly connected directed graph G. As the function L(k) grows rather quickly, we also show that 1/2 kDDPP is solvable in time O(|V(G)|^f(k)) in (36k^3+2k)-strongly connected directed graphs. We show that for each epsilon <1, deciding half-integral feasibility of kDDPP instances is NP-complete when k is given as part of the input, even when restricted to graphs with strong connectivity epsilon k. This is joint work with Katherine Edwards and Paul Wollan.

Erdös-Hajnal properties for powers of sparse graphs

Wednesday 29.01 at 14:00 in room 716

Michał Seweryn
Jagiellonian University

The notion of nowhere dense classes of graphs attracted much attention in recent years and found many applications in structural graph theory, algorithmics and logic. The powers of nowhere dense graphs do not need to be sparse, for instance the second power of star graphs are complete graphs. However, it is believed that powers of sparse graphs inherit somewhat simple structure. In this spirit, we show that for a fixed nowhere dense class of graphs and a positive integer d, in any n-vertex graph G in the class, there are disjoint vertex subsets A and B, each of size almost linear in n, such that in the d-th power of G, either there is no edge between A and B, or there are all possible edges between A and B. This is joint work with Marcin Briański, Piotr Micek and Michał Pilipczuk.

Tangle Tree-Labellings

Wednesday 18.12 at 14:00 in room 716

Stephan Kreutzer
TU Berlin

A tangle of order k in a digraph G is a consistent orientation of every directed separation of G of order
< k. Tangles, introduced by Robertson and Seymour for undirected graphs as part of their graph minor series, can be understood as a formal way of defining "k-connected components".

The tangle tree lemma for undirected graphs proved in Graph Minors X, then, can be seen as a generalisation of Tutte's decomposition theorem to arbitrary values of connectivity. It states that every graph has a tree-decomposition into its tangles (in a sense that will be made precise in the talk).

In this talk I'll present the directed version of this result. I will define directed tangles and the concept of tree-labellings (in analogy to GM X) and prove a directed analogon to the tangle tree lemma.

The tangle tree lemma for undirected graphs proved in Graph Minors X, then, can be seen as a generalisation of Tutte's decomposition theorem to arbitrary values of connectivity. It states that every graph has a tree-decomposition into its tangles (in a sense that will be made precise in the talk).

In this talk I'll present the directed version of this result. I will define directed tangles and the concept of tree-labellings (in analogy to GM X) and prove a directed analogon to the tangle tree lemma.

Distinguishing tangles

Friday 29.11 at 14:00 in room 716

Ann-Kathrin Elm
University of Hamburg

The tree of tangles theorem states that, given a set of tangles of a graph, there is a tree decomposition of the graph which distinguishes all the tangles which can be distinguished. In general the tree decomposition is not unique, one of the reasons being that there are separations of the graph which are contained in the same tangles. These ambiguities can be removed by defining two separations to be equivalent if they are contained in the same tangles, and then working on the equivalence classes. This talk is about the set of equivalence classes, of which a stong structural statement can be made. That structural statement is similar to a structural statement about related equivalence classes of separations in matroid which Clark and Whittle made in 2013.

Ganglions on Directed Graphs

Thursday 14.11 at 14:00 in room 716

Roman Rabinovich
TU Berlin

We present our ongoing work about generalisations of the concept o tangles to directed graphs. J. Erde describes directed blockages, another variant of tangles, that allow for a min-max theorem. In a yet unpublished paper by A. Giannopoulou, K.-i. Kawarabayashi, S. Kreutzer and O-j. Kwon, they present tangles that correspond to directed treewidth. We introduce several versions of ganglions - tangles that are or should be suited for DAG-width and Kelly-width and show a duality theorem for ganglions and the non-monotone version of DAG-width. This is a first structural characterisation of the class of non-monotone DAG-width.

This is what a ganglion looks like: https://en.wikipedia.org/wiki/Ganglion#/media/File:Ganglion_high_mag.jpg.

This is what a ganglion looks like: https://en.wikipedia.org/wiki/Ganglion#/media/File:Ganglion_high_mag.jpg.

Majority Colorings of Sparse Digraphs

Wednesday 13.11 at 14:00 in room 716

Raphael Steiner
TU Berlin

A majority coloring of a directed graph is a vertex-coloring in which every vertex has the same color as at most half of its out-neighbors.

Kreutzer, Oum, Seymour, van der Zypen and Wood proved that every digraph has a majority 4-coloring and conjectured that every digraph admits a majority 3-coloring.

We verify this conjecture for digraphs with chromatic number at most 6 or dichromatic number at most 3. We obtain analogous results for list coloring: We show that every digraph with list chromatic number at most 6 or list dichromatic number at most 3 is majority 3-choosable. We deduce that digraphs with maximum out-degree at most 4 or maximum degree at most 7 are majority 3-choosable.

On the way to these results we investigate digraphs admitting a majority 2-coloring. We show that every digraph without odd directed cycles is majority 2-choosable. We answer an open question posed by Kreutzer et al. negatively, by showing that deciding whether a given digraph is majority 2-colorable is NP-complete.

Finally we deal with a fractional relaxation of majority coloring proposed by Kreutzer et al. and show that every digraph has a fractional majority 3.9602-coloring. We show that every digraph D with sufficiently large minimum out-degree has a fractional majority-(2+ε)-coloring.

Kreutzer, Oum, Seymour, van der Zypen and Wood proved that every digraph has a majority 4-coloring and conjectured that every digraph admits a majority 3-coloring.

We verify this conjecture for digraphs with chromatic number at most 6 or dichromatic number at most 3. We obtain analogous results for list coloring: We show that every digraph with list chromatic number at most 6 or list dichromatic number at most 3 is majority 3-choosable. We deduce that digraphs with maximum out-degree at most 4 or maximum degree at most 7 are majority 3-choosable.

On the way to these results we investigate digraphs admitting a majority 2-coloring. We show that every digraph without odd directed cycles is majority 2-choosable. We answer an open question posed by Kreutzer et al. negatively, by showing that deciding whether a given digraph is majority 2-colorable is NP-complete.

Finally we deal with a fractional relaxation of majority coloring proposed by Kreutzer et al. and show that every digraph has a fractional majority 3.9602-coloring. We show that every digraph D with sufficiently large minimum out-degree has a fractional majority-(2+ε)-coloring.

What is a 'directed tree'?

Wednesday 30.10 at 14:00 in room 716

Sebastian Wiederrecht
TU Berlin

Treewidth is a graph invariant generalising acyclicity, or tree-likeness, of graphs in a way that can be used to obtain many nice structural and algorithmic results. The great success of treewidth has inspired many generalisations of its base ideas to other combinatorial structures like hypergraphs, directed graphs and matroids.

We explore the connection between directed treewidth and hypertree-width and give answers to the question in what way directed treewidth generalises acyclicity in digraphs. To do this we provide characterisations of strongly connected digraphs of directed treewidth one, a class that can be seen as the directed version of trees.

We explore the connection between directed treewidth and hypertree-width and give answers to the question in what way directed treewidth generalises acyclicity in digraphs. To do this we provide characterisations of strongly connected digraphs of directed treewidth one, a class that can be seen as the directed version of trees.

A Polynomial Kernel for Funnel Arc Deletion Set

Wednesday 09.10 at 14:00 in room 716

Marcelo Garlet Millani
TU Berlin

In Directed Feedback Arc Set (DFAS) we search for a set of at most k arcs which intersect every cycle in the input digraph.

It is a well-know open problem in parameterized complexity to decide if DFAS admits a kernel of polynomial size.

We consider C-Arc Deletion Set (C-ADS), a variant of DFAS where we want to remove at most k arcs from the input digraph in order to turn it into a digraph of a class C.

In this work, we choose C to be the class of funnels. Funnel-ADS is NP-hard even if the input is a DAG, but is fixed-parameter tractable with respect to k.

So far no polynomial kernels for this problem were known. Our main result is a kernel for Funnel-ADS with O(k^6) many vertices and O(k^7) many arcs, computable in linear time.

It is a well-know open problem in parameterized complexity to decide if DFAS admits a kernel of polynomial size.

We consider C-Arc Deletion Set (C-ADS), a variant of DFAS where we want to remove at most k arcs from the input digraph in order to turn it into a digraph of a class C.

In this work, we choose C to be the class of funnels. Funnel-ADS is NP-hard even if the input is a DAG, but is fixed-parameter tractable with respect to k.

So far no polynomial kernels for this problem were known. Our main result is a kernel for Funnel-ADS with O(k^6) many vertices and O(k^7) many arcs, computable in linear time.

Summer term 2019

Towards a Characterisation of Kőnig Graphs

Wednesday 02.10 at 14:00 in room 716

Maximilian Gorsky
TU Berlin

In 2011 Guenin and Thomas gave an excluded minor characterisation of the class of digraphs in which, for every subdigraph, the size of a maximum cycle packing is equal to the size of a feedback vertex set. To study this property, they lifted it to matching covered graphs and proved an excluded matching minor characterization for braces which satisfy the property.

We name this property Kőnig and expand its study to general matching covered graphs.

We show that the Kőnig property is closed under taking matching minors and conformal minors. This then allows us to conclude that this property implies being Pfaffian and solid. Beyond this, we are able to prove that tight cut contractions preserve this property for some special graph classes. In the reverse direction, we prove that, should the tight cut contractions of a graph be Kőnig, then the graph itself is Kőnig.

Finally, as a consequence of the above, we are able to characterize the class of planar Kőnig graphs as being exactly the planar solid graphs, which consists of all planar, bipartite, matching covered graphs and odd wheels.

In the talk, we will focus mainly on the results concerning tight cut contractions.

We name this property Kőnig and expand its study to general matching covered graphs.

We show that the Kőnig property is closed under taking matching minors and conformal minors. This then allows us to conclude that this property implies being Pfaffian and solid. Beyond this, we are able to prove that tight cut contractions preserve this property for some special graph classes. In the reverse direction, we prove that, should the tight cut contractions of a graph be Kőnig, then the graph itself is Kőnig.

Finally, as a consequence of the above, we are able to characterize the class of planar Kőnig graphs as being exactly the planar solid graphs, which consists of all planar, bipartite, matching covered graphs and odd wheels.

In the talk, we will focus mainly on the results concerning tight cut contractions.

Graphs without long ladder minors

Wednesday 25.09 at 14:00 in room 716

Piotr Micek
Jagiellonian University, Kraków

A ladder of order k is a grid graph of size 2 by k. We present a qualitative structure theorem for graphs without long ladder minors. Such a characterization is not a precise description but instead, it shows that the size of the largest ladder minor is tied to some structural parameter of the graph, i.e. the minimal number of colors in a 2-connectedly centered coloring.

There are many examples of theorems of similar flavor, including the Graph Structure Theorem and the Grid Theorem by Robertson and Seymour. As a corollary we get that for every k, if a 3-connected graph contains sufficiently many disjoint models of a ladder of order k, then the graph contains a model of a ladder of order k+1. We will discuss our motivation for a project on poset dimension.

Joint work with Tony Huynh, Gwenaël Joret, Michał Seweryn, and Paul Wollan.

There are many examples of theorems of similar flavor, including the Graph Structure Theorem and the Grid Theorem by Robertson and Seymour. As a corollary we get that for every k, if a 3-connected graph contains sufficiently many disjoint models of a ladder of order k, then the graph contains a model of a ladder of order k+1. We will discuss our motivation for a project on poset dimension.

Joint work with Tony Huynh, Gwenaël Joret, Michał Seweryn, and Paul Wollan.

Wednesday 18.09 at 14:00 in room 716

Meike Hatzel
TU Berlin

We prove a recent conjecture of Beisegel et al. that for every positive integer k, every graph containing an induced P_k also contains an avoidable P_k.

Avoidability generalises the notion of simpliciality best known in the context of chordal graphs.

The conjecture was only established for k ∈ {1,2} (Ohtsuki et al. 1976, and Beisegel et al. 2019, respectively).

Our result also implies a result of Chvátal et al. 2002, which assumed cycle restrictions.

We provide a constructive and elementary proof, relying on a single trick regarding the induction hypothesis.

In the line of previous works, we discuss conditions for multiple avoidable paths to exist.

Avoidability generalises the notion of simpliciality best known in the context of chordal graphs.

The conjecture was only established for k ∈ {1,2} (Ohtsuki et al. 1976, and Beisegel et al. 2019, respectively).

Our result also implies a result of Chvátal et al. 2002, which assumed cycle restrictions.

We provide a constructive and elementary proof, relying on a single trick regarding the induction hypothesis.

In the line of previous works, we discuss conditions for multiple avoidable paths to exist.

Progress on the Ubiquity Conjecture

Wednesday 11.09 at 14:00 in room 716

Karl Heuer
TU Berlin

A classic result of R. Halin about infinite graphs says the following: If a graph G contains n disjoint rays, i.e., one-way infinite paths, as subgraphs for every natural number n, then G already contains infinitely many disjoint rays as subgraphs.

While the above statement trivially remains true if we ask for any finite graph H instead of a ray, it is not true for arbitrary infinite graphs instead of rays.

So let us define the following: A graph G is called ubiquitous w.r.t. the subgraph relation if any infinite graph containing n disjoint copies of G as subgraphs for every natural number n also contains infinitely many disjoint copies of G as subgraphs.

Similarly, we define being ubiquitous w.r.t. other relations between graphs, such as the minor or topological minor relation.

Probably one of the most fundamental conjectures about infinite graphs is the following one due to T. Andreae, called the Ubiquity Conjecture.

Conjecture: Every locally finite connected graph is ubiquitous with respect to the minor relation.

In a series of four papers, partially still in preparation, we have made progress on the Ubiquity Conjecture.

This includes sufficient conditions for a graph to be ubiquitous with respect to the minor relation, for example being countable and having bounded tree-width.

Moreover, we proved that all trees - irrespective of their cardinality - are ubiquitous w.r.t. the topological minor relation.

In this talk, I will first give an overview about the Ubiquity Conjecture and explain how ends of graphs are related to it. Then I will discuss some of our results and the involved proof strategies.

This talk is based on joined work with N. Bowler, C. Elbracht, J. Erde, J.P. Gollin, M. Pitz and M. Teegen.

While the above statement trivially remains true if we ask for any finite graph H instead of a ray, it is not true for arbitrary infinite graphs instead of rays.

So let us define the following: A graph G is called ubiquitous w.r.t. the subgraph relation if any infinite graph containing n disjoint copies of G as subgraphs for every natural number n also contains infinitely many disjoint copies of G as subgraphs.

Similarly, we define being ubiquitous w.r.t. other relations between graphs, such as the minor or topological minor relation.

Probably one of the most fundamental conjectures about infinite graphs is the following one due to T. Andreae, called the Ubiquity Conjecture.

Conjecture: Every locally finite connected graph is ubiquitous with respect to the minor relation.

In a series of four papers, partially still in preparation, we have made progress on the Ubiquity Conjecture.

This includes sufficient conditions for a graph to be ubiquitous with respect to the minor relation, for example being countable and having bounded tree-width.

Moreover, we proved that all trees - irrespective of their cardinality - are ubiquitous w.r.t. the topological minor relation.

In this talk, I will first give an overview about the Ubiquity Conjecture and explain how ends of graphs are related to it. Then I will discuss some of our results and the involved proof strategies.

This talk is based on joined work with N. Bowler, C. Elbracht, J. Erde, J.P. Gollin, M. Pitz and M. Teegen.

Packing directed circuits quarter-integrally

Wednesday 14.08 at 14:00 in room 716

Irene Muzi
TU Berlin

The Erdős-Pósa theorem states that every undirected graph that does not admit a family of k vertex-disjoint cycles contains a feedback vertex set (a set of vertices hitting all cycles in the graph) of size O(k log k). After being known for long as Younger's conjecture, a similar statement for directed graphs has been proven in 1996 by Reed, Robertson, Seymour, and Thomas. However, in their proof, the dependency of the size of the feedback vertex set on the size of vertex-disjoint cycle packing is not elementary. We show that if we compare the size of a minimum feedback vertex set in a directed graph with quarter-integral cycle packing number, we obtain a polynomial bound. More precisely, we show that if in a directed graph G there is no family of k cycles such that every vertex of G is in at most four of the cycles, then there exists a feedback vertex set in G of size O(k^4).

Abstract separation systems

Wednesday 12.06 at 14:00 in room 716

Nathan Bowler
Hamburg University

I will give an overview of the theory of abstract separation systems, focusing on two main theorems: the duality theorem and the tangle-tree theorem. I will discuss recent progress, focusing particularly on results related to directed graphs.

Computing shrub-depth decompositions

Wednesday 05.06 at 14:00 in room 716

Jakub Gajarsky
TU Berlin

Shrub-depth is a width measure of graphs which plays an important role in study of recently introduced structurally sparse graph classes. We present an algorithm for computing decompositions of graphs of bounded shrub-depth. To the best of our knowledge, this is the first algorithm which computes the decomposition directly, without use of clique-width decompositions and MSO logic. This is a joint work with Stephan Kreutzer.

The Directed Tangle Decomposition Lemma, Part 2

Tuesday 04.06 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.

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.

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.

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 q

_{1}, q_{2}, ... of elements of Q there exist i < j such that q_{i}⩿ q_{j}. 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.

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.

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.

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.

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.

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

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

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