TY - GEN
A1 - Lindner, Niels
A1 - Reisch, Julian
T1 - Parameterized Complexity of Periodic Timetabling
N2 - Public transportation networks are typically operated with a periodic timetable. The Periodic Event Scheduling Problem (PESP) is the standard mathematical modelling tool for periodic timetabling. Since PESP can be solved in linear time on trees, it is a natural question to ask whether there are polynomial-time algorithms for input networks of bounded treewidth. We show that deciding the feasibility of a PESP instance is NP-hard even when the treewidth is 2, the branchwidth is 2, or the carvingwidth is 3. Analogous results hold for the optimization of reduced PESP instances, where the feasibility problem is trivial. To complete the picture, we present two pseudo-polynomial-time dynamic programming algorithms solving PESP on input networks with bounded tree- or branchwidth. We further analyze the parameterized complexity of PESP with bounded cyclomatic number, diameter, or vertex cover number. For event-activity networks with a special -- but standard -- structure, we give explicit and sharp bounds on the branchwidth in terms of the maximum degree and the carvingwidth of an underlying line network. Finally, we investigate several parameters on the smallest instance of the benchmarking library PESPlib.
T3 - ZIB-Report - 20-15
KW - Parameterized complexity
KW - Periodic timetabling
KW - Treewidth
KW - Branchwidth
KW - Carvingwidth
KW - Periodic Event Scheduling Problem
Y1 - 2020
UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/7831
UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-78314
SN - 1438-0064
ER -