Parameterized algorithms and data reduction for safe convoy routing
Parameterized algorithms and data reduction for safe convoy routing
复制标题
用于安全车队路线的参数化算法和数据缩减
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
O. Tsidulko
中科院分区：
文献类型：
--
作者：
René van Bevern;T. Fluschnik;O. Tsidulko
我们研究了一个通过运输网络安全路由车队的问题，其中与车队行驶路径相邻的任何顶点都需要额外的预防措施：给定图 G=(V,E)、V 中的两个顶点 s,t 和两个整数 k,l，我们搜索一条最多有 k 个顶点和最多 l 个邻居的简单 s-t-路径。我们研究两种类型的交通网络中的问题：由道路网络形成的交叉数较小的图，以及由水道形成的树状图。对于具有恒定交叉数的图，我们提供了次指数 2^O(sqrt n) 时间算法并证明了匹配的下界。我们还展示了一种多项式时间数据缩减算法，该算法可将任何问题实例缩减为输入图的顶点覆盖数中大小多项式的等效实例（所谓的问题内核）。相比之下，我们表明一般图中的问题很难预处理。对于树状图，我们对树宽为 tw 的图获得 2^O(tw) * l^2 * n 次算法，表明不存在 tw 中大小多项式的问题核，但在输入图的反馈边数中显示大小多项式的问题核。
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 s-t-path 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 tree-like 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 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 2^O(tw) * l^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.