8 papers
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 th entry of Robertson and Seymour's Graph Minors Se…
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…
On non-planar, cycle-conformal graphs
Maximilian Gorsky, Clemens Kuske
A graph is called matching covered if all of its edges are contained in some perfect matching of . Furthermore, a cycle is called conformal if has…
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…
Catching Rats in -minor-free Graphs
Maximilian Gorsky, Giannos Stamoulis, Dimitrios M. Thilikos +1
We show that every -minor-free graph that also excludes a -grid as a minor has treewidth/branchwidth bounded from above by a function that is linear in $k…