论文标题
解开网络障碍的计算复杂性
Disentangling the Computational Complexity of Network Untangling
论文作者
论文摘要
我们研究了Rozenshtein，Tatti和Gionis [DMKD 2021]引入的网络无纠结问题，该问题是时间图上顶点覆盖物的变体 - 图形集在离散时间步长上变化的图形。他们介绍了两个问题变体。目的是为每个顶点选择最多$ K $的时间间隔，以便涵盖所有时间边缘，并且（取决于问题变体）最大间隔长度或间隔长度的总总和最小化。该问题在查找活动时间表时具有数据挖掘应用程序，这些应用程序解释了复杂网络中实体的相互作用。 该问题的两个变体都是NP-HARD。在本文中，我们启动涉及以下参数的多元复杂性分析：顶点数，时间图的寿命，每个顶点间隔数和间隔长度绑定。对于这两个问题版本，我们（几乎）（几乎）完全解决了这四个参数的所有组合的参数化复杂性，从而描绘了固定参数障碍的边界。
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.
