  In the NP-hard Edge Dominating Set problem (EDS) we are given a graph
$G=(V,E)$ and an integer $k$, and need to determine whether there is a set
$F\subseteq E$ of at most $k$ edges that are incident with all (other) edges of
$G$. It is known that this problem is fixed-parameter tractable and admits a
polynomial kernel when parameterized by $k$. A caveat for this parameter is
that it needs to be large, i.e., at least equal to half the size of a maximum
matching of $G$, for instances not to be trivially negative. Motivated by this,
we study the existence of polynomial kernels for EDS when parameterized by
structural parameters that may be much smaller than $k$.
  Unfortunately, at first glance this looks rather hopeless: Even when
parameterized by the deletion distance to a disjoint union of paths $P_3$ of
length two there is no polynomial kernelization (under standard assumptions),
ruling out polynomial kernels for many smaller parameters like the feedback
vertex set size. In contrast, somewhat surprisingly, there is a polynomial
kernelization for deletion distance to a disjoint union of paths $P_5$ of
length four. As our main result, we fully classify for all finite sets
$\mathcal{H}$ of graphs, whether a kernel size polynomial in $|X|$ is possible
when given $X$ such that each connected component of $G-X$ is isomorphic to a
graph in $\mathcal{H}$.
