On approximate data reduction for the Rural Postman Problem: Theory and experiments
René van Bevern Till Fluschnik Oxana Yu. Tsidulko

Dynamics of hybrid junctions of Majorana wires
    Nilanjan Bondyopadhaya^1 and Dibyendu Roy^2
    December 30, 2023
===============================================




  =-1
  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 polynomialtime
  compressed to instances of size polynomial in d
  unless the polynomialtime 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
  polynomialsize 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
  towards a PSAKS for the parameter c.


  




  
Keywords:
  Eulerian extension;
  capacitated arc routing;
  lossy kernelization;
  above-guarantee parameterization;
  NP-hard problem;
  parameterized complexity




§ INTRODUCTION


In the framework of lossy kernelization
<cit.>,
we study trade-offs between
the provable effect of data reduction
and
the provably achievable solution quality
for the following classical
vehicle routing problem <cit.>.

[3]
[Rural Postman Problem, RPP]
    
  
  Instance: An undirected graph G=(V,E)
    with n vertices,
    edge weights E→∪{0},
    and a multiset R
    of required edges of G.
    
  
  Task: Find
    a closed walk W^* in G
    containing each edge of R
    and minimizing
    the total weight (W^*)
    of the edges on W^*.
  

We call any closed walk containing
each edge of R an .
By RPP we will also refer to
the decision problem
where one additionally gets a nonnegative integer k∈
in the input
and the task is to decide
whether there is an  W
of weight (W)≤ k.


RPP has direct applications
in snow plowing,
street sweeping,
meter reading <cit.>,
vehicle depot location <cit.>,
drilling, and plotting <cit.>.
The undirected version
occurs especially
in rural areas, where
service vehicles
can operate in both directions
even on oneway roads <cit.>.
Moreover,
RPP is a special case of
the Capacitated Arc Routing Problem (CARP)
<cit.>
and used in all “route first, cluster second” algorithms
for CARP <cit.>,
which are notably the only ones
with proven
approximation guarantees <cit.>.
Improved approximations for RPP
automatically
lead to better approximations for CARP.

=-1
There is a folklore
polynomialtime 3/2-approximation for RPP
based on the -
algorithm for the metric Traveling Salesman Problem <cit.>
(we refer to <cit.> or <cit.>
for a detailed algorithm description).
We aim for (1+ε)approximations
for all ε>0.
Unfortunately,
RPP contains the metric Traveling Salesman Problem
as a special case,
which cannot be
polynomialtime
approximated within any factor smaller than 123/122
unless P=NP <cit.>.
Thus,
finding (1+ε)-approximations
even for constant small ε>0
typically requires exponential time.
We present data reduction rules
for this task.
Their effectivity depends
on the desired ε.



 §.§ Our contributions and outline of this paper

In <ref>,
we introduce basic notation
of graph theory,
approximation algorithms,
parameterized complexity,
problem kernelization,
and WK[1]-completeness.
In <ref>,
we prove basic
properties of optimal s.

Using the recently introduced concept
of WK[1]-hardness <cit.>,
in <ref>,
we prove that it is hard
to reduce exactly solving RPP
to solving instances
of size polynomial in (W^*)-(R)+|W^*|-|R|,
which is
the weight and number
of the deadheading edges
traversed additionally to the required ones:

  
  RPP is WK[1]-complete
  parameterized by Θ((W^*)-(R)+|W^*|-|R|),
  where W^* is an optimal 
  with a minimum amount of edges and
  WK[1]-hardness holds
  even in complete graphs
  with metric edge weights 1 and 2.




In contrast to <ref>,
in <ref>,
we show that effective data reduction for RPP
is possible
if one is interested in (1+ε)-approximations.


  
  There is an algorithm that,
  given ε>0
  and
  an RPP instance (G,R,)
  with b vertices incident to an odd number of edges in R
  and
  whose edges in R form c connected components,
  reduces (G,R,) to an RPP instance (G',R',')
  in O(n^3+|R|) time
  such that
  [(i)]
  
  * 
    the number of vertices in G' is 2b+O(c/ε),
    
  
  * 
    the number of required edges is |R'|≤ 4b+O(c/ε),
    
  
  *  the maximum edge weight
    with respect to ' is O((b+c)/ε^2),
    and
  
  * 
    any α-approximate solution
    for I'
    for some α≥ 1
    can be transformed into
    an α(1+ε)-approximate solution
    for I in polynomial time.
  

Finally,
in <ref>,
we experimentally evaluate
the data reduction algorithm from <ref>.



  
Discussion of our results.
<ref> complement each other
since the number |W^*|-|R| of deadheading arcs
is at least max{b/2,c}
(see <ref>).
Thus,
<ref> shows that
it is hard to polynomialtime reduce RPP to instances
of size (b+c) without
loss in the solution quality,
whereas <ref> allows to do so
with arbitrarily small loss.
In <ref>,
we will also discuss difficulties
of getting rid of b or c
in the size of the reduced instance I'.


Notably,
the α-approximate solution
for I' in <ref>
may be obtained by any means,
for example exact algorithms or heuristics.
Thus, <ref>
can be used to speed up expensive heuristics
without much loss in the solution quality.
In terms of
the recently introduced
concept of lossy kernelization
<cit.>,
<ref>
yields a polynomialsize approximate
  kernelization scheme (PSAKS).

In experiments,
on instances with few connected components,
the number of vertices and required edges is reduced
to about 50 %
at an 1 % loss in the solution quality.
On realworld snow plowing data from Berlin,
the number of vertices is reduced to
about 20 %
without loss in the solution quality.





 §.§ Related work



  
Classical complexity.
RPP is strongly NP-hard <cit.>,
its special case
with R=E is the
polynomialtime solvable
Chinese Postman problem
<cit.>.
Containing the metric Traveling Salesman Problem
as a special case,
RPP is APX-hard <cit.>.
There is a folklore
polynomialtime 3/2-approximation
based on the -
algorithm <cit.> for the metric Traveling Salesman Problem 
(we refer to arc routing surveys <cit.>
for a detailed algorithmic description).
The Chinese Postman Problem
is equivalent to finding a minimumweight set of edges
whose addition makes a connected graph Eulerian <cit.>.
For a disconnected graph,
this is exactly RPP <cit.>.



  
Parameterized complexity.
=-1
<cit.> showed an O(4^d· n^3)-time
algorithm for the directed RPP,
where d=|W^*|-|R| is the minimum number
of deadheading arcs
in an optimal solution W^*.
It can be easily adapted to the undirected RPP.
<cit.> showed an O(4^clog b^2(n))-time
algorithm for the directed RPP,
where
c is the number of (weakly) connected components
induced by the required arcs in R and
b=∑_v∈ V|(v)-(v)|.
It is not obvious whether this algorithm
can be adapted to the undirected RPP
maintaining its running time.
<cit.> showed
a randomized algorithm
that solves the directed and undirected
RPP in f(c)(n) time
if edge weights are bounded polynomially in n.
It is based on the Schwartz-Zippel Lemma <cit.>
for randomized polynomial identity testing.
The existence of a deterministic algorithm
with this running time is open
<cit.>.



  
Exact kernelization.
RPP can easily be reduced
to an equivalent instance with 2|R| vertices
<cit.>.
By shrinking the weights using a theorem of <cit.>
one gets a socalled problem kernel
of size polynomial
in the number of required edges
(we refer to <cit.> for details).
In contrast,
<cit.> showed that,
unless the polynomialtime
hierarchy collapses,
the directed RPP has no problem kernel
of size polynomial in the
number of deadheading arcs.
This result is strengthened by our <ref>,
which shows even WK[1]-hardness,
also of the directed RPP.



  
Lossy kernelization.
=-1
Due to the kernelization hardness of many problems,
recently the concept of approximate kernelization
has gained increased interest <cit.>.
In this context,
<cit.> called for finding
connectivityconstrained problems
that do not have polynomialsize kernels
but α-approximate polynomialsize kernels.
Our <ref> exhibit
that RPP is such a problem.
Among the so far few known lossy kernels
<cit.>,
our <ref>
stands out since it shows a
time and size efficient PSAKS,
which is a property previously observed
only in results of <cit.>.
Moreover,
<ref>
is apparently the first lossy kernelization result
for parameters above lower bounds,
which previously got attention in exact kernelization.






§ PRELIMINARIES




 §.§ Set and graph theory




  
Sets and multisets.
By  we denote the set of natural numbers
including zero.
For two multisets A and B,
A⊎ B is the multiset
obtained
by adding the multiplicities
of elements in A and B.
By A∖ B we denote the multiset
obtained by subtracting
the multiplicities of elements in B
from the multiplicities of elements in A.
Finally,
given some weight function A→,
the weight of a multiset A
is (A):=∑_e∈ Aν(e)(e),
where ν(e) is
the multiplicity of e in A.




  
Graph theory.
Graphs in our work
are allowed to have loops and parallel edges,
so that they are actually
multigraphs G=(V,E)
with a set V(G):=V of vertices,
a multiset E(G):=E over {{u,v}| u,v∈ V}
of (undirected) edges,
and edge weights E→.
Parallel edges in our graphs are indistinguishable
from each other and all have the same weight.
For a multiset R of edges,
we denote by V(R) the set of their incident vertices.




  
Paths and cycles.
=-1
A walk from v_0 to v_ℓ in G is a
sequence w=(v_0,e_1,v_1,e_2,v_2,…,
e_ℓ,v_ℓ)
such that e_i is an edge
with end points v_i-1 and v_i
for each i∈{1,…,ℓ}.
If v_0=v_ℓ,
then we call w a closed walk.
If all vertices on w are pairwise distinct,
then w is a path.
If only its first and last vertex coincide,
then w is a cycle.
By E(w) we denote the multiset of edges on w,
that is,
each edge appears on w and in E(w) equally often.
The length of walk w
is its number |w|:=ℓ=|E(w)| of edges.
The weight of walk w
is (w):=∑_i=1^ℓ(e_ℓ).
An Euler tour for G
is a closed walk that traverses
each edge of G
exactly as often as it is present in G.
A graph is Eulerian
if it allows for an Euler tour.



  
Connectivity and blocks.
=-1
Two vertices u,v of G are connected if there is a path from u to v in G.
A connected component of G
is a maximal subgraph of G
in which the vertices are mutually connected.
A vertex v of G is a
cut vertex
if removing v
and its incident edges
increases the number of
connected components of G.
A biconnected component
or block of G
is a maximal subgraph
without cut vertices.



  
Edge- and vertexinduced subgraphs.
For a subset U⊆ V of vertices,
the subgraph G[U] of G=(V,E) induced by U
consists of the vertices of U
and all edges of G between them
(respecting multiplicities).
For a multiset R of edges of G,
G R:=(V(R),R)
is the graph
induced by the edges in R.
For a walk w,
we also denote Gw:=GE(w).
Note that GR and Gw
do not contain isolated vertices yet
might contain
edges with a higher multiplicity than G and,
therefore,
are not necessarily sub(multi)graphs of G.



 §.§ Decision problems, optimization problems, approximation





  A decision problem is a subset Π⊆Σ^*
  for some finite alphabet Σ.
  The task is,
  given an instance x∈Σ^*,
  determining whether x∈Π.
  If x∈Π,
  then x is a yesinstance.
  Otherwise,
  it is a noinstance.


For optimization problems,
we use the terminology of <cit.>.
We will only consider minimization problems in our work.

  An combinatorial optimization problem Π is a triple Π=(D_Π,S_Π,m_Π),
  where
  
  
  * D_Π is a set of instances,
  
  * S_Π is a function
    assigning to each instance I∈ D_Π
    a finite set S_Π(I) of
    (feasible) solutions, and
  
  * m_Π is a function
    that assigns a solution cost m_Π(I,σ)
    to each feasible solution σ∈ S_Π(I)
    of an instance I∈ D_Π.
  
  An optimal solution
  for an instance I∈ D_Π
  is a feasible solution σ∈ S_Π(I)
  minimizing m_Π(I,σ).
  Its cost is denoted as _Π(I),
  where we drop the subscript Π
  when the optimization problem is clear from context.


If the set S_Π(I) for any instance I∈ D_Π
is polynomialtime recognizable,
any solution σ∈ S_Π(I) has size |σ|≤(|I|),
and the function m_Π is polynomialtime computable,
then one also calls Π an NP-optimization problem.


  An αapproximate solution for an instance I
  of a combinatorial optimization problem Π
  is a feasible solution of cost at most α·_Π(I).




 §.§ Kernelization





=-1
Kernelization is the main notion
of data reduction with provable performance guarantees
<cit.>.
Since proving that a polynomialtime algorithm
always shrinks the input instance of an NP-hard problem,
say from size n to n-1, would imply P=NP,
the size of the reduced instance is measured
in dependence of a
parameter of the input instance.

We formalize parameters using the terminology of <cit.>,
since it allows to parameterize decision and optimization problems
in a uniform way:


  A parameterization is a
  polynomialtime computable
  mapping κΣ^*→
  of instances (of decision or optimization problems)
  to a parameter.
  For a (decision or optimization) problem Π
  and parameterization κ,
  (Π,κ) is called
  a parameterized (decision or optimization) problem.







 
 A kernelization for a parameterized decision problem (Π,κ)
 is a polynomialtime algorithm
 that maps any instance x∈Σ^*
 to an instance x'∈Σ^*
 such that
 [(i)]
  
  * x∈Π x'∈Π, and
  
  * |x'|≤ g(κ(x)) for some computable function g.
  
  We call x' the problem kernel
  and g its size.


A generalization of problem kernels
are Turing kernels,
where one is allowed to generate multiple reduced
instances instead of a single one.


  A Turing kernelization for
  a parameterized decision problem (Π,κ)
  is an algorithm A that decides x∈Π
  in polynomial time
  given access to an oracle
  that answers x'∈Π in constant time
  for any x'∈Σ^* with
  |x'|≤ g(κ(x)),
  where g is an arbitrary function
  called the size of the Turing kernel.


Since <ref> means that
it is hard to obtain problem kernels for RPP
even with size polynomial in a relatively large parameter,
we will consider approximate problem kernels
<cit.>:


  A β-approximate kernelization
  for a parameterized optimization problem (Π,κ)
  consists of two polynomialtime algorithms:
  [(i)]
  
  * The first algorithm reduces an instance I
    of Π to an instance I' of Π
    such that |I'|≤ g(κ(I))
    for some computable function g→.
  
  * The second algorithm turns any
    αapproximate solution for I'
    into an αβapproximate
    solution for I.
  
  We call g the size of the approximate kernel I'.


In fact, we show polynomialsize
approximate kernelization schemes
<cit.>:


  A polynomialsize approximate
    kernelization scheme (PSAKS)
is a family of
  (1+ε)-approximate kernelizations
  yielding approximate kernels of polynomial size for every fixed ε>0.




  §.§.§ Kernelization hardness

WK[1]-complete parameterized decision problems
do not have problem kernels of polynomial size
unless the polynomialtime hierarchy collapses
and are conjectured not to have
Turing kernels of polynomial size either <cit.>.
An archetypal WK[1]-complete
problem is the following <cit.>:
[NDTM Halting]
  
  
  Instance: A nondeterministic Turing machine  and an integer t.
  
  Parameter: tlog ||.
  
  Question: Does  halt in t
    steps on the empty input string?
  


The class WK[1] can now be defined
as the class of all parameterized problems
reducible to NDTM Halting using
the following type of reduction.


  A polynomial parameter transformation (PPT)
  of a parameterized decision problem (Π,κ)
  into a parameterized decision problem (Π',κ')
  is an algorithm that
  maps any instance x∈Σ^*
  to an instance x'∈Σ^*
  in polynomial time
  so that
  [(i)]
  
  * x∈Π x'∈Π' and
  
  * κ'(x')∈(κ(x)).
 


  WK[1] is the class of parameterized decision problems
  PPT-reducible to NDTM Halting.
  A parameterized decision problem (Π,κ) is WK[1]-hard
  if every parameterized decision problem in WK[1]
  is PPT-reducible to (Π,κ).
  It is WK[1]-complete
  if it is WK[1]-hard and contained in WK[1].

