top of page

Photo 10.05.22, 13 11 22.jpg

Sebastian Wiederrecht

I'm an Assistant Professor for Theoretical Computer Science at the School of Computing at KAIST in Daejeon, South Korea.

My main field of interest is (algorithmic) structural graph theory.

Here you can find my CV.

(last updated November 2023)

We prove that directed cycles of even length have the quarter-integral Erdos-Posa property.

Excluding a graph (or a family of graphs) under a fixed containment relation can yield graph classes with very particular properties. Such properties can often be exploited for the design of efficient algorithms on the resulting graph classes. In this talk we survey several such structural parametrizations for the case of the Maximum Independent Set Problem, present new developments and open problems.

We provide a full delineation of the half-integrality of the Erdos-Posa property for minors for graphs that are shallow-vortex-minors and Kuratowski connected.

Universal Obstructions in Graph Minors

A general structure theorem containing of both planar- and K_3,3-matching-minor-free classes of bipartite graphs.

We prove an analog of the celebrated grid-theorem for a parameter that asks for tree-decompositions where all torsos are of bounded genus after deleting a bounded size set of vertices.
This result is complemented by a sharp complexity-dichotomy for counting perfect matchings in minor-closed families of graphs.

DAGwidth Duality

Digraph Minors And Matching Theory

bottom of page