Summary: In the Directed Rural Postman Problem (DRPP), given a strongly connected directed multigraph \(D = (V, A)\) with nonnegative integral weights on the arcs, a subset \(R\) of required arcs and a nonnegative integer \(\ell\), decide whether \(D\) has a closed directed walk containing every arc of \(R\) and of weight at most \(\ell\). Let \(k\) be the number of weakly connected components in the subgraph of \(D\) induced by \(R\). M. Sorge et al. [J. Discrete Algorithms 16, 12–33 (2012; Zbl 1255.68076)] asked whether the DRPP is fixed-parameter tractable (FPT) when parameterized by \(k\), i.e., whether there is an algorithm of running time \(O^\ast(f(k))\) where \(f\) is a function of \(k\) only and the \(O^\ast\) notation suppresses polynomial factors. Using an algebraic approach, we prove that DRPP has a randomized algorithm of running time \(O^\ast(2^k)\) when \(\ell\) is bounded by a polynomial in the number of vertices in \(D\). The same result holds for the undirected version of DRPP.