Notably,
since PPT-reducibility is a transitive relation,
to prove WK[1]-hardness of a parameterized decision problem,
it is enough to PPT-reduce any other WK[1]-hard parameterized decision
problem
to it.












 §.§ Approximate weight reduction




We will use the following lemma
to shrink edge weights
so that their encoding length will be
polynomial in the number of vertices and edges of the graph.
It is a generalization
of an idea implicitly
used for weight reduction
in a proof of <cit.>
and shrinks weights faster
and more significantly
than a theorem of <cit.>
that is frequently used
in the exact kernelization of weighted
problems <cit.>.
We first state the lemma,
and thereafter intuitively describe its application to RPP.




  
  Let ℱ⊆^n_≥ 0 and ∈_≥ 0^n be
such that
  
  
  * _∞≤ for some ∈ and
  
  * x_1≤ N for some N∈ and all x∈ℱ.
  
  Let
  x^*∈{^⊤ x| x∈ℱ}
  and
  x̅^*∈{^⊤ x| x∈ℱ}.
  Then, for any ε>0,
  using O(n) arithmetic operations involving only the numbers ε,
  β, and the components of ,
  one can compute ∈^n such that
  [(i)]
  
  *  _∞≤ N/ε and
  
  *  for any ∈ and
 x∈ℱ with
    ^⊤ x≤·^⊤x̅^*,
    one has
    ^⊤ x≤·^⊤ x^*+ε.



Note that one can easily prove a version of <ref>
for maximization problems.
To apply <ref> to RPP,
we will take ℱ to be the set
of inclusionminimal s
(encoded as vectors x∈ℱ
having an entry for each edge
that specifies how often it is included in the ),
and  to be a vector
having an entry for each edge specifying its weight.
Then the linear forms ^⊤ x and ^⊤ x
give the weight of the  encoded by x
with respect to the initial weights 
and the reduced weights ,
respectively.
The linear forms occurring in the lemma
seem to limit it to problems with
linear or additive goal functions,
yet in fact are powerful enough
to model many nonadditive goal functions
as well
<cit.>.



  Choose M=(ε)/N
  and
  _i = ⌊_i/M ⌋
  for each i∈{1,…,n}.
  Since _i≥ 0 for each i∈{1,…,n},
  we have ∈^n.
  Moreover,
  due to _∞≤,
  for each i∈{1,…,n},
  we have _i ≤/M = N/ε,
  proving (<ref>).
  
  To prove (<ref>),
  let x∈ℱ be
  such that ^⊤ x≤·^⊤x̅^*.
  By the choice of 
  for each i∈{1,…,n},
  we have _i≤ M· (_i+1).
  Moreover, we have
  
    M ·^⊤ x   ≤^⊤ x      for all  x∈ℱ.
 
  It follows that
  ^⊤ x  ≤ M· (^⊤ x + x_1) 
    ≤ M·^⊤ x + ε≤· M·^⊤x̅^* + ε.
    By (<ref>)
  and the choice of x̅^*,
  we have
  ^⊤x̅^* ≤^⊤ x^* ≤^⊤ x^*/M.
  Finally,
  ^⊤ x ≤· M·^⊤x̅^* + ε≤·^⊤ x^* + ε.





§ SOLUTION STRUCTURE


In this section,
we prove fundamental properties
of optimal s.
To make these hold,
we first establish the triangle inequality in <ref>.
In <ref>,
we translate RPP to the problem
of finding Eulerian extensions.
In <ref>,
we derive inequalities
to bound parts of
optimal s.



 §.§ Triangle inequality


