Parameterized Rural Postman Problem

摘要: The Directed Rural Postman Problem (DRPP) can be formulated as follows: given a strongly connected directed multigraph $D=(V,A)$ with nonnegative integral weights on the arcs, subset $R$ of $A$ and integer $\ell$, decide whether $D$ has closed walk containing every arc total weight at most $\ell$. Let $k$ number weakly components in subgraph induced by $R$. Sorge et al. (2012) ask DRPP is fixed-parameter tractable (FPT) when parameterized $k$, i.e., there an algorithm running time $O^*(f(k))$ where $f$ function only $O^*$ notation suppresses polynomial factors. note that this question significant practical relevance been open for more than thirty years. Using algebraic approach, we prove randomized $O^*(2^k)$ $\ell$ bounded vertices $D$. We also show same result holds undirected version DRPP, multigraph.