Book contents
- Frontmatter
- Contents
- Preface
- Phase Transitions in Random Planar Graphs
- Extremal Poset Theory
- Techniques for Taming Temporal Graphs
- Asymptotic Enumeration via Graph Containers and Entropy
- Graph Bootstrap Percolation – A Discovery of Slowness
- Rigidity of Graphs and Frameworks: A Matroid Theoretic Approach
- Monadic Second-Order Logic for Hypergraphs and Matroids
- Domino Tilings Beyond 2D
- References
Techniques for Taming Temporal Graphs
Published online by Cambridge University Press: 06 June 2026
By
Book contents
- Frontmatter
- Contents
- Preface
- Phase Transitions in Random Planar Graphs
- Extremal Poset Theory
- Techniques for Taming Temporal Graphs
- Asymptotic Enumeration via Graph Containers and Entropy
- Graph Bootstrap Percolation – A Discovery of Slowness
- Rigidity of Graphs and Frameworks: A Matroid Theoretic Approach
- Monadic Second-Order Logic for Hypergraphs and Matroids
- Domino Tilings Beyond 2D
- References
Summary
Temporal graphs, in which the vertex-set remains fixed but the edge-set is subject to discrete changes over time, provide a useful formalism for modelling many real-world datasets, from social networks to transport networks. However, many fundamental concepts and results in graph theory do not transfer in a natural way to the temporal setting, and, in particular, even basic algorithmic questions become much more computationally challenging. In this article, we provide an overview of recent attempts to identify tractable cases for computational problems on temporal graphs, via the framework of parameterised complexity, and reflect on the major challenges in addressing this goal.
Information
- Type
- Chapter
- Information
- Surveys in Combinatorics 2026 , pp. 75 - 110Publisher: Cambridge University PressPrint publication year: 2026
References
Akrida, Eleni C., Mertzios, George B., Spirakis, Paul G., and Raptopoulos, Christoforos L., The temporal explorer who returns to the base, Journal of Computer and System Sciences 120 (2021), 179–193.CrossRefGoogle Scholar
Akrida, Eleni C., Mertzios, George B., Spirakis, Paul G., and Zamaraev, Viktor, Temporal vertex cover with a sliding time window, Journal of Computer and System Sciences 107 (2020), 108–123.10.1016/j.jcss.2019.08.002CrossRefGoogle Scholar
Axiotis, Kyriakos and Fotakis, Dimitris, On the size and the approximability of minimum temporally connected subgraphs, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy (Chatzigiannakis, Ioannis, Mitzenmacher, Michael, Rabani, Yuval, and Sangiorgi, Davide, eds.), LIPIcs, vol. 55, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016, pp. 149:1–149:14.Google Scholar
Balabán, Jakub, Ganian, Robert, and Rocton, Mathis, Computing Twin-Width Parameterized by the Feedback Edge Number, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024) (Dagstuhl, Germany) (Beyersdorff, Olaf, Kanté, Mamadou Moustapha, Kupferman, Orna, and Lokshtanov, Daniel, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 289, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, pp. 7:1–7:19.Google Scholar
Berman, Kenneth A., Vulnerability of scheduled networks and a generalization of Menger’s Theorem, Networks 28 (1996), no. 3, 125–134.Google Scholar
Bessy, Stéphane, Bonato, Anthony, Janssen, Jeannette C. M., Rautenbach, Dieter, and Roshanbin, Elham, Burning a graph is hard, Discrete Applied Mathematics 232 (2017), 73–87.CrossRefGoogle Scholar
Bonato, Anthony, Janssen, Jeannette C. M., and Roshanbin, Elham, Burning a graph as a model of social contagion, Algorithms and Models for the Web Graph – 11th International Workshop, WAW 2014, Beijing, China, December 17-18, 2014, Proceedings (Bonato, Anthony, Graham, Fan Chung, and Pralat, Pawel, eds.), Lecture Notes in Computer Science, vol. 8882, Springer, 2014, pp. 13–22.Google Scholar
Brettell, Nick, Munaro, Andrea, Paulusma, Daniël, and Yang, Shizhou, Comparing width parameters on graph classes, European Journal of Combinatorics 127 (2025), 104163.CrossRefGoogle Scholar
Bumpus, Benjamin Merlin and Meeks, Kitty, Edge exploration of temporal graphs, Combinatorial Algorithms – 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings (Flocchini, Paola and Moura, Lucia, eds.), Lecture Notes in Computer Science, vol. 12757, Springer, 2021, pp. 107–121.Google Scholar
Bumpus, Benjamin Merlin and Meeks, Kitty, Edge exploration of temporal graphs, Algorithmica 85 (2023), no. 3, 688–716.Google Scholar
Casteigts, Arnaud, Corsini, Timothée, and Sarkar, Writika, Simple, strict, proper, happy: A study of reachability in temporal graphs, Theoretical Computer Science 991 (2024), 114434.10.1016/j.tcs.2024.114434CrossRefGoogle Scholar
Casteigts, Arnaud, Flocchini, Paola, Quattrociocchi, Walter, and Santoro, Nicola, Time-varying graphs and dynamic networks, International Journal of Parallel, Emergent and Distributed Systems 27 (2012), no. 5, 387–408.10.1080/17445760.2012.668546CrossRefGoogle Scholar
Casteigts, Arnaud, Himmel, Anne-Sophie, Molter, Hendrik, and Zschoche, Philipp, Finding temporal paths under waiting time constraints, Algorithmica 83 (2021), no. 9, 2754–2802.Google Scholar
Casteigts, Arnaud, Morawietz, Nils, and Wolf, Petra, Distance to transitivity: New parameters for taming reachability in temporal graphs, 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia (Rastislav Královic and Antonı́n Kucera, eds.), LIPIcs, vol. 306, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, pp. 36:1–36:17.Google Scholar
Casteigts, Arnaud, Peters, Joseph G., and Schoeters, Jason, Temporal cliques admit sparse spanners, Journal of Computer and System Sciences 121 (2021), 1–17.10.1016/j.jcss.2021.04.004CrossRefGoogle Scholar
Chakraborty, Dipayan, Foucaud, Florent, Majumdar, Diptapriyo, and Tale, Prafullkumar, Structural parameterization of locating-dominating set and test cover, Algorithms and Complexity (Cham) (Finocchi, Irene and Georgiadis, Loukas, eds.), Springer Nature Switzerland, 2025, pp. 187–204.Google Scholar
Christodoulou, Filippos, Crescenzi, Pierluigi, Marino, Andrea, Silva, Ana, and Thilikos, Dimitrios M., Making the Interval Membership Width of Temporal Graphs Connected and Bidirectional, Combinatorial Algorithms (Cham) (Rescigno, Adele Anna and Vaccaro, Ugo, eds.), Springer Nature Switzerland, 2024, pp. 247–258.Google Scholar
Cioni, Lapo, Dondi, Riccardo, Marino, Andrea, Schoeters, Jason, and Silva, Ana, Matching and edge cover in temporal graphs, 4th Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2025, June 9-11, 2025, Liverpool, UK (Meeks, Kitty and Scheideler, Christian, eds.), LIPIcs, vol. 330, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, pp. 8:1–8:16.Google Scholar
Corsini, Timothée, Enright, Jessica A., Larios-Jones, Laura, and Meeks, Kitty, Temporal orienteering with changing fuel costs, CoRR abs/2507.00728 (2025).Google Scholar
Courcelle, B., Makowsky, J. A., and Rotics, U., Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width, Theory of Computing Systems 33 (2000), no. 2, 125–150.Google Scholar
Courcelle, Bruno, The monadic second-order logic of graphs I: recognizable sets of finite graphs, Information and Computation 85 (1990), no. 1, 12–75.Google Scholar
Courcelle, Bruno, The monadic second-order logic of graphs III: tree-decompositions, minor and complexity issues, RAIRO Theoretical Informatics and Applications 26 (1992), 257–286.CrossRefGoogle Scholar
Courcelle, Bruno and Engelfriet, Joost, Graph structure and monadic second-order logic – A language-theoretic approach, Encyclopedia of Mathematics and its Applications, vol. 138, Cambridge University Press, 2012.Google Scholar
Courcelle, Bruno and Olariu, Stephan, Upper bounds to the clique width of graphs, Discrete Applied Mathematics 101 (2000), no. 1, 77–114.Google Scholar
Cygan, Marek, Fomin, Fedor V., Kowalik, Łukasz, Lokshtanov, Daniel, Marx, Dániel, Pilipczuk, Marcin, Pilipczuk, Michał, and Saurabh, Saket, Parameterized Algorithms, Springer International Publishing, Cham, 2015.CrossRefGoogle Scholar
Davot, Tom, Enright, Jessica A., Madathil, Jayakrishnan, and Meeks, Kitty, Temporal triadic closure: Finding dense substructures in social networks that evolve over time, AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 – March 4, 2025, Philadelphia, PA, USA (Walsh, Toby, Shah, Julie, and Kolter, Zico, eds.), AAAI Press, 2025, pp. 26939–26946.Google Scholar
Deligkas, Argyrios, Döring, Michelle, Eiben, Eduard, Goldsmith, Tiger-Lily, Skretas, George, and Tennigkeit, Georg, How many lines to paint the city: Exact edge-cover in temporal graphs, AAAI-25, Sponsored by the Association for the Advancement of Artificial Intelligence, February 25 – March 4, 2025, Philadelphia, PA, USA (Walsh, Toby, Shah, Julie, and Kolter, Zico, eds.), AAAI Press, 2025, pp. 26498–26506.Google Scholar
Downey, Rodney G. and Fellows, Michael R., Parameterized complexity, Monographs in Computer Science, Springer, 1999.Google Scholar
Downey, Rodney G. and Fellows, Michael R., Fundamentals of parameterized complexity, Texts in Computer Science, Springer, 2013.Google Scholar
Enciso, Rosa, Fellows, Michael R., Guo, Jiong, Kanj, Iyad, Rosamond, Frances, and Suchý, Ondřej, What makes equitable connected partition easy, Parameterized and Exact Computation (Berlin, Heidelberg) (Chen, Jianer and Fomin, Fedor V., eds.), Springer Berlin Heidelberg, 2009, pp. 122–133.Google Scholar
Enright, Jessica A., Hand, Samuel D., Larios-Jones, Laura, and Meeks, Kitty, Structural parameters for dense temporal graphs, 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024, August 26-30, 2024, Bratislava, Slovakia (Rastislav Královic and Antonı́n Kucera, eds.), LIPIcs, vol. 306, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024, pp. 52:1–52:15.Google Scholar
Enright, Jessica A., Hand, Samuel D., Larios-Jones, Laura, and Meeks, Kitty, Families of tractable problems with respect to vertex-interval-membership width and its generalisations, CoRR abs/2505.15699 (2025).Google Scholar
Enright, Jessica A., Larios-Jones, Laura, Meeks, Kitty, and Pettersson, William, Reachability in temporal graphs under perturbation, SOFSEM 2025: Theory and Practice of Computer Science – 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025, Bratislava, Slovak Republic, January 20-23, 2025, Proceedings, Part I (Královic, Rastislav and Kurková, Vera, eds.), Lecture Notes in Computer Science, vol. 15538, Springer, 2025, pp. 255–269.Google Scholar
Enright, Jessica A., Meeks, Kitty, Mertzios, George B., and Zamaraev, Viktor, Deleting edges to restrict the size of an epidemic in temporal networks, Journal of Computer and System Sciences 119 (2021), 60–77.CrossRefGoogle Scholar
Enright, Jessica A., Meeks, Kitty, and Molter, Hendrik, Counting temporal paths, Algorithmica 87 (2025), no. 5, 736–782.Google Scholar
Fiala, Jiří, Golovach, Petr A., and Kratochvíl, Jan, Parameterized complexity of coloring problems: Treewidth versus vertex cover, Theoretical Computer Science 412 (2011), no. 23, 2513–2523, Theory and Applications of Models of Computation (TAMC 2009).Google Scholar
Flum, Jörg and Grohe, Martin, Parameterized complexity theory, Texts in Theoretical Computer Science, EATCS Series, Springer, 2006.Google Scholar
Fluschnik, Till, Molter, Hendrik, Niedermeier, Rolf, Renken, Malte, and Zschoche, Philipp, As time goes by: Reflections on treewidth for temporal graphs, Treewidth, Kernels, and Algorithms – Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday (Fomin, Fedor V., Kratsch, Stefan, and Jan van Leeuwen, Erik, eds.), Lecture Notes in Computer Science, vol. 12160, Springer, 2020, pp. 49–77.Google Scholar
Fluschnik, Till, Molter, Hendrik, Niedermeier, Rolf, Renken, Malte, and Zschoche, Philipp, Temporal graph classes: A view through temporal separators, Theoretical Computer Science 806 (2020), 197–218.10.1016/j.tcs.2019.03.031CrossRefGoogle Scholar
Fox, Jacob, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein, Finding cliques in social networks: A new distribution-free model, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic (Chatzigiannakis, Ioannis, Kaklamanis, Christos, Marx, Dániel, and Sannella, Donald, eds.), LIPIcs, vol. 107, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018, pp. 55:1–55:15.Google Scholar
Fox, Jacob, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein, Finding cliques in social networks: A new distribution-free model, SIAM Journal on Computing 49 (2020), no. 2, 448–464.Google Scholar
Gajarský, Jakub, Lampis, Michael, and Ordyniak, Sebastian, Parameterized Algorithms for Modular-Width, Parameterized and Exact Computation (Cham) (Gutin, Gregory and Szeider, Stefan, eds.), Lecture Notes in Computer Science, Springer International Publishing, 2013, pp. 163–176.Google Scholar
Ganian, Robert, Using Neighborhood Diversity to Solve Hard Problems, January 2012, arXiv:1201.3091.Google Scholar
Ganian, Robert, Hlinený, Petr, Kneis, Joachim, Meister, Daniel, Obdrzálek, Jan, Rossmanith, Peter, and Sikdar, Somnath, Are there any good digraph width measures?, Journal of Combinatorial Theory, Series B 116 (2016), 250–286.10.1016/j.jctb.2015.09.001CrossRefGoogle Scholar
Haag, Roman, Molter, Hendrik, Niedermeier, Rolf, and Renken, Malte, Feedback edge sets in temporal graphs, Discrete Applied Mathematics 307 (2022), 65–78.CrossRefGoogle Scholar
Hand, Samuel D., Enright, Jessica, and Meeks, Kitty, Making Life More Confusing for Firefighters, 11th International Conference on Fun with Algorithms (FUN 2022) (Dagstuhl, Germany) (Fraigniaud, Pierre and Uno, Yushi, eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 226, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 15:1–15:15.Google Scholar
Hermelin, Danny, Itzhaki, Yuval, Molter, Hendrik, and Niedermeier, Rolf, Temporal interval cliques and independent sets, Theoretical Computer Science 961 (2023), 113885.10.1016/j.tcs.2023.113885CrossRefGoogle Scholar
Herrmann, Anton, Komusiewicz, Christian, Morawietz, Nils, and Sommer, Frank, Temporal dominating set and temporal vertex cover under the lense of degree restrictions, 4th Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2025, June 9-11, 2025, Liverpool, UK (Meeks, Kitty and Scheideler, Christian, eds.), LIPIcs, vol. 330, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, pp. 16:1–16:18.Google Scholar
Kempe, David, Kleinberg, Jon M., and Kumar, Amit, Connectivity and inference problems for temporal networks, Journal of Computer and System Sciences 64 (2002), no. 4, 820–842.10.1006/jcss.2002.1829CrossRefGoogle Scholar
Koana, Tomohiro, Komusiewicz, Christian, and Sommer, Frank, Exploiting c-closure in kernelization algorithms for graph problems, SIAM Journal on Discrete Mathematics 36 (2022), no. 4, 2798–2821.Google Scholar
Koana, Tomohiro, Komusiewicz, Christian, and Sommer, Frank, Computing dense and sparse subgraphs of weakly closed graphs, Algorithmica 85 (2023), no. 7, 2156–2187.Google Scholar
Koana, Tomohiro, Komusiewicz, Christian, and Sommer, Frank, Essentially tight kernels for (weakly) closed graphs, Algorithmica 85 (2023), no. 6, 1706–1735.Google Scholar
Kobayashi, Yasuaki and Otachi, Yota, Parameterized complexity of graph burning, Algorithmica 84 (2022), no. 8, 2379–2393.Google Scholar
Kratsch, Stefan and Schweitzer, Pascal, Isomorphism for graphs of bounded feedback vertex set number, Algorithm Theory – SWAT 2010 (Berlin, Heidelberg) (Kaplan, Haim, ed.), Springer Berlin Heidelberg, 2010, pp. 81–92.Google Scholar
Kutner, David C. and Larios-Jones, Laura, Temporal reachability dominating sets: Contagion in temporal graphs, Algorithmics of Wireless Networks – 19th International Symposium, ALGOWIN 2023, Amsterdam, The Netherlands, September 7-8, 2023, Revised Selected Papers (Georgiou, Konstantinos and Kranakis, Evangelos, eds.), Lecture Notes in Computer Science, vol. 14061, Springer, 2023, pp. 101–116.Google Scholar
Kutner, David C. and Sommer, Anouk, Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs, 4th Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2025, June 9-11, 2025, Liverpool, UK (Meeks, Kitty and Scheideler, Christian, eds.), LIPIcs, vol. 330, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025, pp. 7:1–7:18.Google Scholar
Lampis, Michael, Algorithmic Meta-theorems for Restrictions of Treewidth, Algorithmica 64 (2012), no. 1, 19–37.Google Scholar
Lokshtanov, Daniel, Parameterized integer quadratic programming: Variables and coefficients, CoRR abs/1511.00310 (2015).Google Scholar
Marino, Andrea and Silva, Ana, Coloring temporal graphs, Journal of Computer and System Sciences 123 (2022), 171–185.CrossRefGoogle Scholar
Marino, Andrea and Silva, Ana, Eulerian walks in temporal graphs, Algorithmica 85 (2023), no. 3, 805–830.Google Scholar
Meeks, Kitty and Skerman, Fiona, The parameterised complexity of computing the maximum modularity of a graph, Algorithmica 82 (2020), no. 8, 2174–2199.Google Scholar
Mertzios, George B., Michail, Othon, and Spirakis, Paul G., Temporal network optimization subject to connectivity constraints, Algorithmica 81 (2019), no. 4, 1416–1449.Google Scholar
Mertzios, George B., Molter, Hendrik, Niedermeier, Rolf, Zamaraev, Viktor, and Zschoche, Philipp, Computing maximum matchings in temporal graphs, Journal of Computer and System Sciences 137 (2023), 1–19.10.1016/j.jcss.2023.04.005CrossRefGoogle Scholar
Accessibility standard: WCAG 2.2 A
Why this information is here
This section outlines the accessibility features of this content - including support for screen readers, full keyboard navigation and high-contrast display options. This may not be relevant for you.Accessibility Information
The PDF of this chapter
complies with version 2.2 of the
Web Content Accessibility Guidelines
(WCAG), offering more comprehensive accessibility measures for a broad range
of users and meets the basic
(A)
level of WCAG compliance, addressing essential accessibility barriers.
Content Navigation
Table of contents navigation
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Allows you to navigate directly to chapters, sections, or non‐text items through a linked table of contents, reducing the need for extensive scrolling.
Index navigation
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.
Provides an interactive index, letting you go straight to where a term or subject appears in the text without manual searching.
Reading Order & Textual Equivalents
Single logical reading order
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
You will encounter all content (including footnotes, captions, etc.) in a clear, sequential flow, making it easier to follow with assistive tools like screen readers.
Short alternative textual descriptions
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.
You get concise descriptions (for images, charts, or media clips), ensuring you do not miss crucial information when visual or audio elements are not accessible.