Abstract
A temporal graph \(\mathcal{G}\) is a graph that changes with time. More specifically, it is a pair \((G, \lambda )\) where G is a graph and \(\lambda \) is a function on the edges of G that describes when each edge \(e\in E(G)\) is active. Given vertices \(s,t\in V(G)\), a temporal \(s,t\)-path is a path in G that traverses edges in non-decreasing time; and if s, t are non-adjacent, then a vertex temporal \(s,t\)-cut is a subset \(S\subseteq V(G)\) whose removal destroys all temporal \(s,t\)-paths.
It is known that Menger’s Theorem does not hold on this context, i.e., that the maximum number of internally vertex disjoint temporal \(s,t\)-paths is not necessarily equal to the minimum size of a vertex temporal \(s,t\)-cut. In a seminal paper, Kempe, Kleinberg and Kumar (STOC’2000) defined a graph G to be Mengerian if equality holds on \((G,\lambda )\) for every function \(\lambda \). They then proved that, if each edge is allowed to be active only once in \((G,\lambda )\), then G is Mengerian if and only if G has no gem as topological minor. In this paper, we generalize their result by allowing edges to be active more than once, giving a characterization also in terms of forbidden structures. We also provide a polynomial time recognition algorithm.
Supported by CNPq grants 303803/2020-7 and 437841/2018-9, FUNCAP/CNPq grant PNE-0112-00061.01.00/16, and CAPES (PhD student funding).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We adopt the definition of [16], where a graph can have multiple edges incident to the same pair of vertices. This is sometimes called multigraph.
References
Berman, K.A.: Vulnerability of scheduled networks and a generalization of Menger’s theorem. Netw.: Int. J. 28(3), 125–134 (1996)
Bhadra, S., Ferreira, A.: Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In: Pierre, S., Barbeau, M., Kranakis, E. (eds.) ADHOC-NOW 2003. LNCS, vol. 2865, pp. 259–270. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-39611-6_23
Campos, V., Lopes, R., Marino, A., Silva, A.: Edge-disjoint branchings in temporal graphs. In: Gąsieniec, L., Klasing, R., Radzik, T. (eds.) IWOCA 2020. LNCS, vol. 12126, pp. 112–125. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-48966-3_9
Casteigts, A., Flocchini, P., Quattrociocchi, W., Santoro, N.: Time-varying graphs and dynamic networks. Int. J. Parallel Emergent Distrib. Syst. 27(5), 387–408 (2012)
Casteigts, A., Himmel, A.-S., Molter, H., Zschoche, P.: Finding temporal paths under waiting time constraints. In: 31st International Symposium on Algorithms and Computation, ISAAC, volume 181 of LIPIcs, pp. 30:1–30:18 (2020)
Jessica Enright and Rowland Raymond Kao: Epidemics on dynamic networks. Epidemics 24, 88–97 (2018)
Fluschnik, T., Molter, H., Niedermeier, R., Renken, M., Zschoche, P.: Temporal graph classes: a view through temporal separators. Theoret. Comput. Sci. 806, 197–218 (2020)
Grohe, M., Kawarabayashi, K., Marx, D., Wollan, P.: Finding topological subgraphs is fixed-parameter tractable. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pp. 479–488 (2011)
Holme, P.: Modern temporal network theory: a colloquium. Eur. Phys. J. B 88(9), 1–30 (2015). https://doi.org/10.1140/epjb/e2015-60657-4
Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64, 820–842 (2002)
Latapy, M., Viard, T., Magnien, C.: Stream graphs and link streams for the modeling of interactions over time. Soc. Netw. Anal. Min. 8(1), 1–29 (2018). https://doi.org/10.1007/s13278-018-0537-7
Menger, K.: Zur allgemeinen kurventheorie. Fundam. Math. 10(1), 96–115 (1927)
Mertzios, G.B., Michail, O., Spirakis, P.G.: Temporal network optimization subject to connectivity constraints. Algorithmica 81(4), 1416–1449 (2019). https://doi.org/10.1007/s00453-018-0478-6
Michail, O.: An introduction to temporal graphs: an algorithmic perspective. Internet Math. 12(4), 239–280 (2016)
Nicosia, V., Tang, J., Mascolo, C., Musolesi, M., Russo, G., Latora, V.: Graph metrics for temporal networks. In: Holme, P., Saramäki, J. (eds.) Temporal Networks. Understanding Complex Systems, pp. 15–40. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36461-7_2
Douglas Brent West: Introduction to Graph Theory, vol. 2. Prentice Hall, Upper Saddle River (1996)
Bui Xuan, B., Ferreira, A., Jarry, A.: Computing shortest, fastest, and foremost journeys in dynamic networks. Int. J. Found. Comput. Sci. 14(02), 267–285 (2003)
Zschoche, P., Fluschnik, T., Molter, H., Niedermeier, R.: The complexity of finding small separators in temporal graphs. J. Comput. Syst. Sci. 107, 72–92 (2020)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Ibiapina, A., Silva, A. (2021). Mengerian Temporal Graphs Revisited. In: Bampis, E., Pagourtzis, A. (eds) Fundamentals of Computation Theory. FCT 2021. Lecture Notes in Computer Science(), vol 12867. Springer, Cham. https://doi.org/10.1007/978-3-030-86593-1_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-86593-1_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86592-4
Online ISBN: 978-3-030-86593-1
eBook Packages: Computer ScienceComputer Science (R0)