Abstract
Temporal graphs are graphs that evolve over time. Many problems which are polynomial-time solvable in standard graphs become NP-hard when appropriately defined in the realm of temporal graphs. This suggested the definition of several parameters for temporal graphs and to prove the fixed-parameter tractability of several problems with respect to these parameters. In this paper, we introduce a hierarchy of parameters based on the previously defined interval membership width and on the temporal evolution of the connected components of the underlying static graph. We then show that the Eulerian trail problem and the temporal 2-coloring problem are both fixed-parameter tractable (in short, FPT) with respect to any of the parameters in the hierarchy. We also introduce a vertex-variant of the parameters and we show that the firefighter problem (which was known to be FPT with respect to the vertex-variant of the interval membership width) is also FPT with respect to one of the parameters in the second level of the hierarchy.
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.
For every positive integer k, [k] denotes the set \(\{1,2,\ldots ,k\}\).
- 2.
Similarly, one can consider non-decreasing sequences, i.e. with \(t_{1}\le \ldots \le t_{k}\). In this paper, however, we focus on the strictly increasing case.
References
Bhadra, S., Ferreira, A.: Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs. J. Internet Serv. Appl. 3(3), 269–275 (2012)
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–285 (2003)
Bumpus, B.M., Meeks, K.: Edge exploration of temporal graphs. Algorithmica 85(3), 688–716 (2023)
Calamai, M., Crescenzi, P., Marino, A.: On computing the diameter of (weighted) link streams. ACM J. Exp. Algorithmics 27, 1–28 (2022)
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. Algorithmica 83, 2754–2802 (2021)
Cygan, M., et al.: Parameterized Algorithms. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21275-3
Enright, J.A., Meeks, K., Molter, H.: Counting temporal paths. In: 40th STACS. LIPIcs, vol. 254, pp. 30:1–30:19 (2023)
Finbow, S., MacGillivray, G.: The firefighter problem: a survey of results, directions and questions. Australas. J. Comb. 43, 57–78 (2009)
Flocchini, P., Mans, B., Santoro, N.: Exploration of periodically varying graphs. In: International Symposium on Algorithms and Computation, pp. 534–543 (2009)
Fluschnik, T., Molter, H., Niedermeier, R., Renken, M., Zschoche, P.: As time goes by: reflections on treewidth for temporal graphs. In: Treewidth, Kernels, and Algorithms, pp. 49–77 (2020)
Hand, S.D., Enright, J.A., Meeks, K.: Making life more confusing for firefighters. In: International Conference on Fun with Algorithms, pp. 15:1–15:15 (2022)
Holme, P., Saramäki, J.: Temporal networks. Phys. Rep. 519(3), 97–125 (2012)
Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. J. Comput. Syst. Sci. 64(4), 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), 61 (2018)
Marino, A., Silva, A.: Coloring temporal graphs. J. Comput. Syst. Sci. 123, 171–185 (2022)
Marino, A., Silva, A.: Eulerian walks in temporal graphs. Algorithmica 85(3), 805–830 (2022)
Michail, O.: An introduction to temporal graphs: an algorithmic perspective. Internet Math. 12, 308–343 (2015)
Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. ACM 22(2), 215–225 (1975)
West, D.B., et al.: Introduction to graph theory, vol. 2. Prentice Hall, Upper Saddle River (2001)
Acknowledgement
P.C. was supported by PNRR MIUR project GAMING “Graph Algorithms and MinINg for Green agents” (PE0000013, CUP D13C24000430001), A.M. by PNRR CN4 Centro Nazionale per la Mobilità Sostenibile, NextGeneration EU-CUP, B13C22001000001, by MUR of Italy, under PRIN Project n. 2022ME9Z78-NextGRAAL: Next-generation algorithms for constrained GRAph visuALization, and by PRIN PNRR Project n. P2022NZPJA-DLT-FRUIT: A user centered framework for facilitating DLTs FRUITion, A.S. by CNPq 303803/2020-7, 404479/2023-5, FUNCAP MLC-0191-00056.01.00/22, COFECUB 88887.712023/2022-00, and D.M.T. by the French-German Collaboration ANR/DFG Project UTMA (ANR-20-CE92-0027) and by the MEAE and the MESR, via the Franco-Norwegian project PHC Aurora projet n. 51260WL (2024).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Christodoulou, F., Crescenzi, P., Marino, A., Silva, A., Thilikos, D.M. (2024). Making the Interval Membership Width of Temporal Graphs Connected and Bidirectional. In: Rescigno, A.A., Vaccaro, U. (eds) Combinatorial Algorithms. IWOCA 2024. Lecture Notes in Computer Science, vol 14764. Springer, Cham. https://doi.org/10.1007/978-3-031-63021-7_19
Download citation
DOI: https://doi.org/10.1007/978-3-031-63021-7_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-63020-0
Online ISBN: 978-3-031-63021-7
eBook Packages: Computer ScienceComputer Science (R0)