MeikeHatzel Archives - Discrete Mathematics Group

The IBS discrete mathematics group welcomes Dr. Meike Hatzel, a new research fellow at the IBS discrete mathematics group from August 1, 2024. She received his Ph.D. from the Technische Universität Berlin under the supervision of Prof. Stephan Kreutzer. She is interested in graph theory, in particular the structure theory of directed graphs.

February 22, 2023July 6, 2024

Meike Hatzel gave a talk on the parameterized complexity of finding a vertex cut of small size separating three pairs of terminals on a directed graph at the Discrete Math Seminar

On February 21, 2023, Meike Hatzel from the National Institute of Informatics in Tokyo gave a talk at the Discrete Math Seminar on the parameterized complexity of the Directed Multicut problem with three pairs of terminals, which is to find a vertex cut of size at most k separating three pairs of terminals. The title of her talk was “Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation“.

Meike Hatzel, Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation

We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$ , pairs of vertices (called terminals) $(s_{1}, t_{1})$ , $(s_{2}, t_{2})$ , and $(s_{3}, t_{3})$ , and an integer $k$ , asks to find a set of at most $k$ non-terminal vertices in $G$ that intersect all $s_{1} t_{1}$ -paths, all $s_{2} t_{2}$ -paths, and all $s_{3} t_{3}$ -paths. The parameterized complexity of this case has been open since Chitnis, Cygan, Hajiaghayi, and Marx proved fixed-parameter tractability of the 2-terminal-pairs case at SODA 2012, and Pilipczuk and Wahlström proved the W[1]-hardness of the 4-terminal-pairs case at SODA 2016.

On the technical side, we use two recent developments in parameterized algorithms. Using the technique of directed flow-augmentation [Kim, Kratsch, Pilipczuk, Wahlström, STOC 2022] we cast the problem as a CSP problem with few variables and constraints over a large ordered domain. We observe that this problem can be in turn encoded as an FO model-checking task over a structure consisting of a few 0-1 matrices. We look at this problem through the lenses of twin-width, a recently introduced structural parameter [Bonnet, Kim, Thomassé, Watrigant, FOCS 2020]: By a recent characterization [Bonnet, Giocanti, Ossona de Mendez, Simon, Thomassé, Toruńczyk, STOC 2022] the said FO model-checking task can be done in FPT time if the said matrices have bounded grid rank. To complete the proof, we show an irrelevant vertex rule: If any of the matrices in the said encoding has a large grid minor, a vertex corresponding to the “middle” box in the grid minor can be proclaimed irrelevant — not contained in the sought solution — and thus reduced.

November 11, 2020July 6, 2024

Meike Hatzel gave a talk on finding a bramble of small order and small size at the Virtual Discrete Math Colloquium

On November 11, 2020, Meike Hatzel from Technische Universität Berlin gave an online talk on the existence of a bramble of small order and small size in a graph of tree-width k at the Virtual Discrete Math Colloquium. The title of her talk was “Constant congestion bramble“.

Meike Hatzel, Constant congestion bramble

In this talk I will present a small result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk, Paweł 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}) \cap V (H_{2}) \neq \emptyset$ 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 $δ \in (0, \frac{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 $\tilde{Ω} (k^{1 / 2})$ and size $\tilde{O} (k^{3 / 2})$ . ( $\tilde{Ω}$ and $\tilde{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 $\tilde{Ω} (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 $δ \in (0, \frac{1}{2}]$ , every graph $G$ of treewidth at least $k$ contains a bramble of order $\tilde{Ω} (k^{1 / 2 + δ})$ and size $2^{\tilde{O} (k^{2 δ})}$ .

Tag: MeikeHatzel

Meike Hatzel, TBA

Welcome Meike Hatzel, a new member of the IBS Discrete Mathematics Group

Meike Hatzel gave a talk on the parameterized complexity of finding a vertex cut of small size separating three pairs of terminals on a directed graph at the Discrete Math Seminar

Meike Hatzel, Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation

Meike Hatzel gave a talk on finding a bramble of small order and small size at the Virtual Discrete Math Colloquium

Meike Hatzel, Constant congestion bramble

Pascal Schweitzer

Caleb McFarland

Niloufar Fuladi