Name
Abstract | ||
|---|---|---|
Given an undirected graph with edge weights and a subsetRof its edges, the Rural Postman Problem (RPP) is to find a closed walk of minimum total weight containing all edges ofR. We prove that RPP is WK[1]-complete parameterized by the number and weightdof edges traversed additionally to the required ones. Thus RPP instances cannot be polynomial-time compressed to instances of size polynomial indunless the polynomial-time hierarchy collapses. In contrast, denoting byb <= 2dthe number of vertices incident to an odd number of edges ofRand byc <= dthe number of connected components formed by the edges inR, we show how to reduce any RPP instanceIto an RPP instanceI(')with2b + O(c/epsilon)vertices inO(n(3))time so that any alpha-approximate solution forI(')gives an alpha(1 + epsilon)-approximate solution forI, for any alpha >= 1and epsilon > 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 parameterc. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1002/net.21985 | NETWORKS |
Keywords | DocType | Volume |
above-guarantee parameterization,capacitated arc routing,Eulerian extension,lossy kernelization,NP-hard problem,parameterized complexity | Journal | 76.0 |
Issue | ISSN | Citations |
4.0 | 0028-3045 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| René van Bevern | 1 | 126 | 19.33 |
| Till Fluschnik | 2 | 26 | 7.14 |
| O. Yu. Tsidulko | 3 | 1 | 2.85 |