Skip to content

Tuesday 16:30 – William Lochet

Disjoint paths on dense graphs

In this talk we will see the proof that the \(k\) edge disjoint paths problem can be solved in polynomial time on graphs with minimum degree \(\alpha \cdot n\) provided \(k\) is small enough (but still linear in \(n\)). In particular this implies a linear kernel on the class of graphs with linear minimum degree, which is not possible on general graphs.
This is based on a joint work with Lokshtanov, Saurabh and Zehavi that appeared in STACS 2020.