4 Citations (Scopus)

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

Original languageEnglish
Article numbere21985
Pages (from-to)485-508
Number of pages24
JournalNetworks
Volume76
Issue number4
Early online date6 Oct 2020
DOIs
Publication statusPublished - 1 Dec 2020

Keywords

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

OECD FOS+WOS

  • 1.02 COMPUTER AND INFORMATION SCIENCES
  • 5.02.PE OPERATIONS RESEARCH & MANAGEMENT SCIENCE

Fingerprint

Dive into the research topics of 'On approximate data reduction for the Rural Postman Problem: Theory and experiments'. Together they form a unique fingerprint.

Cite this