van Bevern, René ;
Fluschnik, Till ;
Tsidulko, Oxana Yu.
Parameterized Algorithms and Data Reduction for Safe Convoy Routing
Abstract
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,l, we search for a simple stpath with at most k vertices and at most l neighbors. We study the problem in two types of transportation networks: graphs with small crossing number, as formed by road networks, and treelike graphs, as formed by waterways. For graphs with constant crossing number, we provide a subexponential 2^O(sqrt n)time algorithm and prove a matching lower bound. We also show a polynomialtime data reduction algorithm that reduces any problem instance to an equivalent instance (a socalled problem kernel) of size polynomial in the vertex cover number of the input graph. In contrast, we show that the problem in general graphs is hard to preprocess. Regarding treelike graphs, we obtain a 2^O(tw) * l^2 * ntime algorithm for graphs of treewidth tw, show that there is no problem kernel with size polynomial in tw, yet show a problem kernel with size polynomial in the feedback edge number of the input graph.
BibTeX  Entry
@InProceedings{vanbevern_et_al:OASIcs:2018:9715,
author = {Ren{\'e} van Bevern and Till Fluschnik and Oxana Yu. Tsidulko},
title = {{Parameterized Algorithms and Data Reduction for Safe Convoy Routing}},
booktitle = {18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
pages = {10:110:19},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783959770965},
ISSN = {21906807},
year = {2018},
volume = {65},
editor = {Ralf Bornd{\"o}rfer and Sabine Storandt},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9715},
URN = {urn:nbn:de:0030drops97157},
doi = {10.4230/OASIcs.ATMOS.2018.10},
annote = {Keywords: NPhard problem, fixedparameter tractability, problem kernelization, shortest path, secluded solution}
}
28.08.2018
Keywords: 

NPhard problem, fixedparameter tractability, problem kernelization, shortest path, secluded solution 
Seminar: 

18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Issue date: 

2018 
Date of publication: 

28.08.2018 