Without loss of generality,
we will assume that the weight function
satisfies the triangle inequality:



  
  =-1
  In O(n^3) time,
  an RPP instance (G,R,)
  can be turned into an RPP instance (G',R,')
  such that

  
  * G' is a complete graph,
  
  * ' satisfies the triangle inequality, and
  
  * any α-approximate solution
  for (G,R,')
  can be turned into an
  α-approximate solution for (G,R,)
  in polynomial time. 
  



  
  =-1
  <ref> holds
  in particular for α=1
  and
  does not increase
the number of connected components of GR,
  the number of odddegree vertices of GR,
  the number and weight of deadheading edges
  of an optimal .
  Thus,
  it is sufficient to prove
  <ref>
  for RPP with triangle inequality.
  We will henceforth assume that the input graph is complete
  and satisfies the triangle inequality.




 §.§ Edge-minimizing Eulerian extensions


=-1
Consider any  W
for an RPP instance (G,R,).
Then GW is an Eulerian
supergraph of GR
whose total edge weight is (W).
Moreover,
any Eulerian supergraph GW'
of GR
yields an  for (G,R,)
of total weight (W').
Thus,
s one-to-one
correspond to s
<cit.>:[Before, this correspondence was
  observed for the Chinese Postman Problem
  independently by <cit.>, and <cit.>.]

An  (EE)
  for an RPP instance (G,R,)
  is a multiset S
  of edges such that
  GR⊎ S is Eulerian.
  We say that an  S is
  
  if there is no  S'
  with |S'|<|S| and (S')≤(S).


In the following,
we will concentrate on finding minimumweight
s rather than s
and exploit that a graph without
isolated vertices is Eulerian
if and only if it is connected and balanced:

  A vertex is balanced
  if it has even degree.
  A graph is balanced
  if each of its vertices is balanced.


Thus,
solving RPP reduces to finding
a minimumweight set S of edges
such that GR⊎ S is connected and balanced.
Since an Euler tour
in the Eulerian graph GR⊎ S
is computable in linear time
using Hierholzer's algorithm <cit.>,
we can easily recover an  from an .

  
  Let (G,R,) be an RPP instance.

  [(i)]
  
  * From any  W for (G,R,),
  one can compute an  S
  of weight (S)=(W)-(R)
  in time linear in |W|.
  

  * From any  S for (G,R,),
  one can compute an  W
  of weight (W)=(R)+(S)
  in time
  linear in |R|+|S|.


Assuming the triangle inequality,
any 
can be shortcut 
to contain only vertices incident to required edges.

  
  Any   S for an RPP instance (G,R,)
  satisfies V(S)⊆ V(R).


The following lemma,
in particular,
shows that no  
contains required edges
between balanced vertices.

  
  An   S
  for an RPP instance (G,
  R,)
  does not contain any
  edge {u,v}
  such that u and v belong
  to the same connected component of GR
  and such that u is  in GR.


  =-1
  Towards a contradiction,
  assume that {u,v}∈ S.
Since u is
   in GR and GR⊎ S,
  S additionally contains
  an edge {u,w}
  (possibly, v=w).
Then
  (S'∖{{u,v},{u,w}})⊎{{v,w}}
  satisfies |S'|<|S|
  and also is an :
  the balance of u, v and w
  is the same in GR⊎ S and GR⊎ S',
  and u still
  is connected to v in GR⊎ S'
  since u and v belong
  to the same connected component of GR.
  Finally,
  using the triangle inequality, (S')≤(S),
  contradicting the fact that
  S is .



  
  =-1
  Let (G,R,) be an RPP instance
  and c be the number of connected components
  of GR.
  At most 2c-2  vertices
  in GR
  are incident to edges of
  an  
  and this bound is tight.


  Let S be an   for (G,R,)
  and T⊆ S be an inclusionminimal
  subset such that GR⊎ T is connected.
  Then |T|=c-1
  and S∖ T is
  an   for (G,R⊎ T,).
  Thus,
  by <ref>,
  V(S∖ T)⊆ V(R⊎ T).
  Combining this with
  <ref>,
  S∖ T does not contain
  any edges incident to  vertices
  of GR⊎ T.
  The only vertices that might
  be  in GR
  but not in GR⊎ T
  are the at most 2c-2 end points
  of edges in T.
  In the worst case,
  all of them are incident to edges in S.
  <ref>
  shows that the bound is tight.
  




  
  The following lemma shows that
  an  
  contains exactly one edge
  incident to each unbalanced vertex of GR
  and either no or two edges
  incident to each balanced vertex of GR.





  
  Each vertex v∈ V
  is incident to at most two edges of
  an   S
  for an RPP instance (G,R,).


  Towards a contradiction,
  assume that S contains e_i={u_i,v}
  for i∈{1,2,3}.
  Obviously,
  S'=(S∖{e_1,e_2})⊎{{u_1,u_2}}
  satisfies |S'|<|S|.
  Moreover,
  (S')≤(S) follows from the triangle inequality.
  We argue that S' is an ,
  contradicting the choice of S.
  The proof is illustrated in <ref>.



  The balance of v, u_1, u_2, and u_3
  is the same in GR⊎ S and GR⊎ S'.
  It remains to show that
  the vertices v,u_1,u_2,u_3 are connected
  in GR⊎ S'.
  To this end,
  observe that
  GR⊎ S is Eulerian
  and thus contains two edgedisjoint
  paths between u_2 and u_3.
  At most one of these paths
  contains the edge e_2 and
  is lost in GR⊎ S'.
  Thus,
  GR⊎ S' contains the
  edges {v,u_3}, {u_1,u_2},
  and a path between u_2 and u_3.









 §.§ Inequalities




  
  In the context of an RPP instance (G,R,),
  we denote by
[W^* –]

  R – the set of required edges,


  c – the number of connected components in GR,
  

  b – the number of imbalanced vertices in GR,
  

  W^* – a minimumweight 
  with a minimum number of edges,


  D – a minimumweight 
   for (G,R,),


  

  T – a minimumweight
  set of edges such that GR⊎ T
  is connected,
  of minimum cardinality,
  and
 

  M – a minimumweight
  set of edges such that GR⊎ M
  is balanced,
  of minimum cardinality.



  
  The following relations hold:

  0.45
  
    (W^*)   =(R)+(D),
                    
    (M)   ≤(D),
                  
    (T)   ≤(D),
                  
    (D)   ≤(M)+2(T),


0.45
  
    |W^*|   =|R|+|D|,
               
    
        2b=|M|   ≤|D|,
                
    
        c-1=|T|   ≤|D|,
                 
    
        |D|   ≤|M|+2|T|,



where |S|≤|M|+2|T|
holds for any   S.


Equations
(<ref>) and (<ref>) follow from
<ref>.
Inequalities
(<ref>) and (<ref>)
follow by choice of M
and the fact that,
since we assume the triangle inequality,
M is simply a
minimumweight
perfect matching on the b 
vertices in GR <cit.>.
Inequalities
(<ref>) and (<ref>)
follow by choice of T.
Inequality
(<ref>)
follows from the fact that
GR⊎ M is balanced
and adding each edge of T twice to it
does not change the balance of vertices,
yet connects the graph.
We now derive inequality (<ref>).
Consider any   S.
By <ref>,
  a set X of at most 2c-2 balanced vertices in GR
  are incident to edges of S.
By <ref>,
  S contains exactly one edge
  incident to each imbalanced vertex in GR
  and exactly two edges
  incident to each vertex in X.
Thus,
by the handshaking lemma,
we get
2|X|+b=2|S|.
Therefore,
|S|=|X|+b/2≤ 2c-2+|M|=2|T|+|M|.









§ HARDNESS OF KERNELIZATION



In this section,
we prove <ref>.
We first show WK[1]-hardness in <ref>,
then we show containment in WK[1] in
<ref>.
<ref>
immediately follows from
<ref>
using (<ref>) and (<ref>).

<ref> means that,
according to the conjecture of <cit.>,
RPP has no Turing kernels with size polynomial
in the number and weight of deadheading edges
in an optimal .


  
  RPP is WK[1]-hard
  parameterized by
  |T|+|M|+(T)+(M)∈Θ(|D|+(D))
  even in complete graphs
  with metric edge weights one and two.


To prove <ref>,
we provide a
polynomial parameter transformation
from the following
known WK[1]-complete parameterized
problem <cit.>.

[Multicolored Cycle]
  
  Instance: An undirected 
    graph G=(V,E)
    with a
    vertex coloring c V→{1,…,k}.
  
  Parameter: k.
  
  Question: Is there a cycle in G
    containing exactly one vertex
    of each color?
  


  Let I:=(G,c)
  with a graph G=(V,E)
  and a vertex kcoloring c V→{1,…,k}
  be an instance
  of Multicolored Cycle.
  For i∈{1,…,k},
  we denote by V_i:={v∈ V| c(v)=i}
  the vertices of color i.
  Now, consider the RPP instance I'=(G', R, ),
  illustrated in <ref>:

G'=(V,E') is a complete graph,
  the set R
  contains a cycle on the vertices in V_i
  for each i∈{1,…,k},
  and
  
    E'→,  e↦
          1    if e∈ E∪ R,
    
          2    otherwise.

  Note that,
  since all edge weights 
  are one and two,
   is metric.
  Thus,
  by
  <ref>,
  |T|+|M|+(T)+(M)∈Θ(|D|+(D)).
  Moreover,
  since G'R is balanced,
  |T|+|M|+(T)+(M)=|T|+(T)∈ O(k).
  We show that
  I is a yesinstance
  if and only if
  I' has an  of weight (R)+k=|R|+k,
  which,
  by <ref>,
  is equivalent to having
  an  S of weight (S)≤ k.
  
  
  Let S be a multicolored cycle in G.
  Since G'R is a disjoint union of cycles,
  G'R is balanced.
  Since S is a cycle,
  G'R⊎ S is also balanced.
  Since S contains one vertex of each color,
  G'R⊎ S is additionally connected.
  Thus, S is an  for (G',R,).
  Since S consists of edges of G,
  we conclude (S)=|S|=k.

  
  Let S be an   with (S)≤ k
  for (G', R,).
  Since G'R and G'R⊎ S
  are balanced,
  so is G'S.
  Since G'R⊎ S is connected
  and G'S is balanced,
  S contains at least two edges incident
  to a vertex in V_i for each i∈{1,…,k}.
  Thus,  
  since (S)≤ k,
  G'S has to contain exactly k edges,
  all of weight one,
  and exactly one vertex
  of V_i for each i∈{1,…,k},
  that is,
  k vertices.
  Since G'S is balanced,
  it follows that G'S is a
  collection of cycles
  whose color sets do not intersect.
  Thus,
  if G'S was not connected,
  then G'R⊎ S would not be either.
  We conclude that G'S
  is connected,
  that is,
  a single cycle
  containing exactly one vertex of each color.
  By <ref>,
  none of the edges in S are in R.
  Since all of them have weight one,
  they are in G.
  It follows that S forms
  a multicolored cycle in G.


Having shown WK[1]-hardness
in <ref>,
we now show containment in WK[1],
concluding the proof of
<ref>.
Note that we showed hardness
for a parameter in Θ(|D|+(D)),
whereas containment we show
for an even smaller
parameter in O(|D|+log(1+(D)))⊆ O(|D|+(D)).
This means that,
if any problem in WK[1] turns out to have
a polynomialsize Turing kernel,
then there will be a Turing kernel
for RPP with size polynomial even in
|D|+log(1+(D)).


  
  RPP parameterized by
  |T|+|M|+log(1+(T)+(M))∈ O(|D|+log(1+(D)))
  is in WK[1].



  We prove a polynomial parameter transformation
  from RPP parameterized by |T|+|M|+log(1+(T)+(M))
  to NDTM Halting (<ref>).
  By <ref>,
  it is sufficient to reduce RPP
  with triangle inequality.
  To this end,
  we construct a number t∈
  and a nondeterministic Turing
  machine 
that,
  given an empty input string,
  has a computation path
  halting within t
  steps if and only if
  a given RPP instance I=(G,R,)
  on a graph G=(V,E) with n vertices,
  m edges, and
  triangle inequality
  has an  of weight at most (R)+k,
  that is,
  an  of weight at most k.
  To this end,
  let
  
    d_1   :=|M|+2|T|      and   d_2   :=(M)+2(T).
  
By (<ref>),
  there is an optimal 
  of at most d_1 edges for (G,R,).
  Thus,
  if d_1≤log n,
  or n=0,
  then we optimally solve I in polynomial time
  <cit.>
  and return t=1 with
  a Turing machine of constant size
  that immediately halts or never halts
  in dependence of whether I is a
  yesinstance.
  Thus,
  we henceforth assume
  
    0≤log n< d_1.

  If k≥ d_2,
  then, by (<ref>), I is a yesinstance
  and we simply return
  t=1 and
  a Turing machine 
  of constant size
  that immediately halts.
  Thus, we henceforth assume
  
    0≤ k<d_2.

  By (<ref>),
  edges e∈ E
  with weight (e)≥ d_2
  will not be part of the sought 
  of weight k,
  thus we lower their weight to d_2
  and henceforth assume
  
    (e)≤ d_2     for all e∈ E.

  We now construct a nondeterministic Turing machine .
  The Turing machine has a binary alphabet
  and G is assumed to be encoded in binary.
  The state names of 
  encode the incidence matrix of G,
  the weight (e) of each edge e∈ E
  in binary,
  and, for each vertex v∈ V,
  the number of its connected component in GR in binary.
  Turing machine  uses three tapes:
  on the edge tape, it guesses
  at most d_1 edges,
  on the connection tape,
  it records
  which of the initially O(d_1) connected
  components of GR
  (by (<ref>))
  are connected by the guessed edges,
  and
  on the balancing tape,
  it records all  vertices,
  of which initially there are O(d_1)
  by (<ref>)
  and whose number will never exceed O(d_1)
  by adding at most d_1 guessed edges.
  The program of Turing machine 
  is as follows.
  On the empty input,
  at most d_1 times:
  
  
  * Write the name {u,v} of an arbitrary edge of G
    (listed in the state names)
    onto the edge tape.
    This takes O(log n)∈ O(d_1)  steps (by (<ref>)).
    
  
  * Flip the balance of u and v on
    the balancing tape in
    (d_1) steps
    because there are only O(d_1) vertices on it,
    each of which is encoded in O(log n)⊆ O(d_1) bits
    (by (<ref>)).
    
  
  * Record the connectivity
    of the components containing u and v
    on the connection tape
    in (d_1) steps
    because there are only
    O(d_1) component names on it.
    

  If,
  after at most d_1 guessed edges,
  the computation does not
  reach a configuration where
  all vertices are 
  and all components of GR are connected,
  then  goes into an infinite loop.
  Otherwise,
  in (d_1) steps,
  we reached
  such a configuration
  and it remains to check
  whether the guessed edges have weight at most k.
  To this end,
   writes down
  the weights of the at most d_1 guessed edges
  in binary,
  sums them up,
  and compares them to k
  in (d_1+log d_2) steps
  because of (<ref>) and (<ref>).
  If their weight is more than k,
  then  goes into an infinite loop.
  Otherwise,
   stops.
  Observe that
  each computation path of ,
  if it terminates,
  then it does so within t
  steps for some t∈(d_1+log d_2).

  We have shown a correct reduction
  from RPP to NDTM Halting.
  To show that it is a polynomial parameter transformation,
  it remains to show tlog ||∈(d_1+log d_2)=(|T|+|M|+log(1+(T)+(M)).
  Since t∈(d_1+log d_2),
  it remains to show that
  log||∈(d_1+log d_2).
The graph G
  can be hardcoded
  in
  Turing machine  
  using (n) symbols.
  The encoded edge weights
  have total size (n+ log d_2)
  by (<ref>).
  Its program therefore has size ||≤(n+d_1+log d_2).
  Thus,
  
    log ||    ≤log(n+d_1+log d_2)^c=clog (n+d_1+log d_2)   for some constant c
       =c(log n+log(1+d_1/n)+log(1+log d_2/n+d_1))   using log(a+b)=log a +log(1+a/b)
       ≤ c(d_1+log(1+d_1)+log(1+log d_2))   using (<ref>),
                                                             n≥ 1, and d_1≥ 1
       ≤ c(2d_1+log d_2)∈(d_1+ log d_2)   using log(1+x)≤ x.







§ APPROXIMATE KERNELIZATION SCHEMES



In <ref>,
we have seen that
provably effective and efficient
data reduction for RPP
is hard when one requires
exact solutions.
In this section,
we show effective data reduction
rules that only slightly decrease
the solution quality.
Indeed,
we will prove <ref>.
To this end,
in <ref>,
we present three data reduction rules.
In <ref>,
we then
show how to apply these rules
to obtain
a polynomialsize approximate kernelization
scheme (PSAKS)
of size 2b+O(c/ε),
proving <ref>.
Finally,
in <ref>,
we discuss some problems
that one faces when
trying to improve it
to a PSAKS for RPP parameterized only by b or only by c.



 §.§ Removing vertices non-incident to required edges


Recall that,
by <ref>,
we can assume that the input graph G is complete
and the edge weights satisfy the triangle inequality.
Thus,
we can simply delete vertices that are not incident to required edges <cit.>.


  
  Let (G,R,) be an RPP instance
  with triangle inequality.
  Delete all vertices
  that are not incident to edges in R.




Since,
by <ref>,
no   uses vertices
outside of V(R),
the following proposition is immediate.


  
  <ref>
  turns an RPP instance (G,R,)
  into an RPP instance (G',R,)
  such that
  
  
  * any   for (G,R,) is one
    for (G',R,)
    and 
  
  * any
     for (G',R,)
    is one for (G,R,).
  






 §.§ Reducing the number of required edges


In this section,
we present a data reduction rule
to shrink the set of required edges.
This will be crucial
since other data reduction rules
only reduce the number of vertices,
yet may leave the multiset of
required edges between them unbounded.


  
  Let (G,R,) be an instance of RPP
  and C be a cycle in GR
  such that GR∖ C
  has the same number of
  connected components
  as GR,
  then delete the edges of C from R.



  
  Using <ref>,
  one can in O(|R|) time
  compute a set R'⊆ R
  of required edges
  with the following properties.
  [(i)]
  
  * 
    Any  for (G,R',)
    is one for (G,R,)
    and vice versa.
  
  * 
    The number of edges
    in each connected component of GR'
    with k vertices
    is at most max{1,2k-2}.
  


  We apply <ref> as follows.
  For i∈{1,…,c},
  let R_i⊆ R be the set of required
  edges in the i-th connected component of GR.
  In O(|R_i|) time,
  one can compute
  a depthfirst search tree T_i of GR_i,
  which is a spanning tree of GR_i.
  Now we remove all cycles from GR_i∖ T_i as follows.
  We start a depthfirst search on GR_i∖ T_i.
  Whenever we meet a vertex v a second time,
  we backtrack to the previous occurrence of v,
  deleting all visited edges from the graph on the way.
  This procedure removes
  all cycles from GR_i∖ T_i
  and looks at each edge in R_i∖ T_i
  at most twice,
  thus works
  in O(|R_i|) time.
  
  (<ref>)
  Any two vertices
  are connected in GR
  if and only if they
  are connected in GR'.
  Moreover,
  the balance
  of each vertex
  is the same in GR and GR'.


  (<ref>)
  Each component of GR'
  with k=1 vertex has one edge (a loop).
  Each component of GR'
  with k>1 vertices
  consists of k-1 edges of a spanning tree T_i
  for some i∈{1,…,c}
  and at most k-1 additional edges,
  otherwise they would contain a cycle.




 §.§ Reducing the number of balanced vertices



In this section,
we present a data reduction rule
that removes balanced vertices.
To this end,
we introduce an operation
that allows us to remove balanced vertices
while maintaining the balance
of their neighbors.

First,
the following lemma in particular shows
that removing a balanced
vertex with all its incident edges
changes the balance of
an even number of vertices.
This allows us to restore
their original balance
by adding a matching to the set
of required edges,
not increasing
the total weight of required edges.
This will be crucial to prove
that our reduction rules
maintain approximation factors.


  
  Let Γ=(V,E) be a graph,
  {{u,v}| u,v∈ V}→
  satisfy the triangle inequality,
  and
  F be an evencardinality submultiset
  of edges incident to a common vertex v∈ V.
  Then
  [(i)]
  
  * 
    The set U⊆ V∖{v}
    of vertices
    incident to an odd number of edges of F
    has even cardinality.
    
  
  *  For any
  matching M_v in the complete graph on U,
  (M_v)≤(F) and |M_v|≤|F|.
  



  (<ref>)
  Any graph, in particular ΓF,
  has an even number of odddegree vertices.
  Since |F| is even,
  v is not one of them.

  (<ref>)
  Let e_i:={x_i,y_i}
  for i∈{1,…,|M_v|}
  be the edges of M_v.
  Then there are
  pairwise edgedisjoint
  paths p_i:=(x_i,v,y_i)
  for i∈{1,…,|M_v|}
  in ΓF.
  Thus
  
    (M_v)=∑_i=1^|M_v|(e_i)≤∑_i=1^|M_v|(p_i)≤(F).

  Finally,
  |M_v|≤ |U|≤|F|.

We now use <ref>
to define an operation that allows
us to remove a balanced vertex from GR.
It is illustrated in
<ref>.




  
  Let (G,R,) be an RPP instance
  with  satisfying the triangle inequality,
  v be a vertex that
  
  
  * is balanced in a connected component of GR
    with at least three vertices and
  
  * not a cut vertex of GR or contained in exactly two blocks of GR,
  
  and let R_v⊆ R be
  the required edges incident to v.
  The result of extracting v from GR is defined as follows.
  [(a)]

  * 
    If v is not a cut vertex of GR,
    then let M_v be any perfect matching on
    the set of vertices
    incident to an odd number of edges of R_v.
    The result of extracting v is R'=(R∖ R_v)⊎ M_v.
  
  * 
    If v is a cut vertex of GR
    contained in exactly two blocks A
    and B of GR,
    then let a be a neighbor of v in A,
    b be a neighbor of v in B,
    and R'=(R∖{{a,v},{b,v}})⊎{a,b}.
    [1.]
    
  *      If v is not contained in GR',
    then R' is the result of extracting v.
  
  *      Otherwise,
    v is not a cut vertex of GR'
    and the result of extracting v from GR
    is defined as the result of extracting v from GR'.
  
  



  
  Let (G,R,) be
  an RPP instance
and R' be the result
  of extracting a balanced vertex v of GR.
  Then the following properties hold.
  [(i)]
  
  * 
    V(R')= V(R)∖{v}.
  
  * 
    (R')≤(R) and |R'|≤|R|.
  
  * 
    Each vertex of GR'
    is balanced if and only
    if it is balanced in GR.
  
  * 
    Two vertices of GR'
    are connected if and only if
    they are so in GR.
  
  * 
    Any multiset S
    of edges with V(S)⊆ V(R')
    is an  for (G,R',)
    if and only if it is one for (G,R,).
  



  (<ref>)
First, assume that
  R' was obtained
  according to  <ref>(<ref>).
  Let R_v⊆ R be
  the required edges incident to v
  and
  U⊆ V be
  the set of vertices incident to
  edges of R_v.
Obviously,
  V(R')⊆ V(R)∖{v}
  and
  V(R')⊇ V(R)∖ U.
  Moreover,
  V(R')⊇ U∖{v}:
  since v is in a connected component
  of GR with at least three vertices
  but not a cut vertex,
  the vertices in U∖{v}
  are incident to edges in R∖ R_v.
  These are retained in GR'.
  If R' was obtained
  according to <ref>(<ref>),
  then R' is the same as
  if it were obtained from
  <ref>(<ref>)
  by extracting v from GR⊎{{a,b}},
  where it is not a cut vertex.




  
(<ref>)–(<ref>)
  If R' was obtained
  according to
  <ref>(<ref>),
  then
  (<ref>) and (<ref>)
  follow from
  <ref>
  applied to Γ=GR
  and F=R_v,
  whereas (<ref>) is clear
  since v is not a cut vertex of GR
  and v is not in GR'.
  If R' was obtained
  according to  <ref>(<ref>),
  then (<ref>)–(<ref>)
  trivially hold since ({a,b})≤({a,v})+({b,v})
  and v is not in GR'.
  If R' was obtained
  according to  <ref>(<ref>),
  then (<ref>)–(<ref>)
  hold since R'
  is the same as extracting v
  from G(R∖{{a,v},{b,v}})⊎{{a,b}},
  where it is not a cut vertex,
  and from
  ({a,b})≤({a,v})+({b,v}).


  


  
  =-1
  (<ref>)
  We show that GR⊎ S
  is connected and balanced
  if and only if GR'⊎ S is.

  =-1
  Connectivity.
  By (<ref>),
  two vertices of V(R')
  are connected in GR'
  if and only if they are connected in GR.
  Since V(S)⊆ V(R')⊆ V(R)
  by (<ref>),
  two vertices in V(R')=V(R'⊎ S)
  are connected
  in GR'⊎ S
  if and only if
  they are connected in GR⊎ S.
  By (<ref>),
  the only vertex of GR⊎ S
  that is absent from GR'⊎ S is v,
  which is not isolated in GR⊎ S
  since it is not isolated in GR.
  
  Balance.
  By (<ref>),
  each vertex in V(R') is
  balanced in GR' if and only if it is balanced in GR.
  Since V(S)⊆ V(R')⊆ V(R)
  by (<ref>),
  each vertex in V(R')=V(R'⊎ S)
  is balanced in GR'⊎ S
  if and only if it is balanced in GR⊎ S.
  By (<ref>),
  the only vertex in GR⊎ S
  that is absent from GR'⊎ S
  is v.
  If so,
  then v∉ V(S)
  and v is balanced in GR⊎ S
  because it is balanced in GR.


=-1
We can now turn <ref> into
a data reduction rule.
Its parameter ∈
allows a tradeoff
between its strength
and the introduced error.


  
  
  =-1
  Let (G,R,) be an RPP instance
  with G=(V,E),
   satisfying the triangle inequality,
  and ∈.
  Let C_i be the vertices
  in connected component i∈{1,…,c} of GR
  and B_i⊆ C_i be an
  inclusionmaximal set of vertices
  such that,
  for each u,v∈ B_i
  with u v, one has ({u,v})>.
  Finally,
  let
  
    B:=⋃_i=1^c B_i.

  Now,
  initially let R':=R
  and,
  as long as GR' contains
  a vertex v∈ V∖ B
  that can be extracted using <ref>,
  replace R' by the result of extracting v.

We now analyze the effectivity and error of
<ref>.



  
  Let (G,R,) be an RPP instance
  with  satisfying the triangle inequality.
Then,
  <ref>
  in O(n^3) time
  yields a multiset R' of edges such that
  [(i)]
  
  *  (R')≤(R) and V(R')⊆ V(R).
  
  * 
    Any multiset S of edges
    with V(S)⊆ V(R')
    is an 
    for (G,R',)
    if and only if it is one for (G,R,).
  
  * 
    Any   S
    for (G,R,)
    can be turned into an  S'
    for (G,R',)
    such that (S')≤(S)+2· (2c-2).
    
  
  * 
    GR' contains at most
    2b+2c+4(R)/ vertices.
  


  (<ref>) and (<ref>)
  follow from <ref>
  since R' is the result
  of a sequence of vertex extractions.

  (<ref>)
  We turn S
  into an  S'
  with V(S')⊆ V(R')
  and then apply (<ref>).
  First,
  since S is 
  and  satisfies the triangle inequality,
  by <ref>,
  V(S)⊆ V(R).
  By <ref>,
  the vertices in X:=V(R)∖ V(R')
  are not in B
  and, thus,
  for each v∈ X∩ C_i,
  we find a vertex v'∈ B_i
  such that ({v,v'})≤.
  Note that v'∈ V(R').
  Since each vertex in X
  is balanced in GR,
  by <ref>,
  each vertex v∈ X∩ V(S)
  is incident to exactly two
  edges {v,u} and {v,w} of S
  (possibly, u=w).
  Since {v,v'}⊆ C_i,
  S':=(S∖{{v,u},{v,w}})⊎{v',u}⊎{v',w}
  is also an  for (G,R,).
  Moreover,
  (S')≤(S)+2.
  Doing this replacement
  for each v∈ X∩ V(S),
  we finally obtain an  S'
  for (G,R,)
  with V(S')⊆ V(R')
  and (S')≤(S)+2·|X∩ V(S)|.
  Since each vertex in X is balanced in GR,
  by <ref>,
  |X∩ V(S)|≤ 2c-2.
  Finally,
  by (<ref>),
  S' is an  for (G,R',).

  (<ref>)
  The vertices of GR' can be partitioned
  into X⊎ Y⊎ Z,
  where X are imbalanced in GR',
  Y are balanced and in B,
  and Z are balanced but not in B.
  
  By <ref>(<ref>),
  the vertices in X are imbalanced in GR also.
  Thus,
  
    |X|≤ b.

  We next analyze |Y|.
  For i∈{1,…,c},
  let R_i⊆ R be
  the edges between vertices in C_i,
  T_i^* be the edge set of a
  tree of least weight in GR_i
  connecting all vertices in B_i,
  T_i be the edge set of
  a minimumweight spanning tree in G[B_i],
  and
  H_i be the edge set of a
  minimumweight Hamiltonian cycle in G[B_i].
  Doubling all edges of T_i^*
  yields a closed walk
  in GR_i containing the vertices in B_i.
  Using the triangle inequality of ,
  it can be shortcut to a Hamiltonian cycle in G[B_i].
  Thus,
  (T_i)≤(H_i)≤ 2(T_i^*).[That is,
    T_i is the folklore 2-approximation
    of a Steiner tree with terminals B_i in GR_i.]
  We thus get
  
    (|B_i|-1)   =∑_e∈ T_i<∑_e∈ T_i(e)=
                         (T_i)≤2(T_i^*)≤ 2(R_i)   and thus
    
        |Y|≤|B|   =∑_i=1^c|B_i|<∑_i=1^c(2(R_i)/+1)=2ω(R)/+c.

  =-1
  Finally,
  we analyze |Z|.
  <ref> is not applicable to any vertex v∈ Z,
  since it would have been removed by <ref>.
  Thus,
  v is a cut vertex contained
  in at least three blocks of GR'
  or its connected component of GR'
  consists of only two vertices.
  To analyze |Z|,
  for each i∈{1,…,c},
  consider X_i:=X∩ C_i,
  Z_i:=Z∩ C_i,
  the set R_i'⊆ R' of edges
  between vertices in C_i,
  and the block-cut tree T_i of GR_i':
  the vertices of T_i
  are the cut vertices
  and the blocks of GR_i'
  and there is an edge between a cut vertex v
  and a block A of GR_i'
  in T_i if v is contained in A.
  Then either |Z_i|≤ 2 or
  the vertices in Z_i
  have degree at least three in T_i.
Therefore,
  T_i has at most |X_i|+|Y_i| leaves.
  Since a tree has at least two leaves,
  we get |X_i|+|Y_i|≥ 2.
  Moreover,
  since a tree with ℓ leaves
  has at most ℓ-1 vertices
  of degree three,
  |Z_i|≤max{2,|X_i|+|Y_i|-1}≤ |X_i|+|Y_i|.
  Thus,
  
    |Z|=∑_i=1^c|Z_i|≤ |X|+|Y|.

  Combining (<ref>), (<ref>),
  (<ref>),
  and that |V(R')|=|X|+|Y|+|Z|,
  (<ref>) follows. 
    
  We finally analyze the running time of <ref>.
  For i∈{1,…,c},
  all sets C_i and B_i
  can be computed in O(n^2) time.
  Also
  the blocks of GR'
  required by <ref> are computable
  in O(n^2) time using depthfirst search.
  Thus,
  in O(n) time,
  we can find a vertex v
  to which <ref> applies.
  Vertex v can then be extracted in O(n) time
  since the matchings M_v
  in <ref> can be chosen arbitrarily,
  that is,
  in particular greedily in O(n) time,
  and the blocks can be recomputed in O(n^2) time.
Finally,
  we extract at most n vertices.













 §.§ A polynomialsize approximate kernelization scheme for the parameter b+c (proof of <ref>)



This section proves <ref>.
We describe how to transform
a given RPP instance I and ε>0
into
an RPP instance I'
such that any αapproximate solution
for I' can be transformed into
an α(1+ε)approximate solution for I.
Due to <ref>,
we assume that I=(G,R,)
has been preprocessed in O(n^3) time
so as to satisfy the triangle inequality.




  §.§.§ Shrinking the graph


Choose ε_1+ε_2=ε.
Apply <ref> with

    =ε_1·(R)/4c-4,

which, by <ref>,
in O(n^3) time
gives an instance (G,R_1,)
with

    |V(R_1)|≤ 2b+2c+16c-16/ε_1.

To (G,R_1,),
we apply <ref>,
which, by <ref>,
in O(|R|) time
gives an instance (G,R_2,) with

    R_2⊆ R_1     and    
      |R_2|≤ 4b+4c+32c-32/ε_1.

Finally,
applying <ref> to (G,R_2,)
in linear time
yields an instance (G_2,R_2,)
such that

    |V(G_2)|≤ |V(R_2)|≤|V(R_1)|.




  §.§.§ Shrinking edge weights


Since GR⊎ T is connected,
due to the triangle inequality of ,
each edge e={u,v} of G,
and thus of its subgraph G_2,
satisfies (e)≤(R)+(T).
Moreover,
by <ref>,
any   for (G_2,R_2,)
has at most |M|+2|T|=b/2+2c-2 edges.
Thus,
we can apply <ref>
with
=(R)+(T)
and
N=|R_2|+b/2+2c-2
to (G_2,R_2,)
to get an instance (G_2,R_2,_2)
such that for all edges e,

    (e)≤|R_2|+b/2+2c-2/ε_2∈ O((b+c)/(ε_1ε_2))
      .

In <ref>,
set ℱ just contains all vectors x
that encode s W
induced by  s for (G_2,R_2,)
(its entries describe how often each edge is in W).
We finally return (G_2,R_2,_2),
whose construction takes O(n^3+|R|) time,
as required by <ref>.



  §.§.§ Kernel size analysis

The returned instance satisfies
<ref>(<ref>)
due to (<ref>) and (<ref>),
(<ref>) due to (<ref>),
and (<ref>) due to (<ref>).




  §.§.§ Approximation factor analysis


It remains to prove <ref>(<ref>),
that is,
that we can lift an αapproximate
solution for (G_2,R_2,_2)
to an α(1+ε)approximate solution
for (G,R,).

An optimal  for (G,R,)
has weight (W^*)=(R)+(D)
by (<ref>),
where D is a minimumweight .
By <ref>(<ref>)
and (<ref>),
there is an  D' for (G,R_1,)
with

    (D')≤(D)+2(2c-2)=(D)+ε_1·(R)
      .

By <ref>,
D' is an  for (G,R_2,)
and, by <ref>, for (G_2,R_2,).
Then D' is also an  for (G_2,R_2,_2).
Thus,
an optimal  for (G_2,R_2,_2)
has weight at most
_2(R_2)+_2(D').
By <ref>,
an α-approximate solution for (G_2,R_2,_2),
can be turned into an  S
such that

    _2(R_2)+_2(S)≤α(_2(R_2)+_2(D')).

By <ref>,
S is an  for (G,R_2,).
By <ref>,
S is an  for (G,R_1,),
and by <ref>,
it is one for (G,R,),
since V(S)⊆ V(G_2)=V(R_2)⊆ V(R_1)⊆ V(R).
Thus,
by <ref>,
S can be turned into an 
of weight (R)+(S) for (G,R,).
We analyze this weight.
By (<ref>) and
<ref> with =(R)+(T),

    (R_2)+(S)   ≤α((R_2)+(D'))+ε_2((R)+(T)).
    Using (R_2)≤(R_1)≤(R)
      from <ref>,
      and α≥ 1,  we get(R)+(S)   ≤α((R)+(D'))+ε_2((R)+(T))
       ≤α((R)+(D'))+ε_2((R)+(D))   using (<ref>).
       ≤α((R)+(D)+ε_1(R))+ε_2((R)+(D))   using (<ref>).
       ≤α(1+ε_1+ε_2)((R)+(D))=α(1+ε)(W^*)   using (<ref>).

Thus,
we got an α(1+ε)approximation
for (G,R,c).




 §.§ On polynomialsize approximate
  kernelization schemes for the parameters b and c


In the previous section,
we have shown
a polynomialsize approximate kernelization
scheme (PSAKS)
for RPP parameterized by b+c.
An obvious question is whether there is a PSAKS
for the parameters b or c.
For the parameter b,
we can easily answer this question.


  If RPP parameterized by b has a (1+ε)approximate
  kernel for any ε<1/122, then P=NP.



  Assume that RPP has an (1+ε)approximate kernel
  of any size g(b)
  for ε<1/122.
  We show how to find an (1+ε)approximate solution
  for the metric Traveling Salesman problem
  in polynomial time,
  which implies P=NP <cit.>.
  Given an instance I of the metric Traveling Salesman problem,
  create an instance I' of RPP by adding a required zeroweight loop
  to each vertex.
  Compute an (1+ε)approximate kernel I”
  for I' in polynomial time.
  Since I' has no imbalanced vertices,
  the kernel I” has size g(b)=g(0)∈ O(1).
  Computing an optimal solution in I” thus takes constant time,
  can be lifted to an (1+ε)approximate solution
  for I' in polynomial time and,
  after removing the loops,
  is an (1+ε)approximation for I.




Answering the question about the existence of a PSAKS for the parameter c is not quite as simple.
In the following,
we discuss the difficulties in resolving this question
and
make some first steps towards its resolution.
In particular, we will show a PSAKS for the parameter (T).

To get the PSAKS for c,
one has to reduce the number of imbalanced vertices in GR.
An obvious idea to do so
is adding to R
cheap edges of a minimumweight
perfect matching M on imbalanced vertices,
since this is optimal
if it happens to connect GR.


  
  Let (G,R,) be an RPP instance
  with triangle inequality and ∈.
  Add to R a subset M^*⊆ M of edges with
  
    ∑_e∈ M^*(e)≤.




  
  Let R'=R⊎ M^* be obtained by applying
  <ref> to R.
  [(i)]
  
  * 
    There are at most 2(|M|-|M^*|)
     vertices in GR'.

  
  * 
    For any  S' for (G,R',),
    S=S'⊎ M^* is an  for (G,R,)
    and (R)+(S)=(R')+(S').
  
  
  * 
    For any  S for (G,R,),
    S'=S⊎ M^* is an  for (G,R',)
    with (S')≤(S)+.
  

To show a PSAKS with respect to the parameter c,
this reduction rule is unsuitable for two reasons:


  * To reduce the number of
  imbalanced vertices in GR
  to some constant,
  we have to add all but a constant number of edges of M to R,
  yet, by <ref>(<ref>),
  each added edge potentially contributes to the error
  and thus would merely retain a 2approximation.
  Unfortunately,
  <ref> shows that
  the bound given by <ref>(<ref>) is tight.
  

  * <ref> increases the total weight
  of required edges.
  This makes it unusable for a PSAKS,
  since, in the resulting instance,
  a solution might be (1+ε)approximate
  merely due to the fact that the
  lower bound (R) on the solution is sufficiently large
  (we will use this fact below).

  
Given the difficulties of showing
a PSAKS for c,
it is tempting to disprove its existence.
However,
we can easily build a 
PSAKS with size polynomial in (T),
which gives a PSAKS of size polynomial in c
in case that the edge weights are bounded by (c).
More specifically,
we prove the following.


  
  Let (G,R,) be an instance of RPP
  with triangle inequality.
[(i)]

  *  If (T) ≤ε( (R)+(M)),
  then
  a (1+ 2ε)-approximate 
  for (G,R,) can be found in polynomial time.
  

  *  If (M) ≤ε( (R)+(T)),
  then (G,R,) has
  a (1+3ε+2ε^2)-approximate kernel
  with O(c/ε) vertices.
  

  * 
  Otherwise,
  (G,R,) has
  an (exact) problem kernel with respect
  to the parameter min{(T)/ε-(M),(M)/ε -(T)}.



<ref> shows that,
in order to exclude PSAKSes for RPP parameterized by c,
a reduction must use unbounded edge weights,
the weights of T, M, and R
may not differ too much (by (<ref>) and (<ref>)),
yet the weights of T and M
must not be too close either (by (<ref>)).
Given these restrictions,
we conjecture:

  
  RPP has a PSAKS with respect to the parameter c.


We finally prove <ref>.


  (<ref>)
  Observe that the multiset T⊎ T⊎ M is
  an  for (G,R,).
  Using <ref>,
  it yields an  of weight
  
    (R)+(M)+2ω(T)   ≤(R)+(M)+2ε(ω(R)+ω(M))
       ≤ (1+2ε)((R)+(D))   using (<ref>)
       =(1+2ε)(W^*)   using (<ref>).



  (<ref>) Let R' be obtained from R
  using <ref>
  with =(M),
  that is, R'=R⊎ M.
  In GR', all vertices are balanced.
  Thus, applying <ref>
  to (G,R',)
  gives an instance (G_2,R_2,_2)
with 
  O(c/ε) vertices.

  =-1
  Let D be an optimal  for (G,R,).
  Then,
  by <ref>,
  an optimal  D' for (G,R',)
  has weight (D')≤(D)+δ=(D)+(M)
  and,
  by <ref>,
  an optimal  for (G,R',) has weight (R')+(D').
  Moreover,
  by <ref>,
any α-approximate
   for (G_2,R_2,_2)
  can be lifted to an α(1+ε)-approximate  W for (G,R',).
By <ref>(<ref>),
  it yields a  for (G,R,) of weight

    (W)≤α(1+ε)((R')+(D'))   ≤α(1+ε)((R) + 2(M) +(D))
       ≤α(1+ε)((R) + 2ε((R)+(T))+(D))   using (<ref>).
       ≤α(1+ε)((1+2ε)(R) + (1+2ε)(D))   using (<ref>)
       =α(1+ε)(1+2ε)((R)+(D))
       =α(1+3ε+2ε^2)(W^*)   using (<ref>).


  
  (<ref>)
  Otherwise, one has
  
    (R)   ≤(M)/ε-(T)       and    (R)   ≤(T)/ε-(M)

  and thus the known
  2|R|-vertex problem kernel <cit.>
  for RPP
  will be a kernel for both of these parameters.







§ EXPERIMENTS



In this section,
we experimentally evaluate the polynomial-size approximate kernelization scheme
presented in <ref>.




  
Data instances.
We evaluate the data reduction effect of our algorithm
on three data sets
generated by <cit.>:
[madr-p-i:]

  alba-p-i for each p∈{0.3,0.5,0.7} and i∈{1,…,5}:
  based on the street network of the Spanish town Albaida,
  where each edge is required with probability p
  and i is just a running index.

  madr-p-i for each p∈{0.3,0.5,0.7} and i∈{1,…,5}:
  based on the street network of the Spanish town Madrigueras,
  where each edge is required with probability p
  and i is just a running index.

  ur-n-d-p for each n∈{500,750,1000},  d∈{3,4,5,6}, and p∈{0.25,0.5,0.75}:
  n vertices are selected randomly from an (1000× 1000)-grid,
  distances are Euclidean,
  each vertex is connected to its d closest neighbors,
  and
  each edge is required with probability p.

These data sets  are widely used in the literature <cit.>.[Available at <https://www.uv.es/corberan/instancias.htm>]
We also test our algorithm on two instances provided to us
by Berliner Stadtreinigung,
the company responsible for snow plowing and garbage collection in Berlin.[Available at <https://gitlab.com/rvb/rpp-psaks>]
In the Berlin instances,
both the street network as well as the required edges
arise from a real snow plowing application,
as opposed to generating the required edges randomly
like in the other instances.

Characteristics of these instances
and the weight (W) of a solution obtained via the 3/2-approximation
can be seen in the “input instance” columns of
<ref>.












  
Experimental setup.
Since our main goal is evaluating the effect of our data reduction
rather than the running time of our algorithm,
we sacrificed speed for simplicity and implemented
the part of our PSAKS described in <ref>
in approximately 200 lines of Python
(not counting the testing environment)
using the NetworkX library for
finding minimumweight perfect matchings,
(bi)connected components,
cut vertices, and
spanning trees.[<https://networkx.github.io/>]
These routines are also contained in
highly optimized C++ libraries like LEMON[<https://lemon.cs.elte.hu/trac/lemon>]
and we expect that one could achieve a speedup by orders of magnitude
by implementing our PSAKS in C++.
We did not implement the
weight reduction step described in <ref>,
since it is mainly of theoretical interest
(to prove a polynomial size of the kernel
rather than just a polynomial number of vertices and edges).

We kernelized each of the instances listed above
for ε=1/10, that is,
we require that a 11α/10-approximation
be recoverable from an α-approximate solution in the kernel.
Since we do not reduce weights,
this means we apply <ref> with
ε_1=ε=1/10 in (<ref>).

We also apply
the folklore 3/2-approximation algorithm
based on the -
algorithm for the metric Traveling Salesman Problem <cit.>
to compute a solution
in the original and kernelized instance
and compare their weights.







  
Experimental results.
<ref> gives a rough idea
of the data reduction effect of our PSAKS
on the alba-p-i, madr-p-i, and ur-n-d-p instances.
The complete experimental results,
including the two Berlin instances,
are shown in <ref>,
where additionally to the notation in <ref>,
we denote by
[|V'|, |R'|]

  (W) – the weight of a 3/2-approximation computed in the input graph,

  (W') – the weight of a 3/2-approximation computed in the kernel and lifted to the input graph,

  |V'|, |R'| – the number of vertices and required edges in the kernel, respectively, and by

  ms – the number of milliseconds it took to compute the kernel (not counting the time for computing pairwise shortest path lengths for
  establishing the triangle inequality using <ref>).

Since for the ur-n-d-p instances,
the weight of an optimal solution is known,
we compare (W') to the optimum
in <ref>.[For the alba-p-i and madr-p-i instances,
  the optimum is only known when considered as instances of the General Routing Problem,
  where also vertices have to be visited.]
Remarkably,
the best compression results are achieved on the Berlin instances,
the only instances consisting purely out of realworld data: only 22 % of
the vertices incident to required edges remain.
<ref> visualizes the kernelization effect on two
strongly
compressed instances.


In the following,
we discuss the data reduction effect in more detail
with the help
of the plots in <ref>.
Since some of the instances in the literature
(concretely, the ur-n-d-p instances)
are already preprocessed with respect
to <ref>,
we analyze the data reduction effect
with respect to the number |V(R)| of those input
vertices incident to required edges.
For the sake of completeness,
the data reduction effect
with respect to the number of all input vertices
is shown in <ref>.



=-1
In <ref>,
we see that the effectivity of our PSAKS grows
with the number of input vertices incident to required edges
and with the number of required edges themselves.
In <ref>,
we see that, as expected,
the effectivity decreases as the number of connected components of G⟨ R⟩ grows.
However,
in all three plots,
we see a clear clustering
of different instance types. It is <ref>
that shows the determining feature for
the effectivity of our PSAKS:
in all instances types,
it
uniformly grows with the
average size of the connected components of G⟨ R⟩.
This comes at no surprise,
since the main action of our PSAKS
is shrinking these connected components.


Regarding the solution quality, we point out that,
despite kernelizing all instances with ε=1/10
and thus allowing a weight increase by a factor of 1.1
when lifting a solution from the kernel to the original instance,
the maximal such weight increase observed is 1.01 (for the alba-p-i instances in <ref>),
whereas often no weight increase is observed.
In some cases,
kernelization leads to better solutions
(for the instances in <ref>).
Also, in <ref>,
the 3/2-approximate solution lifted from the kernel
turns out to be worse than the optimum by a factor not larger than 1.075
and is thus way below the allowance.













  
Possible improvements.
The effectivity of our data reduction can be increased
replacing (R) by

    max{(R)+(M),(R)+(T),(R)+(M)+(T)/2}

in the choice of γ in (<ref>) for the application of <ref>.
Since this also is a lower bound for (W^*) (recall <ref>),
such a replacement will still guarantee
that a α(1+ε)-approximation
can be lifted from a α-approximation on the kernel.
However,
this replacement removes about one or two percents of vertices more,
whereas
computing (M) in the larger instances
took between 11 and 40 seconds,
so the payoff is very limited.












§ CONCLUSION

Our main algorithmic contribution
is a polynomialsize approximate kernelization scheme (PSAKS)
for the Rural Postman Problem
parameterized by b+c,
where b is the number of vertices
incident to an odd number of required edges
and c is the number of connected components
formed by the required edges.
Experiments show that
the data reduction algorithm
efficiently shrinks
problem instances with few connected components
without largely sacrificing solution quality.
We also showed a PSAKS
for the parameter (T),
which gives a PSAKS for the parameter c
when edge weights are bounded polynomially in c.
These results together naturally lead to the question
whether a PSAKS for the parameter c exists
(we conjecture “yes”).

We think that the approach taken by
<ref>,
namely reducing all vertices that
do not belong to some inclusionmaximal set B
of mutually sufficiently distant vertices,
might be applicable to other metric graph problems:
it ensures that,
for each deleted vertex,
some nearby representative in B is retained.
In preliminary research, for example,
we also found it to applicable
to a metric variant
of the Min-Power Symmetric Connectivity problem
where it is required to connect c disconnected
parts of a wireless sensor network <cit.>
and to the Location Rural Postman Problem <cit.>.
Notably,
this approach does not generalize well to
asymmetric distances,
so that another vexing question
besides proving <ref>
is whether the scheme for the parameter b+c
presented in this work can be generalized
to the directed Rural Postman Problem.
We point out that,
using known ideas <cit.>,
one can reduce any instance I of the directed
or undirected RPP to an instance I'
with c vertices in O(n^3log n) time
such that any α-approximation for I'
yields an (α+1)-approximation for I.
Given that undirected RPP is 3/2-approximable,
this is interesting only for the directed RPP.




  
Acknowledgments.
We thank the anonymous referees of Networks for their constructive feedback.



  
Funding.
=-1
R. van Bevern and O. Yu. Tsidulko
are supported by the Russian Foundation for Basic Research,
project 18-501-12031 NNIOa.
T. Fluschnik
is supported by the German Research Foundation,
project TORE (NI 369/18).

dr-rpp
56



urlstyle


[Belenguer et al.(2006)Belenguer, Benavent, Lacomme, and
  Prins]BBLP06
J.-M. Belenguer, E. Benavent, P. Lacomme, and C. Prins, Lower and upper
  bounds for the mixed capacitated arc routing problem, Computers &
  Operations Research 33 (2006), 3363–3383,
  10.1016/j.cor.2005.02.009.

[Bentert et al.(2020)Bentert, van Bevern, Fluschnik, Nichterlein, and
  Niedermeier]BBF+xx
M. Bentert, R. van Bevern, T. Fluschnik, A. Nichterlein, and R. Niedermeier,
  Polynomial-time data reduction for weighted problems beyond additive
  goal functions, 2020, <https://arxiv.org/abs/1910.00277>.

[Bentert et al.(2017)Bentert, van Bevern, Nichterlein, and
  Niedermeier]BBNN17
M. Bentert, R. van Bevern, A. Nichterlein, and R. Niedermeier,
  Parameterized algorithms for power-efficient connected symmetric
  wireless sensor networks, A. F. Anta, T. Jurdzinski, M. A. Mosteiro, and
  Y. Zhang (eds.), ALGOSENSORS 2017, Springer, 2017, Lecture Notes
  in Computer Science, vol. 10718, pp. 26–40,
  10.1007/978-3-319-72751-6_3.

[van Bevern et al.(2019)van Bevern, Fluschnik, and Tsidulko]BFT19
R. van Bevern, T. Fluschnik, and O. Yu. Tsidulko, On
  (1+ε)-approximate data reduction for the Rural Postman
  Problem, M. Khachay, Y. Kochetov, and P. Pardalos (eds.), MOTOR
  2019, Springer, Lecture Notes in Computer Science, vol. 11548, 2019,
  pp. 279–294, 10.1007/978-3-030-22629-9_20.

[van Bevern et al.(2020)van Bevern, Fluschnik, and Tsidulko]BFT20
R. van Bevern, T. Fluschnik, and O. Yu. Tsidulko, Parameterized
  algorithms and data reduction for the short secluded s-t-path problem,
  Networks 75 (2020), 34–63, 10.1002/net.21904.

[van Bevern et al.(2014)van Bevern, Hartung, Nichterlein, and
  Sorge]BHNS14
R. van Bevern, S. Hartung, A. Nichterlein, and M. Sorge, Constant-factor
  approximations for capacitated arc routing without triangle inequality,
  Operations Research Letters 42 (2014), 290–292,
  10.1016/j.orl.2014.05.002.

[van Bevern et al.(2017)van Bevern, Komusiewicz, and Sorge]BKS17
R. van Bevern, C. Komusiewicz, and M. Sorge, A parameterized
  approximation algorithm for the mixed and windy capacitated arc routing
  problem: Theory and experiments, Networks 70 (2017), 262–278,
  10.1002/net.21742.

[van Bevern et al.(2015)van Bevern, Niedermeier, Sorge, and
  Weller]BNSW15
R. van Bevern, R. Niedermeier, M. Sorge, and M. Weller, Complexity of arc
  routing problems, Á. Corberán and G. Laporte (eds.), Arc
  Routing: Problems, Methods, and Applications, SIAM, MOS-SIAM Series on
  Optimization, vol. 20, 2015, pp. 19–52, 10.1137/1.9781611973679.ch2.

[van Bevern and Slugina(in press)]BSxxb
R. van Bevern and V. A. Slugina, A historical note on the
  3/2-approximation algorithm for the metric traveling salesman problem,
  Historia Mathematica  (in press), 10.1016/j.hm.2020.04.003.

[van Bevern and Tsidulko(2019)]BT19
R. van Bevern and O. Yu. Tsidulko, Data reduction for the
  location rural postman problem, Abstracts of the 33rd Annual
  Conference of the Belgian Operations Research Society (ORBEL 33), February
  7–8, 2019, Hasselt University, Belgium, 2019, pp. 41–43.

[Brandão and Eglese(2008)]BE08
J. Brandão and R. Eglese, A deterministic tabu search algorithm for the
  capacitated arc routing problem, Computers & Operations Research
  35 (2008), 1112–1126, 10.1016/j.cor.2006.07.007.

[Christofides(1973)]Chr73
N. Christofides, The optimum traversal of a graph, Omega 1
  (1973), 719–732, 10.1016/0305-0483(73)90089-3.

[Christofides(1976)]Chr76
N. Christofides, Worst-case analysis of a new heuristic for the traveling
  salesman problem, Tech. Rep. 388, Carnegie-Mellon University, Pittsburgh,
  Pennsylvania, USA, 1976.

[Corberán et al.(2001)Corberán, Letchford, and
  Sanchis]CLS01
A. Corberán, A. N. Letchford, and J. M. Sanchis, A cutting plane
  algorithm for the general routing problem, Mathematical Programming
  90 (2001), 291–316, 10.1007/PL00011426.

[Corberán et al.(2007)Corberán, Plana, and Sanchis]CPS07
A. Corberán, I. Plana, and J. M. Sanchis, A branch & cut algorithm
  for the windy general routing problem and special cases, Networks
  49 (2007), 245–257, 10.1002/net.20176.

[Corberán and Laporte(2015)]CL15
Á. Corberán and G. Laporte (eds.), Arc Routing: Problems, Methods,
  and Applications, MOS-SIAM Series on Optimization, vol. 20, SIAM,
  2015, 10.1137/1.9781611973679.

[Dorn et al.(2013)Dorn, Moser, Niedermeier, and Weller]DMNW13
F. Dorn, H. Moser, R. Niedermeier, and M. Weller, Efficient algorithms
  for Eulerian Extension and Rural Postman, SIAM Journal on Discrete
  Mathematics 27 (2013), 75–94, 10.1137/110834810.

[Edmonds and Johnson(1973)]EJ73
J. Edmonds and E. L. Johnson, Matching, Euler tours and the Chinese
  postman, Mathematical Programming 5 (1973), 88–124,
  10.1007/BF01580113.

[Eglese and Murdock(1991)]EM91
R. W. Eglese and H. Murdock, Routeing road sweepers in a rural area,
  Journal of the Operational Research Society 42 (1991), 281–288,
  10.1057/jors.1991.66.

[Eiben et al.(2017)Eiben, Hermelin, and Ramanujan]EHR17
E. Eiben, D. Hermelin, and M. S. Ramanujan, Lossy kernels for hitting
  subgraphs, K. G. Larsen, H. L. Bodlaender, and J.-F. Raskin (eds.),
  MFCS 2017, Schloss Dagstuhl–Leibniz-Zentrum für Informatik,
  Dagstuhl, Germany, Leibniz International Proceedings in Informatics
  (LIPIcs), vol. 83, 2017, pp. 67:1–67:14, 10.4230/LIPIcs.MFCS.2017.67.

[Eiben et al.(2018)Eiben, Kumar, Mouawad, Panolan, and
  Siebertz]EKM+18
E. Eiben, M. Kumar, A. E. Mouawad, F. Panolan, and S. Siebertz, Lossy
  kernels for connected dominating set on sparse graphs, R. Niedermeier and
  B. Vallée (eds.), 35th Symposium on Theoretical Aspects of Computer
  Science (STACS 2018), Schloss Dagstuhl–Leibniz-Zentrum für Informatik,
  Leibniz International Proceedings in Informatics (LIPIcs), vol. 96,
  2018, pp. 29:1–29:15, 10.4230/LIPIcs.STACS.2018.29.

[Eiselt et al.(1995)Eiselt, Gendreau, and Laporte]EGL95
H. A. Eiselt, M. Gendreau, and G. Laporte, Arc routing problems, part
  II: The Rural Postman Problem, Operations Research 43 (1995),
  399–414, 10.1287/opre.43.3.399.

[Etscheid et al.(2017)Etscheid, Kratsch, Mnich, and Röglin]EKMR17
M. Etscheid, S. Kratsch, M. Mnich, and H. Röglin, Polynomial kernels for
  weighted problems, Journal of Computer and System Sciences 84
  (2017), 1–10, 10.1016/j.jcss.2016.06.004.

[Fellows et al.(2018)Fellows, Kulik, Rosamond, and Shachnai]FKRS18
M. R. Fellows, A. Kulik, F. A. Rosamond, and H. Shachnai, Parameterized
  approximation via fidelity preserving transformations, Journal of Computer
  and System Sciences 93 (2018), 30–40,
  10.1016/j.jcss.2017.11.001.

[Fernández et al.(2003)Fernández, Meza, Garfinkel, and
  Ortega]FMGO03
E. Fernández, O. Meza, R. Garfinkel, and M. Ortega, On the undirected
  rural postman problem: Tight bounds based on a new formulation, Operations
  Research 51 (2003), 281–291, 10.1287/opre.51.2.281.12790.

[Fleischner(1991)]Fle91
H. Fleischner, Eulerian Graphs and Related Topics: Part 1, Volume 2,
  North-Holland, Amsterdam, The Netherlands, Annals of Discrete
  Mathematics, vol. 50, 1991, pp. X.1–X.14.

[Flum and Grohe(2006)]FG06
J. Flum and M. Grohe, Parameterized Complexity Theory, Texts in
  Theoretical Computer Science, An EATCS Series, Springer, 2006,
  10.1007/3-540-29953-X.

[Fomin et al.(2019)Fomin, Lokshtanov, Saurabh, and Zehavi]FLSZ19
F. V. Fomin, D. Lokshtanov, S. Saurabh, and M. Zehavi, Kernelization,
  Cambridge University Press, 2019, 10.1017/9781107415157.

[Frank and Tardos(1987)]FT87
A. Frank and É. Tardos, An application of simultaneous diophantine
  approximation in combinatorial optimization, Combinatorica 7
  (1987), 49–65, 10.1007/BF02579200.

[Frederickson(1977)]Fre77
G. N. Frederickson, Approximation Algorithms for NP-hard Routing
  Problems, Ph.D. thesis, University of Maryland Graduate School, College
  Park, Maryland, USA, 1977.

[Garey and Johnson(1979)]GJ79
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to
  the Theory of NP-Completeness, Freeman, New York, USA, 1979.

[Ghiani and Improta(2001)]GI01
G. Ghiani and G. Improta, The laser-plotter beam routing problem,
  Journal of the Operational Research Society 52 (2001), 945–951,
  10.1057/palgrave.jors.2601161.

[Ghiani and Laporte(1999)]GL99
G. Ghiani and G. Laporte, Eulerian location problems, Networks
  34 (1999), 291–302,
  10.1002/(SICI)1097-0037(199912)34:4<291::AID-NET9>3.0.CO;2-4.

[Golden and Wong(1981)]GW81
B. L. Golden and R. T. Wong, Capacitated arc routing problems, Networks
  11 (1981), 305–315, 10.1002/net.3230110308.

[Grötschel et al.(1991)Grötschel, Jünger, and
  Reinelt]GJR91
M. Grötschel, M. Jünger, and G. Reinelt, Optimal control of
  plotting and drilling machines: A case study, Zeitschrift für Operations
  Research 35 (1991), 61–84, 10.1007/BF01415960.

[Gutin et al.(2017)Gutin, Wahlström, and Yeo]GWY17
G. Gutin, M. Wahlström, and A. Yeo, Rural Postman parameterized by the
  number of components of required edges, Journal of Computer and System
  Sciences 83 (2017), 121–131, 10.1016/j.jcss.2016.06.001.

[Hermelin et al.(2015)Hermelin, Kratsch, Sołtys, Wahlström, and
  Wu]HKS+15b
D. Hermelin, S. Kratsch, K. Sołtys, M. Wahlström, and X. Wu, A
  completeness theory for polynomial (Turing) kernelization, Algorithmica
  71 (2015), 702–730, 10.1007/s00453-014-9910-8.

[Hierholzer and Wiener(1873)]HW73
C. Hierholzer and C. Wiener, Ueber die Möglichkeit, einen Linienzug
  ohne Wiederholung und ohne Unterbrechung zu umfahren, Mathematische Annalen
  6 (1873), 30–32, 10.1007/BF01442866.

[Hà et al.(2014)Hà, Bostel, Langevin, and Rousseau]HBLR14
M. H. Hà, N. Bostel, A. Langevin, and L.-M. Rousseau, Solving the
  close-enough arc routing problem, Networks 63 (2014), 107–118,
  10.1002/net.21525.

[Jansen(1993)]Jan93
K. Jansen, Bounds for the general capacitated routing problem, Networks
  23 (1993), 165–173, 10.1002/net.3230230304.

[Karpinski et al.(2015)Karpinski, Lampis, and Schmied]KLS15
M. Karpinski, M. Lampis, and R. Schmied, New inapproximability bounds for
  TSP, Journal of Computer and System Sciences 81 (2015),
  1665–1677, 10.1016/j.jcss.2015.06.003.

[Krithika et al.(2018)Krithika, Majumdar, and Raman]KMR18
R. Krithika, D. Majumdar, and V. Raman, Revisiting connected vertex
  cover: FPT algorithms and lossy kernels, Theory of Computing Systems
  62 (2018), 1690–1714, 10.1007/s00224-017-9837-y.

[Krithika et al.(2016)Krithika, Misra, Rai, and Tale]KMRT16
R. Krithika, P. Misra, A. Rai, and P. Tale, Lossy kernels for graph
  contraction problems, A. Lal, S. Akshay, S. Saurabh, and S. Sen (eds.),
  FSTTCS 2016, Schloss Dagstuhl–Leibniz-Zentrum für Informatik,
  Dagstuhl, Germany, Leibniz International Proceedings in Informatics
  (LIPIcs), vol. 65, 2016, pp. 23:1–23:14,
  10.4230/LIPIcs.FSTTCS.2016.23.

[Lenstra and Rinnooy Kan(1976)]LR76
J. K. Lenstra and A. H. G. Rinnooy Kan, On general routing problems,
  Networks 6 (1976), 273–280, 10.1002/net.3230060305.

[Lokshtanov et al.(2017)Lokshtanov, Panolan, Ramanujan, and
  Saurabh]LPRS17
D. Lokshtanov, F. Panolan, M. S. Ramanujan, and S. Saurabh, Lossy
  kernelization, H. Hatami, P. McKenzie, and V. King (eds.), STOC 2017,
  ACM, 2017, pp. 224–237, 10.1145/3055399.3055456.

[Marx and Végh(2015)]MV15
D. Marx and L. A. Végh, Fixed-parameter algorithms for minimum-cost
  edge-connectivity augmentation, ACM Transactions on Algorithms 11
  (2015), 27:1–27:24, 10.1145/2700210.

[Orloff(1974)]Orl74
C. S. Orloff, A fundamental problem in vehicle routing, Networks
  4 (1974), 35–64, 10.1002/net.3230040105.

[Reinelt et al.(2008)Reinelt, Theis, and Wenger]RTW08
G. Reinelt, D. O. Theis, and K. M. Wenger, Computing finest mincut
  partitions of a graph and application to routing problems, Discrete Applied
  Mathematics 156 (2008), 385–396, 10.1016/j.dam.2007.03.022.

[Schwartz(1980)]Sch80
J. T. Schwartz, Fast probabilistic algorithms for verification of
  polynomial identities, Journal of the ACM 27 (1980), 701–717,
  10.1145/322217.322225.

[Serdyukov(1974)]Ser74
A. I. Serdyukov, O zadache nakhozhdeniya minimal'nogo Eilerova
  mul'tigrafa dlya svyaznogo grafa so vzveshennymi rebrami, Upravlyaemye
  sistemy 12 (1974), 61–67,
  <http://nas1.math.nsc.ru/aim/journals/us/us12/us12_008.pdf>.

[Serdyukov(1978)]Ser78
A. I. Serdyukov, O nekotorykh ekstremal'nykh obkhodakh v grafakh,
  Upravlyaemye sistemy 17 (1978), 76–79,
  <http://nas1.math.nsc.ru/aim/journals/us/us17/us17_007.pdf>.

[Sorge et al.(2011)Sorge, van Bevern, Niedermeier, and
  Weller]SBNW11
M. Sorge, R. van Bevern, R. Niedermeier, and M. Weller, From few
  components to an Eulerian graph by adding arcs, P. Kolman and
  J. Kratochvíl (eds.), WG 2011, Springer, Lecture Notes in
  Computer Science, vol. 6986, 2011, pp. 307–318,
  10.1007/978-3-642-25870-1_28.

[Sorge et al.(2012)Sorge, van Bevern, Niedermeier, and
  Weller]SBNW12
M. Sorge, R. van Bevern, R. Niedermeier, and M. Weller, A new view on
  Rural Postman based on Eulerian Extension and Matching, Journal of
  Discrete Algorithms 16 (2012), 12–33,
  10.1016/j.jda.2012.04.007.

[Ulusoy(1985)]Ulu85
G. Ulusoy, The fleet size and mix problem for capacitated arc routing,
  European Journal of Operational Research 22 (1985), 329–337,
  10.1016/0377-2217(85)90252-8.

[Wøhlk(2008)]Woe08
S. Wøhlk, An approximation algorithm for the Capacitated Arc Routing
  Problem, The Open Operational Research Journal 2 (2008), 8–12,
  10.2174/1874243200802010008.

[Zippel(1979)]Zip79
R. Zippel, Probabilistic algorithms for sparse polynomials, E. W. Ng
  (ed.), EUROSAM 1979, Springer, Lecture Notes in Computer
  Science, vol. 72, 1979, pp. 216–226, 10.1007/3-540-09519-5_73.


 





