Photo 14.10.19, 23 29 16.jpg

Sebastian Wiederrecht

I'm a PhD student working on graph theory in the group of Stephan Kreutzer at TU Berlin.

Parameterized Algorithms for Directed Modular Width

Many well-known NP-hard algorithmic problems on directed graphs re- sist efficient parametrisations with most known width measures for directed graphs, such as directed treewidth, DAG-width, Kelly-width and many others. While these focus on measuring how close a digraph is to an oriented tree resp. a directed acyclic graph, in this paper, we investigate directed modular width as a parameter, which is closer to the concept of clique-width. We investigate applications of modular decompositions of directed graphs to a wide range of algorithmic problems and derive FPT-algorithms for several well-known digraph-specific NP-hard problems, namely minimum (weight) directed feed- back vertex set, minimum (weight) directed dominating set, digraph colouring, directed Hamiltonian path/cycle, partitioning into paths, (capacitated) vertex- disjoint directed paths, and the directed subgraph homeomorphism problem. The latter yields a polynomial-time algorithm for detecting topological minors in digraphs of bounded directed modular width. Finally we illustrate that also other structural digraph parameters, such as directed pathwidth and the cycle-rank can be computed efficiently using directed modular width as a parameter.

A Note on Directed Treewidth

We characterise digraphs of directed treewidth one in terms of forbidden butterfly minors. Moreover, we show that there is a linear relation between the hypertree-width of the dual of the cycle hypergraph of D, i. e. the hypergraph with vertices V(D) where every hyperedge corresponds to a directed cycle in D, and the directed treewidth of D. Based on this we show that a digraph has directed treewidth one if and only if its cycle hypergraph is a hypertree.

Talk at KOLKOM 2019

A Grid Theorem for Perfect Matching Width of Bipartite Matching Covered Graphs

A connected graph G is called matching covered if every edge of G is contained in a perfect matching. Perfect matching width is a width parameter for matching covered graphs based on a branch decomposition. It was introduced by Norine and intended as a tool for the structural study of matching covered graphs, especially in the context of Pfaffian orientations. Norine conjectured that graphs of high perfect matching width would contain a large grid as a matching minor, similar to the result on treewidth by Robertson and Seymour.
In this paper we obtain the first results on perfect matching width since its introduction. For the restricted case of bipartite graphs, we show that perfect
matching width is equivalent to directed treewidth and thus the Directed Grid Theorem by Kawarabayashi and Kreutzer for directed treewidth implies
Norine’s conjecture.

Talk at WG 2019

Colouring Non-Even Digraphs

A colouring of a digraph as defined by Neumann-Lara in 1982 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.

Talk at Cycles and Colourings 2019