Timeline Cover in Temporal Graphs: Exact and Approximation Algorithms

13^th July 2023, 13:00 Ashton Lecture Theatre
Prof. Alexandru Popa
Faculty of Mathematics and Computer Science, University of Bucharest

Abstract

In this talk we present a variant of vertex cover on temporal graphs that has been recently introduced for timeline activities summarization in social networks. The problem has been proved to be NP-hard, even in restricted cases. We present algorithmic contributions for the problem. First, we present an approximation algorithm of factor $O(T \log{n})$, on a temporal graph of $T$ timestamps and $n$ vertices. Then, we consider the restriction where at most one temporal edge is defined in each timestamp. For this restriction, which has been recently shown to be NP-hard, we present a $4(T-1)$ approximation algorithm and a parameterized algorithm when the parameter is the cost (called span) of the solution.

Joint work with Riccardo Dondi

Additional Materials

• https://link.springer.com/chapter/10.1007/978-3-031-34347-6_15