Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4951282 | Journal of Computer and System Sciences | 2017 | 11 Pages |
Abstract
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 â, decide whether D has a closed directed walk containing every arc of R and of weight at most â. Let k be the number of weakly connected components in the subgraph of D induced by R. Sorge et al. [30] asked whether the DRPP is fixed-parameter tractable (FPT) when parameterized by k, i.e., whether there is an algorithm of running time Oâ(f(k)) where f is a function of k only and the Oâ notation suppresses polynomial factors. Using an algebraic approach, we prove that DRPP has a randomized algorithm of running time Oâ(2k) when â is bounded by a polynomial in the number of vertices in D. The same result holds for the undirected version of DRPP.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gregory Gutin, Magnus Wahlström, Anders Yeo,