  In this paper, we propose an algorithm that, given an undirected graph $G$ of
$m$ edges and an integer $k$, computes a graph $G'$ and an integer $k'$ in
$O(k^4 m)$ time such that (1) the size of the graph $G'$ is $O(k^2)$, (2)
$k'\leq k$, and (3) $G$ has a feedback vertex set of size at most $k$ if and
only if $G'$ has a feedback vertex set of size at most $k'$. This is the first
linear-time polynomial-size kernel for Feedback Vertex Set. The size of our
kernel is $2k^2+k$ vertices and $4k^2$ edges, which is smaller than the
previous best of $4k^2$ vertices and $8k^2$ edges. Thus, we improve the size
and the running time simultaneously. We note that under the assumption of
$\mathrm{NP}\not\subseteq\mathrm{coNP}/\mathrm{poly}$, Feedback Vertex Set does
not admit an $O(k^{2-\epsilon})$-size kernel for any $\epsilon>0$.
  Our kernel exploits $k$-submodular relaxation, which is a recently developed
technique for obtaining efficient FPT algorithms for various problems. The dual
of $k$-submodular relaxation of Feedback Vertex Set can be seen as a
half-integral variant of $A$-path packing, and to obtain the linear-time
complexity, we propose an efficient augmenting-path algorithm for this problem.
We believe that this combinatorial algorithm is of independent interest.
  A solver based on the proposed method won first place in the 1st
Parameterized Algorithms and Computational Experiments (PACE) challenge.
