tree-interval-membership width (TIM)

<aside> 🌐

Outdated page — the Temporal Graph Wiki has moved. Read this page 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:

$\mathsf{tw}\leq \mathsf{pw}\leq \mathsf{vim}$ and
$\mathsf{tw}\leq \mathsf{tim}\leq \mathsf{vim}$.

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 Tree-Interval-Membership (TIM) width generalizes vertex-interval-membership (VIM) width by relaxing the decomposition structure from a linear sequence to a directed tree (almost). This allows more flexibility: multiple bags can exist at the same time step, and each bag can contain only a part of the active vertices (one connected component). This is especially useful for problems where connected components at the same time step can be treated independently.

While in a VIM sequence there is exactly one bag per time step, in a TIM decomposition the bags are indexed by a directed ‘tree’ and may overlap in time. This decomposition structure better captures the temporal evolution of disconnected components and enables refined algorithmic techniques.

Let $\mathcal{G} = (V, E, \lambda)$ be a temporal graph with lifetime $\Lambda$.

Definition.

A Tree-Interval-Membership (TIM) decomposition of a temporal graph $\mathcal{G}$ is a triple $(T, \mathcal{B}, \tau)$ where:

$T$ is a directed tree,
$\mathcal{B} = { B(s) \mid s \in V(T) }$ is a collection of bags, each $B(s) \subseteq V$,
$\tau : \mathcal{B} \to [\Lambda]$ assigns a time step to each bag,

such that:

Vertex uniqueness at each time:

For every $v \in V$ and every $t \in [\Lambda]$, there exists a unique node $i \in V(T)$ such that $\tau(B(i)) = t$ and $v \in B(i)$.
Edge coverage:

For every temporal edge $(uv, t) \in E$, there exists a unique node $i \in V(T)$ such that ${u, v} \subseteq B(i)$ and $\tau(B(i)) = t$.
Tree structure:

The arcs of $T$ are precisely those pairs $(i, j)$ such that $B(i) \cap B(j) \ne \emptyset$ and $\tau(B(j)) = \tau(B(i)) + 1$.

The width of the decomposition is $\max_{s \in V(T)} \lvert B(s)\rvert$.

The TIM width of $\mathcal{G}$ is the minimum such width over all valid TIM decompositions of $\mathcal{G}$.

</aside>

A TIM decomposition can be found in TODO

A dynamic program on a TIM decomposition can be found as follows TODO