TY - GEN

T1 - Parameterized algorithms and data reduction for safe convoy routing

AU - Van Bevern, René

AU - Fluschnik, Till

AU - Tsidulko, Oxana Yu

N1 - Publisher Copyright: © 2018 René van Bevern, Till Fluschnik, and Oxana Yu. Tsidulko.

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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 ∈ V, and two integers k, ℓ, we search for a simple s-tpath with at most k vertices and at most ℓ 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. For graphs with constant crossing number, we provide a subexponential 2O(√n)-time algorithm and prove a matching lower bound. We also 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 of the input graph. In contrast, we show that the problem in general graphs is hard to preprocess. Regarding tree-like graphs, we obtain a 2O(tw) · ℓ2 · n-time 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.

AB - 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 ∈ V, and two integers k, ℓ, we search for a simple s-tpath with at most k vertices and at most ℓ 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. For graphs with constant crossing number, we provide a subexponential 2O(√n)-time algorithm and prove a matching lower bound. We also 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 of the input graph. In contrast, we show that the problem in general graphs is hard to preprocess. Regarding tree-like graphs, we obtain a 2O(tw) · ℓ2 · n-time 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.

KW - Fixed-parameter tractability

KW - NP-hard problem

KW - Problem kernelization

KW - Secluded solution

KW - Shortest path

UR - http://www.scopus.com/inward/record.url?scp=85053278906&partnerID=8YFLogxK

UR - https://elibrary.ru/item.asp?id=35750926

U2 - 10.4230/OASIcs.ATMOS.2018.10

DO - 10.4230/OASIcs.ATMOS.2018.10

M3 - Conference contribution

AN - SCOPUS:85053278906

SN - 9783959770965

VL - 65

BT - 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2018

Y2 - 23 August 2018 through 24 August 2018

ER -