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.