Many problems that are easy on static graphs become computationally intractable in the temporal setting—even for highly restricted input classes like trees or stars. Mirroring the goals of parameterized complexity in static graphs, researchers have introduced temporal graph parameters to better capture the combined structural and temporal complexity of time-dependent networks. These parameters enable refined complexity classifications and fixed-parameter tractable (FPT) algorithms for otherwise intractable problems.

There are four main strands of parameterization strategies:

1. Footprint-based parameters, where classical structural graph measures (like cliquewidth, modular-width, or neighborhood diversity) are extended to temporal graphs.
2. Time-based parameters, such as lifetime, temporality, temporal cost or labels per time step. These bound the graph’s evolution over time and can usually be read off the graph directly.
3. Temporal-structural parameters, such as vertex-interval-membership width (VIM) (which captures how long a vertex or edge remains active) or arc edit distance to transitivity. These are typically harder to compute but more expressive for capturing temporal behavior.
4. Generation-based parameters, like exact edge-cover (union of paths), which consider how the temporal graph is built.

The study of temporal parameters that intrinsically reflect both the dynamic and structural aspects of temporal graphs is still in its early stages. A significant body of prior work has shown that bounding classical parameters on the footprint alone is not sufficient—highlighting the need for parameters that are fundamentally temporal.

This page provides an overview of the known parameters, their definitions, and the problems for which they have proven algorithmically meaningful.

‘Temporal’ and ‘Static’ Parameters

Literature on Temporal Parameterized Complexity