Untangling temporal graphs of bounded degree

In this contribution we consider a variant of the vertex cover problem in temporal graphs that has been recently introduced to summarize timeline activities in social networks. The problem is NP-hard, even when the time domain considered consists of two timestamps. We further analyze the complexity of this problem, focusing on temporal graphs of bounded degree. We prove that the problem is NP-hard when (1) each vertex has degree at most one in each timestamp and (2) each vertex is connected with at most three neighbors, has degree at most two in each timestamp and the time domain consists of three timestamps. On the other hand, we prove that the problem is in P when each vertex is connected with at most two neighbors. Then we present a fixed-parameter algorithm for the restriction where we bound the number of interactions in each timestamp and the length of the interval where a vertex has incident temporal edges. (c) 2023 Elsevier B.V. All rights reserved.