{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:22:33Z","timestamp":1772119353153,"version":"3.50.1"},"reference-count":71,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T00:00:00Z","timestamp":1740441600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T00:00:00Z","timestamp":1740441600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/T004878\/1"],"award-info":[{"award-number":["EP\/T004878\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/T004878\/1"],"award-info":[{"award-number":["EP\/T004878\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1456\/18"],"award-info":[{"award-number":["1456\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["949707"],"award-info":[{"award-number":["949707"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005005","name":"Ben-Gurion University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005005","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    This work investigates the parameterised complexity of counting temporal paths. The problem of counting temporal paths is mainly motivated by temporal betweenness computation. The betweenness centrality of a vertex\n                    <jats:italic>v<\/jats:italic>\n                    is an important centrality measure that quantifies how many optimal paths between pairs of other vertices visit\n                    <jats:italic>v<\/jats:italic>\n                    . Computing betweenness centrality in a temporal graph, in which the edge set may change over discrete timesteps, requires us to count temporal paths that are optimal with respect to some criterion. For several natural notions of optimality, including\n                    <jats:italic>foremost<\/jats:italic>\n                    or\n                    <jats:italic>fastest<\/jats:italic>\n                    temporal paths, this counting problem reduces to\n                    <jats:sc>#Temporal Path<\/jats:sc>\n                    , the problem of counting\n                    <jats:italic>all<\/jats:italic>\n                    temporal paths between a fixed pair of vertices; like the problems of counting foremost and fastest temporal paths,\n                    <jats:sc>#Temporal Path<\/jats:sc>\n                    is #P-hard in general. Motivated by the many applications of this intractable problem, we initiate a systematic study of the parameterised and approximation complexity of\n                    <jats:sc>#Temporal Path<\/jats:sc>\n                    . We show that the problem presumably does not admit an FPT-algorithm for the feedback vertex number of the static underlying graph, and that it is hard to approximate in general. On the positive side, we prove several exact and approximate FPT-algorithms for special cases.\n                  <\/jats:p>","DOI":"10.1007\/s00453-025-01301-3","type":"journal-article","created":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T15:40:46Z","timestamp":1740498046000},"page":"736-782","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Counting Temporal Paths"],"prefix":"10.1007","volume":"87","author":[{"given":"Jessica","family":"Enright","sequence":"first","affiliation":[]},{"given":"Kitty","family":"Meeks","sequence":"additional","affiliation":[]},{"given":"Hendrik","family":"Molter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,2,25]]},"reference":[{"issue":"1","key":"1301_CR1","doi-asserted-by":"crossref","first-page":"35","DOI":"10.2307\/3033543","volume":"40","author":"LC Freeman","year":"1977","unstructured":"Freeman, L.C.: A set of measures of centrality based on betweenness. Sociometry 40(1), 35\u201341 (1977)","journal-title":"Sociometry"},{"issue":"2","key":"1301_CR2","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","volume":"25","author":"U Brandes","year":"2001","unstructured":"Brandes, U.: A faster algorithm for betweenness centrality. J. Math. Sociol. 25(2), 163\u2013177 (2001)","journal-title":"J. Math. Sociol."},{"issue":"3","key":"1301_CR3","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput. 8(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"1301_CR4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1140\/epjb\/e2015-60657-4","volume":"88","author":"P Holme","year":"2015","unstructured":"Holme, P.: Modern temporal network theory: a colloquium. Eur. Phys. J. B 88, 1\u201330 (2015)","journal-title":"Eur. Phys. J. B"},{"key":"1301_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-23495-9","volume-title":"Temporal Network Theory","author":"P Holme","year":"2019","unstructured":"Holme, P., Saram\u00e4ki, J.: Temporal Network Theory. Springer, New York (2019)"},{"key":"1301_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s13278-018-0537-7","volume":"8","author":"M Latapy","year":"2018","unstructured":"Latapy, M., Viard, T., Magnien, C.: Stream graphs and link streams for the modeling of interactions over time. Soc. Netw. Anal. Min. 8, 1\u201329 (2018)","journal-title":"Soc. Netw. Anal. Min."},{"issue":"4","key":"1301_CR7","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1080\/15427951.2016.1177801","volume":"12","author":"O Michail","year":"2016","unstructured":"Michail, O.: An introduction to temporal graphs: An algorithmic perspective. Internet Math. 12(4), 239\u2013280 (2016)","journal-title":"Internet Math."},{"issue":"4","key":"1301_CR8","doi-asserted-by":"crossref","first-page":"820","DOI":"10.1006\/jcss.2002.1829","volume":"64","author":"D Kempe","year":"2002","unstructured":"Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 820\u2013842 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"02","key":"1301_CR9","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1142\/S0129054103001728","volume":"14","author":"B-M Bui-Xuan","year":"2003","unstructured":"Bui-Xuan, B.-M., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(02), 267\u2013285 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"11","key":"1301_CR10","doi-asserted-by":"crossref","first-page":"2927","DOI":"10.1109\/TKDE.2016.2594065","volume":"28","author":"H Wu","year":"2016","unstructured":"Wu, H., Cheng, J., Ke, Y., Huang, S., Huang, Y., Wu, H.: Efficient algorithms for temporal path computation. IEEE Trans. Knowl. Data Eng. 28(11), 2927\u20132942 (2016)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"1301_CR11","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1017\/nws.2024.5","volume":"12","author":"S Bu\u00df","year":"2024","unstructured":"Bu\u00df, S., Molter, H., Niedermeier, R., Rymar, M.: Algorithmic aspects of temporal betweenness. Netw. Sci. 12(2), 160\u2013188 (2024)","journal-title":"Netw. Sci."},{"issue":"3","key":"1301_CR12","doi-asserted-by":"crossref","first-page":"173","DOI":"10.7155\/jgaa.00619","volume":"27","author":"M Rymar","year":"2023","unstructured":"Rymar, M., Molter, H., Nichterlein, A., Niedermeier, R.: Towards classifying the polynomial-time solvability of temporal betweenness centrality. J. Graph Algorithms Appl. 27(3), 173\u2013194 (2023)","journal-title":"J. Graph Algorithms Appl."},{"key":"1301_CR13","unstructured":"Habiba, H., Tantipathananandh, C., Berger-Wolf, T.: Betweenness centrality measure in dynamic networks. Technical Report 19, Department of Computer Science, University of Illinois at Chicago, Chicago. DIMACS Technical Report (2007)"},{"issue":"2","key":"1301_CR14","doi-asserted-by":"crossref","first-page":"026107","DOI":"10.1103\/PhysRevE.85.026107","volume":"85","author":"H Kim","year":"2012","unstructured":"Kim, H., Anderson, R.: Temporal node centrality in complex networks. Phys. Rev. E 85(2), 026107 (2012)","journal-title":"Phys. Rev. E"},{"key":"1301_CR15","doi-asserted-by":"crossref","unstructured":"Mutzel, P., Oettershagen, L.: On the enumeration of bicriteria temporal paths. In: Proceedings of the 15th Annual Conference on Theory and Applications of Models of Computation (TAMC \u201919). Lecture Notes in Computer Science, vol. 11436, pp. 518\u2013535 (2019)","DOI":"10.1007\/978-3-030-14812-6_32"},{"issue":"1","key":"1301_CR16","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1186\/s40649-017-0041-7","volume":"4","author":"AA Rad","year":"2017","unstructured":"Rad, A.A., Flocchini, P., Gaudet, J.: Computation and analysis of temporal betweenness in a knowledge mobilization network. Comput. Soc. Netw. 4(1), 5 (2017)","journal-title":"Comput. Soc. Netw."},{"issue":"1","key":"1301_CR17","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/s41109-020-00311-0","volume":"5","author":"M Bentert","year":"2020","unstructured":"Bentert, M., Himmel, A.-S., Nichterlein, A., Niedermeier, R.: Efficient computation of optimal temporal walks under waiting-time constraints. Appl. Netw. Sci. 5(1), 73 (2020)","journal-title":"Appl. Netw. Sci."},{"issue":"9","key":"1301_CR18","doi-asserted-by":"crossref","first-page":"2754","DOI":"10.1007\/s00453-021-00831-w","volume":"83","author":"A Casteigts","year":"2021","unstructured":"Casteigts, A., Himmel, A.-S., Molter, H., Zschoche, P.: Finding temporal paths under waiting time constraints. Algorithmica 83(9), 2754\u20132802 (2021)","journal-title":"Algorithmica"},{"key":"1301_CR19","unstructured":"F\u00fcchsle, E., Molter, H., Niedermeier, R., Renken, M.: Delay-robust routes in temporal graphs. In: Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS \u201922). LIPIcs, vol. 219, pp. 30\u201313015 (2022)"},{"issue":"1","key":"1301_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10458-022-09583-5","volume":"37","author":"N Klobas","year":"2023","unstructured":"Klobas, N., Mertzios, G.B., Molter, H., Niedermeier, R., Zschoche, P.: Interference-free walks in time: temporally disjoint paths. Auton. Agent. Multi Agent Syst. 37(1), 1 (2023)","journal-title":"Auton. Agent. Multi Agent Syst."},{"key":"1301_CR21","doi-asserted-by":"crossref","unstructured":"Kunz, P., Molter, H., Zehavi, M.: In which graph structures can we efficiently find temporally disjoint paths and walks? In: Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 180\u2013188 (2023)","DOI":"10.24963\/ijcai.2023\/21"},{"key":"1301_CR22","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.chaos.2014.12.009","volume":"72","author":"A Alsayed","year":"2015","unstructured":"Alsayed, A., Higham, D.J.: Betweenness in time dependent networks. Chaos Solitons Fractals 72, 35\u201348 (2015)","journal-title":"Chaos Solitons Fractals"},{"key":"1301_CR23","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-642-36461-7_2","volume-title":"Temporal Networks","author":"V Nicosia","year":"2013","unstructured":"Nicosia, V., Tang, J., Mascolo, C., Musolesi, M., Russo, G., Latora, V.: Graph metrics for temporal networks. In: Temporal Networks, pp. 15\u201340. Springer, Berlin (2013)"},{"issue":"3","key":"1301_CR24","doi-asserted-by":"crossref","first-page":"195","DOI":"10.7155\/jgaa.00620","volume":"27","author":"F Simard","year":"2023","unstructured":"Simard, F., Magnien, C., Latapy, M.: Computing betweenness centrality in link streams. J. Graph Algorithms Appl. 27(3), 195\u2013217 (2023)","journal-title":"J. Graph Algorithms Appl."},{"key":"1301_CR25","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1007\/978-3-642-36461-7_7","volume-title":"Temporal Networks","author":"J Tang","year":"2013","unstructured":"Tang, J., Leontiadis, I., Scellato, S., Nicosia, V., Mascolo, C., Musolesi, M., Latora, V.: Applications of temporal graph metrics to real-world networks. In: Temporal Networks, pp. 135\u2013159. Springer, Berlin (2013)"},{"key":"1301_CR26","doi-asserted-by":"crossref","unstructured":"Tang, J., Musolesi, M., Mascolo, C., Latora, V., Nicosia, V.: Analysing information flows and key mediators through temporal centrality metrics. In: Proceedings of the 3rd ACM Workshop on Social Network Systems, pp. 3\u2013136. ACM (2010)","DOI":"10.1145\/1852658.1852661"},{"issue":"3","key":"1301_CR27","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s41060-019-00189-x","volume":"9","author":"I Tsalouchidou","year":"2020","unstructured":"Tsalouchidou, I., Baeza-Yates, R., Bonchi, F., Liao, K., Sellis, T.: Temporal betweenness centrality in dynamic graphs. Int. J. Data Sci. Anal. 9(3), 257\u2013272 (2020)","journal-title":"Int. J. Data Sci. Anal."},{"key":"1301_CR28","unstructured":"Axiotis, K., Fotakis, D.: On the size and the approximability of minimum temporally connected subgraphs. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916), pp. 149\u2013114914 (2016)"},{"key":"1301_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2021.04.004","volume":"121","author":"A Casteigts","year":"2021","unstructured":"Casteigts, A., Peters, J.G., Schoeters, J.: Temporal cliques admit sparse spanners. J. Comput. Syst. Sci. 121, 1\u201317 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"1301_CR30","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1016\/j.tcs.2019.03.031","volume":"806","author":"T Fluschnik","year":"2020","unstructured":"Fluschnik, T., Molter, H., Niedermeier, R., Renken, M., Zschoche, P.: Temporal graph classes: A view through temporal separators. Theor. Comput. Sci. 806, 197\u2013218 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"1301_CR31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2023.01.004","volume":"135","author":"N Maack","year":"2023","unstructured":"Maack, N., Molter, H., Niedermeier, R., Renken, M.: On finding separators in temporal split and permutation graphs. J. Comput. Syst. Sci. 135, 1\u201314 (2023)","journal-title":"J. Comput. Syst. Sci."},{"key":"1301_CR32","doi-asserted-by":"crossref","first-page":"106229","DOI":"10.1016\/j.ipl.2021.106229","volume":"175","author":"H Molter","year":"2022","unstructured":"Molter, H.: The complexity of finding temporal separators under waiting time constraints. Inf. Process. Lett. 175, 106229 (2022)","journal-title":"Inf. Process. Lett."},{"key":"1301_CR33","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1016\/j.jcss.2019.07.006","volume":"107","author":"P Zschoche","year":"2020","unstructured":"Zschoche, P., Fluschnik, T., Molter, H., Niedermeier, R.: The complexity of finding separators in temporal graphs. J. Comput. Syst. Sci. 107, 72\u201392 (2020)","journal-title":"J. Comput. Syst. Sci."},{"issue":"Part B","key":"1301_CR34","doi-asserted-by":"crossref","first-page":"104890","DOI":"10.1016\/j.ic.2022.104890","volume":"285","author":"A Deligkas","year":"2022","unstructured":"Deligkas, A., Potapov, I.: Optimizing reachability sets in temporal graphs by delaying. Inf. Comput. 285(Part B), 104890 (2022)","journal-title":"Inf. Comput."},{"key":"1301_CR35","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.jcss.2021.01.007","volume":"119","author":"J Enright","year":"2021","unstructured":"Enright, J., Meeks, K., Mertzios, G.B., Zamaraev, V.: Deleting edges to restrict the size of an epidemic in temporal networks. J. Comput. Syst. Sci. 119, 60\u201377 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"1301_CR36","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.jcss.2020.08.001","volume":"115","author":"J Enright","year":"2021","unstructured":"Enright, J., Meeks, K., Skerman, F.: Assigning times to minimise reachability in temporal graphs. J. Comput. Syst. Sci. 115, 169\u2013186 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"1301_CR37","doi-asserted-by":"crossref","first-page":"103549","DOI":"10.1016\/j.jcss.2024.103549","volume":"144","author":"H Molter","year":"2024","unstructured":"Molter, H., Renken, M., Zschoche, P.: Temporal reachability minimization: delaying vs. deleting. J. Comput. Syst. Sci. 144, 103549 (2024)","journal-title":"J. Comput. Syst. Sci."},{"key":"1301_CR38","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.jcss.2021.04.001","volume":"120","author":"EC Akrida","year":"2021","unstructured":"Akrida, E.C., Mertzios, G.B., Spirakis, P.G., Raptopoulos, C.L.: The temporal explorer who returns to the base. J. Comput. Syst. Sci. 120, 179\u2013193 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"1301_CR39","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.ipl.2018.10.016","volume":"142","author":"HL Bodlaender","year":"2019","unstructured":"Bodlaender, H.L., Zanden, T.C.: On exploring always-connected temporal graphs of small pathwidth. Inf. Process. Lett. 142, 68\u201371 (2019)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1301_CR40","doi-asserted-by":"crossref","first-page":"688","DOI":"10.1007\/s00453-022-01018-7","volume":"85","author":"BM Bumpus","year":"2023","unstructured":"Bumpus, B.M., Meeks, K.: Edge exploration of temporal graphs. Algorithmica 85(3), 688\u2013716 (2023)","journal-title":"Algorithmica"},{"key":"1301_CR41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jcss.2021.01.005","volume":"119","author":"T Erlebach","year":"2021","unstructured":"Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. J. Comput. Syst. Sci. 119, 1\u201318 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"1301_CR42","unstructured":"Erlebach, T., Kammer, F., Luo, K., Sajenko, A., Spooner, J.T.: Two moves per time step make a difference. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP \u201919). LIPIcs, vol. 132, pp. 141\u2013114114 (2019)"},{"key":"1301_CR43","doi-asserted-by":"crossref","unstructured":"Erlebach, T., Spooner, J.T.: Non-strict temporal exploration. In: Proceedings of the 27th International Colloquium on Structural Information and Communication Complexity (SIROCCO \u201920). Lecture Notes in Computer Science, vol. 12156, pp. 129\u2013145 (2020)","DOI":"10.1007\/978-3-030-54921-3_8"},{"issue":"3","key":"1301_CR44","doi-asserted-by":"crossref","first-page":"907","DOI":"10.1007\/s00224-017-9757-x","volume":"61","author":"EC Akrida","year":"2017","unstructured":"Akrida, E.C., Gasieniec, L., Mertzios, G.B., Spirakis, P.G.: The complexity of optimal design of temporally connected graphs. Theory Comput. Syst. 61(3), 907\u2013944 (2017)","journal-title":"Theory Comput. Syst."},{"key":"1301_CR45","doi-asserted-by":"crossref","first-page":"103564","DOI":"10.1016\/j.jcss.2024.103564","volume":"146","author":"N Klobas","year":"2024","unstructured":"Klobas, N., Mertzios, G.B., Molter, H., Spirakis, P.G.: The complexity of computing optimum labelings for temporal connectivity. J. Comput. Syst. Sci. 146, 103564 (2024)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1301_CR46","doi-asserted-by":"crossref","first-page":"1416","DOI":"10.1007\/s00453-018-0478-6","volume":"81","author":"GB Mertzios","year":"2019","unstructured":"Mertzios, G.B., Michail, O., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. Algorithmica 81(4), 1416\u20131449 (2019)","journal-title":"Algorithmica"},{"key":"1301_CR47","unstructured":"F\u00fcchsle, E., Molter, H., Niedermeier, R., Renken, M.: Temporal connectivity: coping with foreseen and unforeseen delays. In: Proceedings of the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND \u201922). LIPIcs, vol. 221, pp. 17\u201311717 (2022)"},{"key":"1301_CR48","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.dam.2021.09.029","volume":"307","author":"R Haag","year":"2022","unstructured":"Haag, R., Molter, H., Niedermeier, R., Renken, M.: Feedback edge sets in temporal graphs. Discrete Appl. Math. 307, 65\u201378 (2022)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"1301_CR49","doi-asserted-by":"crossref","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892\u2013922 (2004)","journal-title":"SIAM J. Comput."},{"key":"1301_CR50","doi-asserted-by":"crossref","unstructured":"Arvind, V., Raman, V.: Approximation algorithms for some parameterized counting problems. In: Bose, P., Morin, P. (eds.) Proceedings of the 13th International Symposium on Algorithms and Computation (ISAAC\u201902). Lecture Notes in Computer Science, vol. 2518, pp. 453\u2013464 (2002)","DOI":"10.1007\/3-540-36136-7_40"},{"key":"1301_CR51","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, London (2013)"},{"key":"1301_CR52","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. In: Texts in Theoretical Computer Science. An EATCS Series, vol. XIV (2006)"},{"key":"1301_CR53","doi-asserted-by":"crossref","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.: Parameterized Algorithms. Springer, Cham (2015)"},{"key":"1301_CR54","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Dell, H., Husfeldt, T.: The parity of set systems under random restrictions with applications to exponential time problems. In: Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP \u201915), pp. 231\u2013242 (2015). Springer","DOI":"10.1007\/978-3-662-47672-7_19"},{"key":"1301_CR55","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"M Mitzenmacher","year":"2017","unstructured":"Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis, 2nd edn. Cambridge University Press, Cambridge (2017)","edition":"2"},{"key":"1301_CR56","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"MR Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 43, 169\u2013188 (1986)","journal-title":"Theor. Comput. Sci."},{"issue":"49","key":"1301_CR57","doi-asserted-by":"crossref","first-page":"4253","DOI":"10.1016\/j.tcs.2010.09.001","volume":"411","author":"M Jiang","year":"2010","unstructured":"Jiang, M.: On the parameterized complexity of some optimization problems related to multiple-interval graphs. Theor. Comput. Sci. 411(49), 4253\u20134262 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1301_CR58","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16(1), 47\u201356 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"5","key":"1301_CR59","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/s10951-014-0398-5","volume":"18","author":"R van Bevern","year":"2015","unstructured":"van Bevern, R., Mnich, M., Niedermeier, R., Weller, M.: Interval scheduling and colorful independent sets. J. Sched. 18(5), 449\u2013469 (2015)","journal-title":"J. Sched."},{"issue":"1","key":"1301_CR60","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s10951-018-0595-8","volume":"22","author":"M Bentert","year":"2019","unstructured":"Bentert, M., van Bevern, R., Niedermeier, R.: Inductive $$k$$-independent graphs and $$c$$-colorable subgraphs in scheduling: a review. J. Sched. 22(1), 3\u201320 (2019)","journal-title":"J. Sched."},{"key":"1301_CR61","first-page":"1","volume-title":"Graph Theory and Sparse Matrix Computation","author":"JR Blair","year":"1993","unstructured":"Blair, J.R., Peyton, B.: An introduction to chordal graphs and clique trees. In: Graph Theory and Sparse Matrix Computation, pp. 1\u201329. Springer, New York (1993)"},{"issue":"3","key":"1301_CR62","doi-asserted-by":"crossref","first-page":"483","DOI":"10.7155\/jgaa.00543","volume":"24","author":"M Bentert","year":"2020","unstructured":"Bentert, M., Dittmann, A., Kellerhals, L., Nichterlein, A., Niedermeier, R.: An adaptive version of Brandes\u2019 algorithm for betweenness centrality. J. Graph Algorithms Appl. 24(3), 483\u2013522 (2020)","journal-title":"J. Graph Algorithms Appl."},{"key":"1301_CR63","series-title":"Encyclopedia of Mathematics and its Applications","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511977619","volume-title":"Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach","author":"B Courcelle","year":"2012","unstructured":"Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic: A Language-Theoretic Approach. Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge (2012)"},{"key":"1301_CR64","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1016\/j.dam.2016.09.002","volume":"217","author":"M Yamamoto","year":"2017","unstructured":"Yamamoto, M.: Approximately counting paths and cycles in a graph. Discrete Appl. Math. 217, 381\u2013387 (2017)","journal-title":"Discrete Appl. Math."},{"key":"1301_CR65","doi-asserted-by":"crossref","unstructured":"Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., Sahinalp, S.C.: Biomolecular network motif counting and discovery by color coding. In: Proceedings 16th International Conference on Intelligent Systems for Molecular Biology (ISMB \u201908), pp. 241\u2013249 (2008)","DOI":"10.1093\/bioinformatics\/btn163"},{"issue":"3","key":"1301_CR66","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1798596.1798607","volume":"6","author":"N Alon","year":"2010","unstructured":"Alon, N., Gutner, S.: Balanced families of perfect hash functions and their applications. ACM Trans. Algorithms 6(3), 1\u201312 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"1301_CR67","series-title":"Algorithms and Combinatorics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity\u2014Graphs, Structures, and Algorithms","author":"J Nesetril","year":"2012","unstructured":"Nesetril, J., Mendez, P.O.: Sparsity\u2014Graphs, Structures, and Algorithms. Algorithms and Combinatorics, vol. 28. Springer, Berlin (2012)"},{"key":"1301_CR68","doi-asserted-by":"crossref","unstructured":"Grohe, M., Schweikardt, N.: First-order query evaluation with cardinality conditions. In: Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (SIGMOD\/PODS \u201918), pp. 253\u2013266 (2018)","DOI":"10.1145\/3196959.3196970"},{"issue":"1","key":"1301_CR69","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Appl. Math. 108(1), 23\u201352 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1301_CR70","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/0890-5401(92)90041-D","volume":"98","author":"D Eppstein","year":"1992","unstructured":"Eppstein, D.: Parallel recognition of series-parallel graphs. Inf. Comput. 98(1), 41\u201355 (1992)","journal-title":"Inf. Comput."},{"key":"1301_CR71","unstructured":"Enright, J.A., Meeks, K., Molter, H.: Counting temporal paths. In: Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS \u201923). LIPIcs, vol. 254, pp. 30\u201313019 (2023)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01301-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-025-01301-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-025-01301-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T07:01:35Z","timestamp":1746687695000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-025-01301-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,25]]},"references-count":71,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["1301"],"URL":"https:\/\/doi.org\/10.1007\/s00453-025-01301-3","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-3181661\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,25]]},"assertion":[{"value":"18 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}