7831
eng
reportzib
0
--
2020-05-11
--
Parameterized Complexity of Periodic Timetabling
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.
1438-0064
urn:nbn:de:0297-zib-78314
Niels Lindner
Niels Lindner
Julian Reisch
ZIB-Report
20-15
eng
uncontrolled
Parameterized complexity
eng
uncontrolled
Periodic timetabling
eng
uncontrolled
Treewidth
eng
uncontrolled
Branchwidth
eng
uncontrolled
Carvingwidth
eng
uncontrolled
Periodic Event Scheduling Problem
COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
MODAL-Gesamt
Lindner, Niels
MathPlus-Incubator-Timetabling
MODAL-MobilityLab
https://opus4.kobv.de/opus4-zib/files/7831/pesp-treewidth.pdf