Sebastian Wiederrecht

A Dichotomy for Terminal Cyclability

Matthias Bentert, Dario Cavallaro, Sebastian Wiederrecht

Given an undirected graph $G$ and a set $R \subseteq V (G)$ of terminals, Terminal Cyclability asks whether $G$ contains a simple cycle visiting every vertex of $R$ . We establish a…

Hitting Minors: Stronger Lower Bounds

Jongseo Lee, Roohani Sharma, Sebastian Wiederrecht

For a fixed finite collection of graphs $F$ , the $F$ -Minor-Free Deletion problem asks, given a graph $G$ and an integer $k$ , whether there is a set $S\subseteq…

Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting

Kyungjin Cho, Eunjin Oh, Sebastian Wiederrecht

We study the \textsc{ $k$ -Disjoint Paths} problem on a graph embedded on a surface with bounded Euler genus. Given a graph $G$ with $n$ vertices and $k$ vertex pairs embedded on a s…

The Erdős-Pósa Property for Colorful Minors

Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht

A colorful graph relation enhances the minor relation by merging color sets along contractions and by allowing the removal of colors; it generalizes rooted minors and models proble…

A relaxation of the Bermond-Thomassen conjecture

Stéphane Bessy, Matthijs Muis, Jean-Sébastien Sereni +2

The well-known Bermond-Thomassen conjecture states that every digraph of minimum out-degree at least $2 k - 1$ contains $k$ vertex-disjoint directed cycles. Despite being posed in 198…

A directed flat wall theorem excluding a crossrow grid

Meike Hatzel, Ken-ichi Kawarabayashi, Stephan Kreutzer +1

The graph minor project contains the most influential results in recent undirected graph theory research. There has been progress in recent years in generalising some of their resu…

Spanning Paths and Cycles: Structural Limitations of the Irrelevant Vertex Technique

Dimitrios M. Thilikos, Sebastian Wiederrecht

The Irrelevant Vertex Technique is one of the cornerstones of algorithmic graph theory, underlying Robertson and Seymour's algorithm for \textsc{Disjoint Paths} and much of the alg…

An Erdős-Pósa theorem for cycles and faces of distinct lengths

J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel +6

We show that for every $k \in N$ , every graph $G$ contains $k$ vertex-disjoint cycles of different lengths, or there exists a set $X \subseteq V (G)$ with $|X| \in \mathcal…

Optimal Bounds for the k-Disjoint Paths Problem

Dario Cavallaro, Maximilian Gorsky, Stephan Kreutzer +2

The Graph Minors Series of Robertson and Seymour forms the foundation of algorithmic structural graph theory, yielding fixed-parameter algorithms for problems such as Disjoint Path…

Quickly excluding an annotated planar graph

Maximilian Gorsky, Evangelos Protopapas, Sebastian Wiederrecht

We provide proofs certifying that the structure theorem for vertex sets of bounded bidimensionality holds with polynomial bounds. The bidimensionality of vertex sets is a common ge…

The price of homogeneity is polynomial

Maximilian Gorsky, Michał T. Seweryn, Sebastian Wiederrecht

We provide explicit and polynomial bounds for the Homogeneous Wall Lemma which occurred for the first time implicitly in the $13$ th entry of Robertson and Seymour's Graph Minors Se…

Excluding surfaces as minors in graphs

Dimitrios M. Thilikos, Sebastian Wiederrecht

The Graph Minors Structure Theorem (GMST) of Robertson and Seymour states that for every graph $H,$ any $H$ -minor-free graph $G$ has a tree-decomposition of bounded adhesion such t…

Odd-Cycle-Packing-treewidth: On the Maximum Independent Set problem in odd-minor-free graph classes

Mujin Choi, Maximilian Gorsky, Gunwoo Kim +2

We introduce the tree-decomposition-based graph parameter Odd-Cycle-Packing-treewidth (OCP-tw) as a width parameter that asks to decompose a given graph into pieces of bounded odd…

Excluding a Ladder as an Induced Minor in Graphs Without Induced Stars

Mujin Choi, Sebastian Wiederrecht

A $k$ -ladder is the graph obtained from two disjoint paths, each with $k$ vertices, by joining the $i$ th vertices of both paths with an edge for each $i \in {1, \dots, k}$ . In this…

Unavoidable butterfly minors in digraphs of large cycle rank

Meike Hatzel, O-joung Kwon, Myounghwan Lee +1

Cycle rank is one of the depth parameters for digraphs introduced by Eggan in 1963. We show that there exists a function $f : N \to N$ such that every digraph of cyc…

Colorful Minors

Evangelos Protopapas, Dimitrios M. Thilikos, Sebastian Wiederrecht

We introduce the notion of colorful minors, which generalizes the classical concept of rooted minors in graphs. A $q$ -colorful graph= is defined as a pair $(G, χ),$ where $G$ is a…

The Local Structure Theorem for Graph Minors with finite index

Christophe Paul, Evangelos Protopapas, Dimitrios M. Thilikos +1

The Local Structure Theorem (LST) for Graph Minors roughly states that for every $H$ -minor-free graph $G$ that contains a sufficiently large wall $W$ , there is a small vertex subse…

Excluding Pinched Spheres

Laure Morelle, Evangelos Protopapas, Dimitrios M. Thilikos +1

The pinched sphere is the pseudo-surface $S_{0}^{\circ}$ obtained by identifying two distinct points of the sphere. We provide a structural characterization of graphs exclud…

Excluding an induced wheel minor in graphs without large induced stars

Mujin Choi, Claire Hilaire, Martin Milanič +1

We study a conjecture due to Dallard, Krnc, Kwon, Milanič, Munaro, Štorgel, and Wiederrecht stating that for any positive integer $d$ and any planar graph $H$ , the class of all $K_…

The Erdős-Pósa property for circle graphs as vertex-minors

Rutger Campbell, J. Pascal Gollin, Meike Hatzel +4

We prove that for any circle graph $H$ with at least one edge and for any positive integer $k$ , there exists an integer $t = t (k, H)$ so that every graph $G$ either has a vertex-minor…

Catching Rats in $H$ -minor-free Graphs

Maximilian Gorsky, Giannos Stamoulis, Dimitrios M. Thilikos +1

We show that every $H$ -minor-free graph that also excludes a $(k \times k)$ -grid as a minor has treewidth/branchwidth bounded from above by a function $f (t, k)$ that is linear in $k…

On graphs with a simple structure of maximal cliques

J. Pascal Gollin, Meike Hatzel, Sebastian Wiederrecht

We say that a hereditary graph class $G$ is \emph{clique-sparse} if there is a constant $k = k (G)$ such that for every graph $G \in G$ , every vertex of $G…