  There are many classical problems in P whose time complexities have not been
improved over the past decades. Recent studies of "Hardness in P" have revealed
that, for several of such problems, the current fastest algorithm is the best
possible under some complexity assumptions. To bypass this difficulty, Fomin et
al. (SODA 2017) introduced the concept of fully polynomial FPT algorithms. For
a problem with the current best time complexity $O(n^c)$, the goal is to design
an algorithm running in $k^{O(1)}n^{c'}$ time for a parameter $k$ and a
constant $c'<c$. In this paper, we investigate the complexity of graph problems
in P parameterized by tree-depth, a graph parameter related to tree-width. We
show that a simple divide-and-conquer method can solve many graph problems,
including Weighted Matching, Negative Cycle Detection, Minimum Weight Cycle,
Replacement Paths, and 2-hop Cover, in $O(\mathrm{td}\cdot m)$ time or
$O(\mathrm{td}\cdot (m+n\log n))$ time, where $\mathrm{td}$ is the tree-depth
of the input graph. Because any graph of tree-width $\mathrm{tw}$ has
tree-depth at most $(\mathrm{tw}+1)\log_2 n$, our algorithms also run in
$O(\mathrm{tw}\cdot m\log n)$ time or $O(\mathrm{tw}\cdot (m+n\log n)\log n)$
time. These results match or improve the previous best algorithms parameterized
by tree-width. Especially, we solve an open problem of fully polynomial FPT
algorithm for Weighted Matching parameterized by tree-width posed by Fomin et
al.
