A New Temporal Interpretation of Cluster Editing

The NP-complete graph problem Cluster Editing seeks to transform a static graph into disjoint union of cliques by making the fewest possible edits to the edge set. We introduce a natural interpreta- tion of this problem in the setting of temporal graphs, whose edge-sets are subject to discrete changes over time, which we call Editing to Tem- poral Cliques. 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 special cases with further restrictions. 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 P3; we demon- strate that there can be no universal characterisation of cluster temporal graphs in terms of subsets of at most four vertices. However, subject to a minor additional restriction, we obtain a characterisation involving for- bidden configurations on five vertices. This characterisation gives rise to an FPT algorithm parameterised simultaneously by the permitted num- ber of modifications and the lifetime of the temporal graph, which uses a simple search-tree strategy.