Parameterized Algorithms and Data Reduction for Safe Convoy Routing

Till Fluschnik (TU Berlin)

We study a problem that models safely routing a convoy through a transportation network, where any vertex adjacent to the travel path of the convoy requires additional precaution: Given a graph \(G = (V, E)\), two vertices \(s, t \in V\), and two integers \(k\), \(\ell\), we search for a simple \(s\)-\(t\)-path with at most \(k\) vertices and at most \(\ell\) neighbors. We study the problem in two types of transportation networks: graphs with small crossing number, as formed by road networks, and tree-like graphs, as formed by waterways.

In this talk, we give an overview of our results and present the following two results in more detail. For graphs with constant crossing number, we show a polynomial-time data reduction algorithm that reduces any problem instance to an equivalent instance (a so-called problem kernel) of size polynomial in the vertex cover number vc of the input graph. In contrast, we show that the problem in general graphs is hard to preprocess regarding vc.

This is joint work with René van Bevern and Oxana Yu. Tsidulko.

Back to the research colloquium site.