# Combinatorics Seminar

When: Sunday, April 6, 10am

Where: Schreiber 309

Speaker: Gregory Z. Gutin (Royal Holloway, University of
London)

Title: Planning for Snow Plowing in Berlin: Parameterized
Rural Postman Problem

## Abstract:

The Directed Rural Postman Problem (DRPP) can be formulated as
follows: given a strongly connected directed multigraph $D=(V,A)$
with nonnegative integral weights on the arcs, a subset $R$ of $A$
and a nonnegative integer $\ell$, decide whether $D$ has a closed
directed walk containing every arc of $R$ and of total weight at most
$\ell$. DRPP is NP-complete. Let $k$ be the number of weakly
connected components in the subgraph of $D$ induced by $R$.
Sorge et al. (2012) asked whether the DRPP is fixed-parameter
tractable (FPT) when parameterized by $k$, i.e., whether there is an
algorithm of running time $O^*(f(k))$ where $f$ is a function of $k$
only and the $O^*$ notation suppresses polynomial factors.
Sorge et al. (2012) noted that this question is of significant
practical relevance (in Snow Plowing in Berlin, k is between 3 and
5) and has been open for more than thirty years. Using an algebraic
approach, we prove that DRPP has a randomized algorithm
with running time $O^*(2^k)$ when $\ell$ is bounded by a
polynomial in the number of vertices in $D$.

We also show that the same result holds for the undirected version
of DRPP, where $D$ is a connected undirected multigraph. We obtain
similar results for problems on constrained matchings in bipartite and
general undirected graphs.

Joint work with Magnus Wahlstrom (RHUL) and Anders Yeo (Singapore
Univ. Technology and Design)

redesigned by barak soreq