Insights into the Complexity of Disentangling Temporal Graphs

We consider a variant of vertex cover in temporal graphs recently introduced to summarize timeline activities in social networks. Since the problem is already NP-hard when the time domain considered consists of two timestamps, we analyse the complexity of the problem in other restricted cases. We prove that the problem is NP-hard when (1) there exists exactly one interaction in each timestamp and (2) when each vertex has at most two interactions in each timestamp and the time domain consists of three timestamps. Moreover, we prove that the problem is fixed parameter tractable when the parameter is the size of the time window activity, which bounds the number of vertices with active temporal edges in a timestamp and the length of the interval where a vertex has incident temporal edges.