  We consider the following problem called the $k$-Chinese Postman Problem
($k$-CPP): given a connected edge-weighted graph $G$ and integers $p$ and $k$,
decide whether there are at least $k$ closed walks such that every edge of $G$
is contained in at least one of them and the total weight of the edges in the
walks is at most $p$? The problem $k$-CPP is NP-complete, and van Bevern et al.
(to appear) and Sorge (2013) asked whether the $k$-CPP is fixed-parameter
tractable when parameterized by $k$. We prove that the $k$-CPP is indeed
fixed-parameter tractable. In fact, we prove a stronger result: the problem
admits a kernel with $O(k^2\log k)$ vertices. We prove that the directed
version of $k$-CPP is NP-complete and ask whether the directed version is
fixed-parameter tractable when parameterized by $k$.
