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.
翻译:我们研究了Rozenshtein、Tatti和Gionis[DMKD 2021]提出的未解开问题的网络,这是时间图上的Vertex Cover的变体 -- -- 其边缘在离散时间步骤上设定变化的图形。它们引入了两个问题变体。目标是为每个顶端选择最多为美元的时间间隔,以便覆盖所有时间间隔(视问题变体而定),或者尽可能缩小最大间隔长度或间隔长度总和。这个问题在寻找能够解释复杂网络中实体相互作用的活动时间表方面有数据挖掘应用。两种问题变体都是NP硬的。在本文件中,我们发起了一个多变量复杂程度分析,涉及以下参数:脊椎的数目、时间图的寿命、每个顶点的间隔数以及间隔线。对于这两个问题版本,我们(最大部分)完全解决了这四个参数的所有组合的参数的参数复杂性,从而分解了固定参数的边界。