Seminár z teoretickej informatiky - Alexandru Popa (29.9.2023)

v piatok 29.9.2023 o 13:00 hod. v miestnosti M 213


27. 09. 2023 10.58 hod.
Od: Rastislav Královič

Prednášajúci: prof. Alexandru Popa  (Faculty of Mathematics and Computer Science, University of Bucharest)

Názov: Timeline Cover in Temporal Graphs: Exact and Approximation Algorithms

Termín29.9.2023, 13:00 hod., M/213


Abstrakt:
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