Computational complexity is the main lens through which we analyse algorithmic aspects of temporal graphs. Many problems that are straightforward to compute for static graphs become surprisingly difficult once they are generalized to temporal graphs. That is due to (1) there not being one distinct, obvious generalization, leading to different notions of different complexity, while (2) many graph problems are based on reachability which brings its own difficulties.

To analyze these computational questions, there are three basic toolboxes:

• Classical complexity theory%20and%20memory%20storage%20requirements.) provides the baseline: NP-hardness proofs show where efficient algorithms are unlikely, while algorithms with polynomial running time proof tractability.
• Parameterized complexity refines this view by asking which structural parameters—such as treewidth, lifetime, or the number of requests—might allow fixed-parameter tractable (FPT) algorithms. This is crucial for temporal graphs, where problems are mostly NP-hard.
• Approximation algorithms offer a third perspective: when exact solutions are infeasible, can we compute “good enough” solutions efficiently?

Together, these approaches form the toolbox for temporal graph complexity. This page surveys how they have been applied so far, linking to the literature, emphasizing where tools have succeeded, and pointing out where they have failed. The goal is not only to map known results, but also to reveal methodological patterns: which reductions are common, which parameters are useful, and where new techniques might be needed. (work in progress)

2. Classical Complexity Tools

• Typical use cases in temporal graphs:
  • Reductions to show NP-hardness (e.g., temporal reachability, connectivity, separators, TCC).
  • Identifying problems that remain polynomial-time solvable (temporal shortest paths, temporal reachability queries).
• Examples from literature:
  • Temporal vertex cover (NP-hard even on paths).
  • Temporal separators (NP-hard with small pathwidth).
  • Some polynomial-time solvable cases (temporal matching, temporal path existence).
• Open questions:
  • Boundary cases (planar graphs, bounded degree, bounded lifetime).
  • When temporal constraints simplify vs complicate things.

3. Parameterized Complexity Tools

• Parameters studied in temporal graphs:

  • Number of terminals, treewidth/pathwidth/tree-cut width of the underlying graph, lifetime (number of snapshots), max degree, number of temporal paths, etc.

• Successful techniques:

  • Dynamic programming over tree decompositions.
  • Kernelization for lifetime/terminal number.

  Polynomial Kernels

  • Courcelle-style meta-theorems adapted to temporal graphs.

• Literature examples:

  • Temporally disjoint paths → W[1]-hard wrt. #vertices, but FPT wrt. #requests.
  • Temporal separators → FPT for lifetime, W[1]-hard wrt. treewidth.
  • Open TCC → FPT algorithms under monotonicity assumptions.

• Where tools fail:

  • ParaNP-hardness results (e.g., paraNP-hard wrt. treewidth/lifetime for some problems).
  • Obstacles in transferring static DP techniques directly.

4. Approximation and Inapproximability Tools

• Approximation algorithms in temporal graphs:
  • Temporal vertex cover: log-approximation.
  • Temporal Steiner network: bicriteria approximations.
• Hardness of approximation:
  • Inapproximability results via reductions (e.g., temporal path covering).