Planning for Snow Plowing in Berlin: Parameterized Rural Postman Problem

Professor Gregory Gutin ( Royal Holloway, University of London )

31Jan
16:00 31st January 2014 ( week 2, Hilary Term 2014 )
Room 278, Oxford e-Research Centre, 7 Keble Road

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 l, decide whether D has a closed directed walk containing every arc of R and of total weight at most l. DRPP is NP-complete. Let k be the number of weakly connected components in the 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 false negatives of running time O^*(2^k) when l 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.

Speaker bio

Gregory Gutin received his MSc in Mathematics in 1979 from Gomel State University, Belarus. He worked in high school and research institutes of Belarus from 1979-1990. He studied for PhD under Professor Noga Alon at the School of Mathematics, Tel Aviv University, Israel, and received his PhD (with distinction) in 1993. Between 1993 and 1996 he held visiting positions in the Department of Mathematics and Computer Science, Odense University, Denmark and then became a lecturer at the Department of Mathematics, Brunel University, UK. Since 1 September 2000, Gregory has been Professor of Computer Science, Department of Computer Science, Royal Holloway, University of London.

Gutin's main research interests include graphs and combinatorics (theory, algorithms and applications), parameterized algorithmics and combinatorial optimization. G. Gutin has more than 150 papers published or accepted for publication in refereed journals and conference proceedings.