New Approximations for Temporal Vertex Cover on Always Star Temporal Graphs
For researchers working on temporal graph algorithms, this work provides efficient approximations for a specific graph class, though the results are incremental.
The paper presents two polynomial-time approximation algorithms for Sliding Window Temporal Vertex Cover on always star temporal graphs, achieving approximation ratios of 2Δ-1 and Δ-1 with running times O(T) and O(TmΔ^2), respectively. Experiments show the new algorithms outperform existing ones in running time, and a novel implementation of the d-approximation algorithm improves its runtime.
Modern networks are highly dynamic, and temporal graphs capture these changes through discrete edge appearances on a fixed vertex set, known in advance up to the graph's lifetime. The Vertex Cover problem extends to the temporal setting as Temporal Vertex Cover (TVC) and Sliding Window Temporal Vertex Cover (SW-TVC). In TVC, each edge is covered by one endpoint over the lifetime, while in SW-TVC, edges are covered within every $Δ$-step window. In always star temporal graphs, each snapshot is a star with a center that may change at each time step. TVC is NP-complete on always star temporal graphs, but an FPT algorithm parameterized by $Δ$ solves it optimally in $O(TΔ(n+m)\cdot 2^Δ)$. This paper presents two polynomial-time approximation algorithms for SW-TVC on always star temporal graphs, achieving $2Δ-1$ and $Δ-1$ approximation ratios with running times $O(T)$ and $O(TmΔ^2)$, respectively. These algorithms provide exact solutions for $Δ=1$ and $Δ\leq 2$. Additionally, we offer the first implementation and experimental evaluation of state-of-the-art approximation algorithms with $d$ and $d-1$ approximation ratios, where $d$ is the maximum degree of any snapshot. Our experiments on artificially generated always star temporal graphs show that the new approximation algorithms outperform the known $d-1$ approximation in running time, even in some cases where $Δ>d$. We test state-of-the-art algorithms on real-world data and observe that the $d-1$ approximation algorithm outperforms the analytically better $d$ approximation algorithm in running time when implemented as described in the original paper. However, a novel implementation of the $d$ approximation algorithm significantly improves its runtime, surpassing $d-1$ in practice. Nonetheless, the $d-1$ approximation consistently computes smaller solutions.