Given an undirected graph with edge weights and a subset R of its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges of R. We prove that RPP is WK-complete parameterized by the number and weight d of edges traversed additionally to the required ones. Thus RPP instances cannot be polynomial-time compressed to instances of size polynomial in d unless the polynomial-time hierarchy collapses. 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(n3) 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 experimentally evaluate it on wide-spread benchmark data sets as well as on two real snow plowing instances from Berlin. We also make first steps toward a PSAKS for the parameter c.
Предметные области OECD FOS+WOS
- 1.02 КОМПЬЮТЕРНЫЕ И ИНФОРМАЦИОННЫЕ НАУКИ
- 5.02.PE ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И НАУКА УПРАВЛЕНИЯ