Given a graph G=(V,E) with edge weights ω:E→N∪0 and a subset R⊆E of required edges, the Rural Postman Problem (RPP) is to find a closed walk W* of minimum weight ω(W*) containing all edges of R. We prove that RPP is WK-complete parameterized by the number and cost d=ω(W^*)-ω(R)+|W*|-|R| of edges traversed additionally to the required ones, that is, presumably cannot be polynomial-time reduced to solving instances of size polynomial in d. In contrast, denoting by b≤2d the number of vertices incident to an odd number of edges of R and by c≤d the number of connected components formed by the edges in R, we show how to reduce any RPP instance I to an RPP instance I' with 2b+O(c/ε) vertices in O(n³) time so that any α-approximate solution for I' gives an α(1+ε)-approximate solution for I, for any α≥1 and ε>0. That is, we provide a polynomial-size approximate kernelization scheme (PSAKS). We make first steps towards a PSAKS for the parameter c.
[ bib | DOI | source code | http ] Back
This file was generated by bibtex2html 1.99.