TY - JOUR

T1 - On approximate data reduction for the Rural Postman Problem: Theory and experiments

AU - van Bevern, René

AU - Fluschnik, Till

AU - Tsidulko, Oxana Yu

N1 - Publisher Copyright: © 2020 Wiley Periodicals LLC

PY - 2020/12/1

Y1 - 2020/12/1

N2 - 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(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.

AB - 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(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.

KW - above-guarantee parameterization

KW - capacitated arc routing

KW - Eulerian extension

KW - lossy kernelization

KW - NP-hard problem

KW - parameterized complexity

KW - EULERIAN EXTENSION

KW - ARC

KW - BOUNDS

KW - ALGORITHM

UR - http://www.scopus.com/inward/record.url?scp=85084978725&partnerID=8YFLogxK

U2 - 10.1002/net.21985

DO - 10.1002/net.21985

M3 - Article

AN - SCOPUS:85084978725

VL - 76

SP - 485

EP - 508

JO - Networks

JF - Networks

SN - 0028-3045

IS - 4

M1 - e21985

ER -