<aside> 🌐
Outdated page — the Temporal Graph Wiki has moved. Read the wiki on temporalgraph.wiki.
</aside>
<aside> 🚨
Note (17.07.2025)
We observe that a VIM decomposition of a temporal graph $\mathcal{G}=(G,\lambda)$ yields a (not necessarily optimal) path decomposition of its footprint $G$ of width $\mathsf{vim}-1$. Equivalently, a TIM decomposition yields a tree decomposition of its footprint $G$ of width $\mathsf{tim}-1$. This implies:
However, neither $\mathsf{pw}\leq \mathsf{tim}$ nor $\mathsf{tim}\leq \mathsf{pw}$ hold:
| temporal graph $\mathcal{G}$ | pathwidth $\mathsf{pw}$ | TIM width $\mathsf{tim}$ |
|---|---|---|
| $\mathcal{G}\in\mathsf{TC}$, footprint $G$ is a path | $\mathsf{pw}=1$ | $\mathsf{tim}=\mathsf{vim}=n$ |
| footprint $G$ is a full binary tree, $\mathcal{G}$ has a proper + simple labeling increasing per level away from the root | $\mathsf{pw}=\Theta(\log n)$ | $\mathsf{tim}=3$ |
| </aside> |
The vertex-interval-membership width (vim width) was introduced by Bumpus and Meeks (2025). It captures how "spread out" the activity of vertices is over time.
Let $(G, \lambda)$ be a temporal graph with lifetime $\Lambda$.
<aside> <img src="/icons/exclamation-mark_orange.svg" alt="/icons/exclamation-mark_orange.svg" width="40px" />
Definition.
For each time step $t \in [\Lambda]$, define the vim bag at time $t$ as:
$F_t := \left\{ v \in V(G) \;\middle|\; \exists u, w \in V(G) \text{ such that } \min \lambda(vu) \le t \le \max \lambda(vw) \right\}$.
That is, $v \in F_t$ if there exists at least one incident edge of $v$ active at or before time $t$ and at least one incident edge active at or after time $t$ — i.e., $v$ is within its active interval at time $t$.
The vim width of $(G, \lambda)$ is defined as:
$\mathsf{vim} := \max_{t \in [\Lambda]} |F_t|$.
</aside>
Intuitively, we compute for each vertex $v$, the active interval $[t_{min}(v),t_{max}(v)]$, where:
At each time $t$, let $B_t$ be the set of all vertices whose active interval includes $t$, i.e., $B_t := \{ v \in V \mid t_{\min}(v) \leq t \leq t_{\max}(v) \}$.
The vim width of the temporal graph is defined as: $\mathsf{vim} := \max_t |B_t|$.
This parameter reflects the maximal number of vertices that are simultaneously "active" in their respective intervals. It abstracts the temporal structure in a way that enables dynamic programming approaches over time, especially when solving problems like edge exploration, temporal path counting, or scheduling.
VIM width is purely temporal: it depends only on the time-labeling of edges, not on the static structure of the footprint. It is particularly useful when vertices outside their active interval can be safely ignored during computation.
There exists a generalized bidirectional connected variant and a tree variant.
A vim decomposition can be found in TODO
FPT result via a dynamic program on a vim decomposition can be found as follows TODO
FPT result via an MSO formula can be found as follows TODO