Polynomial kernel for immersion hitting in tournaments
share
For a fixed simple digraph H without isolated vertices, we consider the problem of deleting arcs from a given tournament to get a digraph which does not contain H as an immersion. We prove that for every H, this problem admits a polynomial kernel when parameterized by the number of deleted arcs. The degree of the bound on the kernel size depends on H.
READ FULL TEXT