The NP-complete graph problem Cluster Editing seeks to transform a static graph into a disjoint union of cliques by making the fewest possible edits to the edges. We introduce a natural interpretation of this problem in temporal graphs, whose edge sets change over time. This problem is NP-complete even when restricted to temporal graphs whose underlying graph is a path, but we obtain two polynomial-time algorithms for restricted cases. In the static setting, it is well-known that a graph is a disjoint union of cliques if and only if it contains no induced copy of $P_3$; we demonstrate that no general characterisation involving sets of at most four vertices can exist in the temporal setting, but obtain a complete characterisation involving forbidden configurations on at most five vertices. This characterisation gives rise to an FPT algorithm parameterised simultaneously by the permitted number of modifications and the lifetime of the temporal graph.
翻译:NP- 完整的图形问题群集编辑试图将静态图形转换成分解的晶体组合, 方法是对边缘进行尽可能少的编辑。 我们在时间图中引入了对这一问题的自然解释, 时间图的边缘随着时间变化而变化。 这个问题即使局限于其底图是路径的瞬时图, 也已经完全解决了 NP 问题, 但我们为限制的个案获得了两个多数值- 时间算法。 在静态设置中, 众所周知, 一个图形是cliques的分解组合, 如果并且只有它不包含 $P_ 3 的导出副本; 我们证明, 在时间设置中, 最多有四个顶点的数组不会存在一般特征化, 但是在最多五个顶点上获得禁止配置的完整特征化。 这种特征化产生一种FPT 算法, 由允许的修改次数和时间图的寿命同时参数化 。