{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T03:14:33Z","timestamp":1769829273681,"version":"3.49.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T00:00:00Z","timestamp":1644883200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T00:00:00Z","timestamp":1644883200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2046\/1"],"award-info":[{"award-number":["EXC-2046\/1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["project ID: 390685689"],"award-info":[{"award-number":["project ID: 390685689"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sched"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Public transportation networks are typically operated with a periodic timetable. The periodic event scheduling problem (PESP) is the standard mathematical modeling tool for periodic timetabling. PESP is a computationally very challenging problem: For example, solving the instances of the benchmarking library PESPlib to optimality seems out of reach. Since PESP can be solved in linear time on trees, and the treewidth is a rather small graph parameter in the networks of the PESPlib, it is a natural question to ask whether there are polynomial-time algorithms for input networks of bounded treewidth, or even better, fixed-parameter tractable algorithms. 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. Moreover, we show W[1]-hardness of the general feasibility problem with respect to treewidth, which means that we can most likely only accomplish pseudo-polynomial-time algorithms on input networks with bounded tree- or branchwidth. We present two such algorithms based on dynamic programming. We further analyze the parameterized complexity of PESP with bounded cyclomatic number, diameter, or vertex cover number. For event-activity networks with a special\u2014but standard\u2014structure, 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.<\/jats:p>","DOI":"10.1007\/s10951-021-00719-1","type":"journal-article","created":{"date-parts":[[2022,2,15]],"date-time":"2022-02-15T05:03:17Z","timestamp":1644901397000},"page":"157-176","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["An analysis of the parameterized complexity of periodic timetabling"],"prefix":"10.1007","volume":"25","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8337-4387","authenticated-orcid":false,"given":"Niels","family":"Lindner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julian","family":"Reisch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,2,15]]},"reference":[{"issue":"1","key":"719_CR1","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S Arnborg","year":"1989","unstructured":"Arnborg, S., & Proskurowski, A. (1989). Linear time algorithms for NP-hard problems restricted to partial $$k$$-trees. Discrete Applied Mathematics, 23(1), 11\u201324.","journal-title":"Discrete Applied Mathematics"},{"issue":"13","key":"719_CR2","doi-asserted-by":"publisher","first-page":"1888","DOI":"10.1016\/j.dam.2013.02.036","volume":"161","author":"R Belmonte","year":"2013","unstructured":"Belmonte, R., & van\u2019t Hof, P. (2013). Characterizing graphs of small carving-width. Discrete Applied Mathematics, 161(13), 1888\u20131893.","journal-title":"Discrete Applied Mathematics"},{"issue":"6","key":"719_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H. L. (1996). A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6), 1305\u20131317.","journal-title":"SIAM Journal on Computing"},{"key":"719_CR4","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1007\/3-540-63165-8_217","volume-title":"Automata, languages and programming","author":"HL Bodlaender","year":"1997","unstructured":"Bodlaender, H. L., & Thilikos, D. M. (1997). Constructive linear time algorithms for branchwidth. In P. Degano, R. Gorrieri, & A. Marchetti-Spaccamela (Eds.), Automata, languages and programming (pp. 627\u2013637). Berlin: Springer."},{"key":"719_CR5","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1007\/s004530010070","volume":"29","author":"HL Bodlaender","year":"2001","unstructured":"Bodlaender, H. L., & van Antwerpen-de Fluiter, B. (2001). Parallel algorithms for series parallel graphs and graphs with treewidth two. Algorithmica, 29, 534\u2013559.","journal-title":"Algorithmica"},{"key":"719_CR6","doi-asserted-by":"crossref","unstructured":"Bornd\u00f6rfer, R., Lindner, N., & Roth, S. (2019). A concurrent approach to the periodic event scheduling problem. Journal of Rail Transport Planning & Management, 100\u2013175.","DOI":"10.1016\/j.jrtpm.2019.100175"},{"key":"719_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, F. V., Kowalik, \u0141, Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., & Saurabh, S. (2015). Parameterized algorithms. Cham: Springer."},{"key":"719_CR8","unstructured":"Dell, H., Komusiewicz, C., Talmon, N., & Weller, M. (2018). The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In D. Lokshtanov & N. Nishimura (Eds.), 12th international symposium on parameterized and exact computation (IPEC 2017), volume 89 of Leibniz international proceedings in informatics (LIPIcs), Dagstuhl (pp. 30:1\u201330:12). Germany: Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"719_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized complexity. Monographs in computer science","author":"RG Downey","year":"1999","unstructured":"Downey, R. G., & Fellows, M. R. (1999). Parameterized complexity. Monographs in computer science. New York: Springer."},{"issue":"3","key":"719_CR10","doi-asserted-by":"publisher","first-page":"461","DOI":"10.7155\/jgaa.00468","volume":"22","author":"D Eppstein","year":"2018","unstructured":"Eppstein, D. (2018). The effect of planarization on width. Journal of Graph Algorithms and Applications, 22(3), 461\u2013481.","journal-title":"Journal of Graph Algorithms and Applications"},{"key":"719_CR11","unstructured":"Erd\u0151s, P., Rubin, A. L., & Taylor, H. (1980). Choosability in graphs. In Combinatorics, graph theory and computing, proceedings of the west coast conference, Arcata\/California, 1979 (pp. 125\u2013157)."},{"issue":"2","key":"719_CR12","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"MR Fellows","year":"2011","unstructured":"Fellows, M. R., Fomin, F. V., Lokshtanov, D., Rosamond, F., Saurabh, S., Szeider, S., & Thomassen, C. (2011). On the complexity of some colorful problems parameterized by treewidth. Information and Computation, 209(2), 143\u2013153.","journal-title":"Information and Computation"},{"key":"719_CR13","doi-asserted-by":"crossref","unstructured":"Fiala, J., Golovach, P. A., & Kratochv\u00edl, J. (2011). Parameterized complexity of coloring problems: Treewidth versus vertex cover. Theoretical Computer Science, 412(23), 2513\u20132523. Theory and Applications of Models of Computation (TAMC 2009).","DOI":"10.1016\/j.tcs.2010.10.043"},{"key":"719_CR14","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability. San Francisco: W. H. Freeman and Company."},{"key":"719_CR15","unstructured":"Goerigk, M. (2012). PESPlib\u2014A benchmark library for periodic event scheduling. http:\/\/num.math.uni-goettingen.de\/m.goerigk\/pesplib\/."},{"key":"719_CR16","unstructured":"Goerigk, M. & Liebchen, C. (2017). An improved algorithm for the periodic timetabling problem. In ATMOS, volume\u00a059 of OASICS (pp. 12:1\u201312:14). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik."},{"key":"719_CR17","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/s12469-013-0072-x","volume":"5","author":"M Goerigk","year":"2013","unstructured":"Goerigk, M., Schachtebeck, M., & Sch\u00f6bel, A. (2013). Evaluating line concepts using travel times and robustness. Public Transport, 5, 267\u2013284.","journal-title":"Public Transport"},{"key":"719_CR18","doi-asserted-by":"crossref","unstructured":"Hadjiat, M., & Maurras, J. F. (1997). A strongly polynomial algorithm for the minimum cost tension problem. Discrete Mathematics, 165\u2013166, 377\u2013394. Graphs and Combinatorics.","DOI":"10.1016\/S0012-365X(96)00185-9"},{"key":"719_CR19","doi-asserted-by":"crossref","unstructured":"Hagberg, A.\u00a0A., Schult, D.\u00a0A., & Swart, P.\u00a0J. (2008). Exploring Network Structure, Dynamics, and Function using NetworkX. In Varoquaux, G., Vaught, T., & Millman, J. (Eds.), Proceedings of the 7th python in science conference (pp. 11\u201315), Pasadena, CA, USA.","DOI":"10.25080\/TCWV9851"},{"key":"719_CR20","doi-asserted-by":"crossref","unstructured":"Hamann, M., & Strasser, B. (2018). Graph bisection with pareto optimization. Journal of Experimental Algorithmics 23","DOI":"10.1145\/3173045"},{"key":"719_CR21","first-page":"85","volume-title":"Reducibility among combinatorial problems","author":"RM Karp","year":"1972","unstructured":"Karp, R. M. (1972). Reducibility among combinatorial problems (pp. 85\u2013103). Boston: Springer."},{"key":"719_CR22","doi-asserted-by":"crossref","unstructured":"Kloks, T. (1994). Treewidth, computations and approximations. Lecture Notes in Computer Science (Vol. 842). New York: Springer.","DOI":"10.1007\/BFb0045375"},{"key":"719_CR23","unstructured":"Liebchen, C. (2006). Periodic timetable optimization in public transport. PhD thesis, Technische Universit\u00e4t Berlin."},{"key":"719_CR24","doi-asserted-by":"crossref","unstructured":"Liebchen, C. & M\u00f6hring, R.\u00a0H. (2007). The modeling power of the periodic event scheduling problem: Railway timetables\u2014And beyond. In Algorithmic methods for railway optimization (pp. 3\u201340). Springer.","DOI":"10.1007\/978-3-540-74247-0_1"},{"key":"719_CR25","unstructured":"Lindner, N., & Liebchen, C. (2019). New perspectives on PESP: T-partitions and separators. In V. Cacchiani & A. Marchetti-Spaccamela (Eds.), 19th Symposium on algorithmic approaches for transportation modelling, optimization, and systems (ATMOS 2019), volume 75 of OpenAccess series in informatics (OASIcs) (pp. 2:1\u20132:18). Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"719_CR26","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/j.cor.2018.07.020","volume":"100","author":"M Mnich","year":"2018","unstructured":"Mnich, M., & van Bevern, R. (2018). Parameterized complexity of machine scheduling: 15 open problems. Computers&amp; Operations Research, 100, 254\u2013261.","journal-title":"Computers & Operations Research"},{"key":"719_CR27","unstructured":"Nachtigall, K. (1993). Exact solution methods for periodic programs. Technical Report 14\/93, Hildesheimer Informatikberichte."},{"key":"719_CR28","unstructured":"Nachtigall, K. (1998). Periodic network optimization and fixed interval timetables. Habilitation thesis, Universit\u00e4t Hildesheim."},{"key":"719_CR29","volume-title":"8th workshop on algorithmic approaches for transportation modeling, optimization, and systems (ATMOS\u201908), volume 9 of OpenAccess Series in Informatics (OASIcs)","author":"K Nachtigall","year":"2008","unstructured":"Nachtigall, K., & Opitz, J. (2008). Solving periodic timetable optimisation problems by modulo simplex calculations. In M. Fischetti & P. Widmayer (Eds.), 8th workshop on algorithmic approaches for transportation modeling, optimization, and systems (ATMOS\u201908), volume 9 of OpenAccess Series in Informatics (OASIcs). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik: Dagstuhl, Germany."},{"key":"719_CR30","doi-asserted-by":"crossref","unstructured":"Nestoridis, N. V., & Thilikos, D. M. (2014). Square roots of minor closed graph classes. Discrete Applied Mathematics, 168, 34\u201339. Fifth Workshop on Graph Classes, Optimization, and Width Parameters, Daejeon, Korea, October 2011.","DOI":"10.1016\/j.dam.2013.05.026"},{"key":"719_CR31","unstructured":"Odijk, M.\u00a0A. (1994). Construction of periodic timetables, part 1: A cutting plane algorithm. Technical Report 94-61, TU Delft."},{"key":"719_CR32","unstructured":"P\u00e4tzold, J., Schiewe, A., Schiewe, P., & Sch\u00f6bel, A. (2017). Look-ahead approaches for integrated planning in public transportation. In ATMOS, volume\u00a059 of OASICS (pp. 17:1\u201317:16). Schloss Dagstuhl\u2014Leibniz-Zentrum f\u00fcr Informatik."},{"key":"719_CR33","unstructured":"P\u00e4tzold, J., & Sch\u00f6bel, A. (2016). A matching approach for periodic timetabling. of OpenAccess Series in Informatics (OASIcs) (pp. 1:1\u20131:15). Dagstuhl, GermanyIn M. Goerigk & R. Werneck (Eds.), 16th workshop on algorithmic approaches for transportation modelling, optimization, and systems (ATMOS 2016) (Vol. 54, pp. 2190\u20136807). ISSN: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"719_CR34","doi-asserted-by":"crossref","unstructured":"Robertson, N., & Seymour, P. (1984). Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1), 49\u201364.","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"719_CR35","doi-asserted-by":"crossref","unstructured":"Robertson, N., & Seymour, P. (1991). Graph minors. X. Obstructions to tree-decomposition. Journal of Combinatorial Theory, Series B, 52(2), 153\u2013190.","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"719_CR36","doi-asserted-by":"crossref","unstructured":"Robertson, N., & Seymour, P. (1995). Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory, Series B, 63(1), 65\u2013110.","DOI":"10.1006\/jctb.1995.1006"},{"key":"719_CR37","volume-title":"Theory of linear and integer programming","author":"A Schrijver","year":"1986","unstructured":"Schrijver, A. (1986). Theory of linear and integer programming. New York: Wiley."},{"key":"719_CR38","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1016\/j.trc.2016.11.018","volume":"74","author":"A Sch\u00f6bel","year":"2017","unstructured":"Sch\u00f6bel, A. (2017). An eigenmodel for iterative line planning, timetabling and vehicle scheduling in public transportation. Transportation Research Part C: Emerging Technologies, 74, 348\u2013365.","journal-title":"Transportation Research Part C: Emerging Technologies"},{"issue":"4","key":"719_CR39","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1137\/0402049","volume":"2","author":"P Serafini","year":"1989","unstructured":"Serafini, P., & Ukovich, W. (1989). A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4), 550\u2013581.","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"2","key":"719_CR40","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P Seymour","year":"1994","unstructured":"Seymour, P., & Thomas, R. (1994). Call routing and the ratcatcher. Combinatorica, 14(2), 217\u2013241.","journal-title":"Combinatorica"},{"issue":"4","key":"719_CR41","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1007\/s10878-018-0353-z","volume":"37","author":"H Tamaki","year":"2019","unstructured":"Tamaki, H. (2019). Positive-instance driven dynamic programming for treewidth. Journal of Combinatorial Optimization, 37(4), 1283\u20131311.","journal-title":"Journal of Combinatorial Optimization"},{"key":"719_CR42","unstructured":"van Heuven van Staereling, I. (2018). Tree decomposition methods for the periodic event scheduling problem. In R. Bornd\u00f6rfer & S. Storandt (Eds.), 18th workshop on algorithmic approaches for transportation modelling, optimization, and systems (ATMOS 2018), volume 65 of OpenAccess Series in Informatics (OASIcs) (pp. 6:1\u20136:13). Dagstuhl. Germany: Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"719_CR43","first-page":"3","volume":"29","author":"VG Vizing","year":"1976","unstructured":"Vizing, V. G. (1976). Vertex colorings with given colors. Diskretnyi Analiz, 29, 3\u201310.","journal-title":"Diskretnyi Analiz"}],"container-title":["Journal of Scheduling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00719-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10951-021-00719-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10951-021-00719-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T15:41:31Z","timestamp":1726674091000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10951-021-00719-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,15]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["719"],"URL":"https:\/\/doi.org\/10.1007\/s10951-021-00719-1","relation":{},"ISSN":["1094-6136","1099-1425"],"issn-type":[{"value":"1094-6136","type":"print"},{"value":"1099-1425","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,15]]},"assertion":[{"value":"22 December 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}