  We study the network untangling problem introduced by Rozenshtein, Tatti, and
Gionis [DMKD 2021], which is a variant of Vertex Cover on temporal graphs --
graphs whose edge set changes over discrete time steps. They introduce two
problem variants. The goal is to select at most $k$ time intervals for each
vertex such that all time-edges are covered and (depending on the problem
variant) either the maximum interval length or the total sum of interval
lengths is minimized. This problem has data mining applications in finding
activity timelines that explain the interactions of entities in complex
networks.
  Both variants of the problem are NP-hard. In this paper, we initiate a
multivariate complexity analysis involving the following parameters: number of
vertices, lifetime of the temporal graph, number of intervals per vertex, and
the interval length bound. For both problem versions, we (almost) completely
settle the parameterized complexity for all combinations of those four
parameters, thereby delineating the border of fixed-parameter tractability.
