In this talk we discuss recent work to that establishes that the bounds of the Vital Linkage Function is single-exponential. This has immediate impacts on the complexity of the k-Disjoint Paths Problem, Minor Checking, and more generally, the Folio-Problem. We in fact prove something even stronger: It turns out that it is not in fact the number of terminals (or more generally vertices) that matters in these problems, but rather their structure within the graph. Concretely, we show that the Vital Linkage Function is single-exponential only in the bidimensionality of the terminals, whilst the number of terminals contributes only polynomially. A direct consequence of this is an algorithm for the k-Disjoint Paths Problem running in $f(k)n^2$-time, where f(k) is singly exponential in k and doubly exponential in the bidimensionality of k. This derives directly from an algorithm for the Folio-problem we give that has an analogous runtime. Notably these are the first algorithms for these problems in which the function f is explicit. In particular, we give the first explicit bounds for the Vital Linkage Function.
Joint work with Dario Cavallaro, Stephan Kreutzer, Dimitrios Thilikos, and Sebastian Wiederrecht.
From February 10 to 12, 2025, the second week of the IBS-DIMAG Winter School on Graph Minors took place at IBS. This week, Maximilian Gorsky from the IBS Discrete Mathematics Group gave lectures on classifying society using a structure called transaction meshes.
The IBS-DIMAG Winter School on Graph Minors is taking place at IBS every Monday, Tuesday, and Wednesday over a three-week period, beginning on February 3, 2025. Sebastian Wiederrecht (KAIST) and Maximilian Gorsky (IBS Discrete Mathematics Group) are giving lectures. In the first week, the topics covered included the two-paths theorem, the flat wall theorem, and various results on societies, transactions, and vortices.
The IBS Discrete Mathematics Group welcomes Dr. Maximilian Gorsky, a new research fellow at the IBS Discrete Mathematics Group, from November 1, 2024. He received his Ph.D. from Technische Universität Berlin under the supervision of Prof. Stephan Kreutzer. He is interested in structural graph theory, (structural) matching theory, and structural digraph theory.
A family $\mathcal F$ of (di)graphs is said to have the half- or quarter-integral Erdős-Pósa property if, for any integer $k$ and any (di)graph $G$, there either exist $k$ copies of graphs in $\mathcal F$ within $G$ such that any vertex of $G$ is contained in at most 2, respectively at most 4, of these copies, or there exists a vertex set $A$ of size at most $f(k)$ such that $G – A$ contains no copies of graphs in $\mathcal F$. Very recently we showed that even dicycles have the quarter-integral Erdős-Pósa property [STOC’24] via the proof of a structure theorem for digraphs without large packings of even dicycles.
In this talk we discuss our current effort to improve this approach towards the half-integral Erdős-Pósa property, which would be best possible, as even dicycles do not have the integral Erdős-Pósa property. Complementing the talk given by Sebastian Wiederrecht in this seminar regarding our initial result, we also shine a light on some of the particulars of the embedding we use in lieu of flatness and how this helps us to move even dicycles through the digraph. In the process of this, we highlight the parts of the proof that initially caused the result to be quarter-integral.
(This is joint work with Ken-ichi Kawarabayashi, Stephan Kreutzer, and Sebastian Wiederrecht.)
