Exact and approximation algorithms for covering timeline in temporal graphs

We consider a variant of vertex cover on temporal graphs that has been recently defined for summarization of timeline activities in temporal graphs. The problem has been proved to be NP-hard, even for several restrictions of the time domain and vertex degree. We present novel algorithmic contributions for the problem and we give an approximation algorithm of factor \(O(T \log {n})\) $O(Tlogn)$ , on a temporal graph of T timestamps and n vertices. We focus then on the NP-hard restriction of the problem, where at most one temporal edge is defined in each timestamp. For this restriction we present a \(4(T-1)\) $4(T-1)$ approximation algorithm and a parameterized algorithm (a reduction to kernel) for parameter the cost, called span, of the solution.