Abstract
A temporal (directed) graph is a graph whose edges are available only at specific times during its lifetime, \(\tau \). Paths are sequences of adjacent edges whose appearing times are either strictly increasing or non-strictly increasing (i.e., non-decreasing) depending on the scenario. Then, the classical concept of connected components and also of unilateral connected components in static graphs naturally extends to temporal graphs. In this paper, we answer the following fundamental questions in temporal graphs. (i) What is the complexity of deciding the existence of a component of size k, parameterized by \(\tau \), by k, and by \(k+\tau \)? We show that this question has a different answer depending on the considered definition of component and whether the temporal graph is directed or undirected. (ii) What is the minimum running time required to check whether a subset of vertices are pairwise reachable? A quadratic algorithm is known but, contrary to the static case, we show that a better running time is unlikely unless SETH fails. (iii) Is it possible to verify whether a subset of vertices is a component in polynomial time? We show that depending on the definition of component this test is \(\textsf{NP}\)-complete.
(Partially) supported by: FUNCAP MLC-0191-00056.01.00/22 and PNE-0112-00061.01.00/16, CNPq 303803/2020-7, Italian PNRR CN4 Centro Nazionale per la Mobilità Sostenibile, and the group Casino/ENS Chair on Algorithmics and Machine Learning. Thanks to Giulia Punzi and Mamadou Kanté for interesting discussions. A full version of this paper is available at: https://arxiv.org/abs/2302.12068.
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.
In the directed case, it suffices to replace each edge of the input graph with two opposite directed edges between the same endpoints.
- 2.
\(M=\sum _{e\in E(\mathcal{G})}|\lambda (e)|\).
References
Arjomandi, E.: On finding all unilaterally connected components of a digraph. Inf. Process. Lett. 5(1), 8–10 (1976)
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
Borassi, M., Crescenzi, P., Habib, M.: Into the square: on the complexity of some quadratic-time solvable problems. In: ICTCS. Electronic Notes in Theoretical Computer Science, vol. 322, pp. 51–67. Elsevier (2015)
Borodin, A.B., Munro, I.: Notes on efficient and optimal algorithms. Technical report, U. of Toronto and U. of Waterloo, Canada (1972)
Casteigts, A.: Finding structure in dynamic networks. arXiv preprint arXiv:1807.07801 (2018)
Casteigts, A., Corsini, T., Sarkar, W.: Simple, strict, proper, happy: a study of reachability in temporal graphs. arXiv preprint arXiv:2208.01720 (2022)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness ii: on completeness for w [1]. Theor. Comput. Sci. 141(1–2), 109–131 (1995)
Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372–378 (1973)
Impagliazzo, R., Paturi, R.: On the complexity of k-sat. J. Comput. Syst. Sci. 62(2), 367–375 (2001)
Kempe, D., Kleinberg, J., Kumar, A.: Connectivity and inference problems for temporal networks. In: Yao, F.F., Luks, E.M., eds, Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 21–23 May 2000. Portland, pp. 504–513. ACM (2000)
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
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Generating all maximal independent sets: Np-hardness and polynomial-time algorithms. SIAM J. Comput. 9(3), 558–565 (1980)
Levorato, V., Petermann, C.: Detection of communities in directed networks based on strongly p-connected components. In: 2011 International Conference on Computational Aspects of Social Networks (CASoN), pp. 211–216. IEEE (2011)
Nicosia, V., Tang, J., Musolesi, M., Russo, G., Mascolo, C., Latora, V.: Components in time-varying graphs. Chaos: Interdisc. J. Nonlinear Sci. 22(2), 023101 (2012)
Foad Mahdavi Pajouh and Balabhaskar Balasundaram: On inclusionwise maximal and maximum cardinality k-clubs in graphs. Discret. Optim. 9(2), 84–97 (2012)
Peeters, R.: The maximum edge biclique problem is np-complete. Discret. Appl. Math. 131(3), 651–654 (2003)
Huanhuan, W., Cheng, J., Huang, S., Ke, Y., Yi, L., Yanyan, X.: Path problems in temporal graphs. Proc. VLDB Endowment 7(9), 721–732 (2014)
Yannakakis, M.: Computing the minimum fill-in is np-complete. SIAM J. Algebraic Discrete Methods 2(1), 77–79 (1981)
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
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Costa, I.L., Lopes, R., Marino, A., Silva, A. (2023). On Computing Large Temporal (Unilateral) Connected Components. In: Hsieh, SY., Hung, LJ., Lee, CW. (eds) Combinatorial Algorithms. IWOCA 2023. Lecture Notes in Computer Science, vol 13889. Springer, Cham. https://doi.org/10.1007/978-3-031-34347-6_24
Download citation
DOI: https://doi.org/10.1007/978-3-031-34347-6_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-34346-9
Online ISBN: 978-3-031-34347-6
eBook Packages: Computer ScienceComputer Science (R0)