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

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 cost $d$ of edges traversed additionally to the required ones. Thus, in particular, 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\le 2d$ the number of vertices incident to an odd number of edges of $R$ and by $c\le 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^{\prime }$ with $2b+O(c/\epsilon )$ vertices in $O(n^3)$ time so that any $\alpha$-approximate solution for $I^{\prime }$ gives an $\alpha (1+\epsilon )$-approximate solution for $I$, for any $\alpha \ge 1$ and $\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. On instances with few connected components, the number of vertices and required edges is reduced to about $50\%$ at a $1\%$ solution quality loss. We also make first steps towards a PSAKS for the parameter $c$.

arXiv commentAdded plot, definition of parameterized optimization problem, argument against PSAKS for parameter b

References in corpus (7)

• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
• Constant-factor approximations for Capacitated Arc Routing without triangle inequality
• A parameterized approximation algorithm for the mixed and windy Capacitated Arc Routing Problem: theory and experiments
• Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels
• Optimal-size problem kernels for $d$-Hitting Set in linear time and space
• Parameterized algorithms and data reduction for the short secluded $s$-$t$-path problem
• Polynomial-Time Data Reduction for Weighted Problems Beyond Additive Goal Functions

Cited by in corpus (6)

• A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
• Optimal-size problem kernels for $d$-Hitting Set in linear time and space
• The Hierarchical Chinese Postman Problem: the slightest disorder makes it hard, yet disconnectedness is manageable
• Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
• Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU
• Polynomial-Time Data Reduction for Weighted Problems Beyond Additive Goal Functions