## Abstract

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[1]-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(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). 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.

Original language | English |
---|---|

Article number | e21985 |

Pages (from-to) | 485-508 |

Number of pages | 24 |

Journal | Networks |

Volume | 76 |

Issue number | 4 |

Early online date | 6 Oct 2020 |

DOIs | |

Publication status | Published - 1 Dec 2020 |

## Keywords

- above-guarantee parameterization
- capacitated arc routing
- Eulerian extension
- lossy kernelization
- NP-hard problem
- parameterized complexity
- EULERIAN EXTENSION
- ARC
- BOUNDS
- ALGORITHM