## René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko.
On (1+ɛ)-approximate problem kernels for the Rural
Postman Problem.
In *Proceedings of the International Conference Mathematical
Optimization Theory and Operations Research (MOTOR'19), Ekaterinburg, Russian
Federation*, Lecture Notes in Computer Science, 2019.
Accepted for publication.

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[1]-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 |
http ]
Back

*This file was generated by
bibtex2html 1.98.*