On (1+ε)-approximate problem kernels for the Rural Postman Problem
share
Given a graph G=(V,E) with edge weights ω E→ N∪{0} and a subset R⊆ E of 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 poly(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^3) 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) and make first steps towards a PSAKS for the parameter c.
READ FULL TEXT