Most transportation networks are inherently temporal: Connections (e.g. flights, train runs) are only available at certain, scheduled times. When transporting passengers or commodities, this fact must be considered for the the planning of itineraries. This has already led to several well-studied algorithmic problems on temporal graphs. The difficulty of the described task is increased by the fact that connections are often unreliable -- in particular, many modes of transportation suffer from occasional delays. If these delays cause subsequent connections to be missed, the consequences can be severe. Thus, it is a vital problem to design itineraries that are robust to (small) delays. We initiate the study of this problem from a parameterized complexity perspective by proving its NP-completeness as well as several hardness and tractability results for natural parameterizations.
翻译:大多数运输网络本来就是时间性的:连接(如航班、列车运行)只在特定时间提供,在运送乘客或商品时,在规划行程时必须考虑到这一事实,这已经导致在时间图上出现若干经过充分研究的算法问题,所述任务的困难因连接往往不可靠而增加,特别是许多运输方式有时会发生延误,如果这些延误导致随后的连接被错失,后果可能很严重。因此,设计对(小)延误具有活力的路线是一个重大问题。我们从参数化的复杂性角度出发,通过证明NP的完整以及自然参数化的若干硬性和可移动性结果,开始研究这一问题。