## 4 Deep Learning-Based Minimum Timeline Cover
### Iterative Algorithm
#### 4.5.3 Minimal Timeline Completion Validity  
According to Theorem 1, we can show that the output computed by Algorithm 1 is a valid solution (i.e., covers all temporal edges) and compute the solution with a locally minimal increase (i.e., reducing any intervals among those increased results in a solution which is not valid). **Theorem 1**. : _Given any initial set of activity intervals \(\mathcal{T}=I_{u}=[s_{u},e_{u}]u\in V\) and a temporal graph \(G=(V,E)\), the Minimal Timeline Completion algorithm produces adjusted intervals \(\mathcal{T}^{\prime}=I^{\prime}_{u}=[s^{\prime}_{u},e^{\prime}_{u}]u\in V\) that meet the following criteria:_  
1. _They cover all temporal edges in_ \(E\)_, i.e., for every_ \((u,v,t)\in E\)_,_ \(t\in I^{\prime}_{u}\) _or_ \(t\in I^{\prime}_{v}\)_._
2. _They are locally minimal with respect to sum-span increase, that is, no final interval can be reduced without leaving at least one temporal edge uncovered. Moreover, each incremental expansion chosen by the algorithm was the minimal possible increase at the time it was made._  
The proof of Theorem 1 can be carried out by showing first of all that the algorithm produces intervals that cover all edges, and then showing that the increased sum-span produced is minimal, i.e., any further reduction in the increased intervals would result in uncovered edges. Proof. : Part 1: The algorithm produces intervals that cover all edges. The algorithm starts from an initial set of intervals \(\mathcal{T}\) and identifies all uncovered edges:  
\[U=\{(u,v,t)\in E\mid t\
ot\in I_{u}\wedge t\
otin I_{v}\}.\]  
For each edge \((u,v,t)\in U\), the algorithm determines the minimal necessary increase to adjust either \(I_{u}\) or \(I_{v}\) so that \(t\) falls within it. One of these intervals is then extended just enough to cover \(t\). As a result, this edge is no longer uncovered. Since the algorithm processes each uncovered edge in \(U\) in this manner, every edge initially in \(U\) will be covered by at least one updated interval after these adjustments. Thus, when no uncovered edges remain, every \((u,v,t)\in E\) is covered by \(I^{\prime}_{u}\) or \(I^{\prime}_{v}\). Hence, the final set of intervals \(\mathcal{T}^{\prime}\) covers all temporal edges. Part 2: Local minimality of the total sum-span increase. Consider an uncovered edge \((u,v,t)\in U\). To cover it, the algorithm calculates the increases required to include \(t\) in \(I_{u}\) or \(I_{v}\):  
\[\delta_{u}= \begin{cases}s_{u}-t,&\text{if }t<s_{u}\\ t-e_{u},&\text{if }t>e_{u}\\ 0,&\text{if }t\in[s_{u},e_{u}]\end{cases} \quad\quad\text{and}\quad\delta_{v}= \begin{cases}s_{v}-t,&\text{if }t<s_{v}\\ t-e_{v},&\text{if }t>e_{v}\\ 0,&\text{if }t\in[s_{v},e_{v}].\end{cases} \]  
The algorithm picks the endpoint with the minimal increase \(\delta=\min(\delta_{u},\delta_{v})\) and adjusts its interval accordingly. This choice ensures that for each uncovered edge, the increase in sum-span is as small as possible at the moment of adjustment. Now consider the final solution \(\mathcal{T}^{\prime}\) after all uncovered edges are addressed. Suppose we attempt to reduce the sum-span of this solution by shrinking one of the intervals \(I^{\prime}_{u}=[s^{\prime}_{u},e^{\prime}_{u}]\). Any attempt to decrease \(e^{\prime}_{u}\) or increase \(s^{\prime}_{u}\) may exclude a timestamp that was previously uncovered and is now covered only by \(I^{\prime}_{u}\). Because the algorithm always adjusted intervals minimally, there is no \"slack\" that can be removed without losing coverage of at least one temporal edge. This implies the solution is locally minimal: there is no unilateral reduction in the updated intervals that can decrease the total sum-span without uncovering an edge. Furthermore, at each individual step of covering an edge, the chosen increment was minimal. Hence, for each uncovered edge at the time it was covered, no smaller incremental adjustment could have achieved coverage. Part 3: No further reductions are possible without losing coverage.