This page contains the computational complexity of open and closed temporal connected components, their unilateral variants, single source variants, and $\delta$-time window variants.
In the path-based approach, temporal connected components are defined in terms of temporal paths between vertices. The central idea is to generalize static connectivity by requiring pairwise temporal reachability between pairs of vertices. Since temporal reachability is not transitive there are two possible definitions which differ in whether paths are allowed to leave the component or must remain inside. Both generalize the idea of strongly connected components in static directed graphs.
<aside> <img src="/icons/new-folder_yellow.svg" alt="/icons/new-folder_yellow.svg" width="40px" />
Definition: open Temporal Connected Component (open tcc) Maximal set of vertices $X\subseteq V$ s.t. for any pair ****$u,v\in X$ there exist temporal paths $u\curvearrowright v$ and $u\curvearrowleft v$.
</aside>
<aside> <img src="/icons/new-folder_yellow.svg" alt="/icons/new-folder_yellow.svg" width="40px" />
Definition: closed Temporal Connected Component (closed tcc) Maximal set of vertices $X\subseteq V$ s.t. for any pair $u,v\in X$ there exist temporal paths $u\curvearrowright v$ and $u\curvearrowleft v$ using only edges in $X \times X$.
</aside>
Note: Unlike static connected components, open tccs and closed tccs do not need partition the vertex set; they may overlap and their number can be exponential in the graph size.