Preprint Poster Slides Code doi abstract bibtex

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.

@article{BFT20b, author = {Ren{\'{e}} van Bevern and Till Fluschnik and Oxana Tsidulko}, title = {On approximate data reduction for the {Rural Postman Problem}: Theory and experiments}, year = {2020}, date = {2020-11-02}, journal = {Networks}, url_Preprint = {https://arxiv.org/abs/1812.10131}, url_Poster = {https://figshare.com/articles/poster/On_approximate_data_reduction_for_the_Rural_Postman_Problem/13058969}, url_Slides = {https://www.researchgate.net/publication/348297308_On_approximate_approximate_data_reduction_for_the_Rural_Postman_Problem_Theory_and_Experiments}, doi = {10.1002/net.21985}, volume = 76, number = 4, pages = {485-508}, url_Code = {https://gitlab.com/rvb/rpp-psaks}, abstract = {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.} }

Downloads: 0