The first one either produces an arboreal decomposition of width 3k-2 or finds a haven of order k in a digraph D, improving on the original result for arboreal decompositions by Johnson et al. The second algorithm finds, in a digraph of large directed tree-width, a well-linked set of order k with some additional properties. As tools to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices T in FPT time with parameter |T|, a result that we consider to be of its own interest.
--------------------
Join Zoom Meeting
Meeting ID: 527 278 8807
Note: for people outside D1 interested in listening to this talk, please contact Sándor Kisfaludi-Bak at skisfalu@mpi-inf.mpg.de for the password.