A New Temporal Interpretation of Cluster Editing

Bocci, Cristiano, Capresi, Chiara, Meeks, Kitty and Sylvester, John ORCID: 0000-0002-6543-2934
(2022) A New Temporal Interpretation of Cluster Editing. [Preprint]

[thumbnail of IWOCA_Cluster.pdf] PDF
IWOCA_Cluster.pdf - Other

Download (561kB) | Preview


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.

Item Type: Preprint
Additional Information: 27 pages, 2 figures. Extended abstract appeared at IWOCA 2022
Uncontrolled Keywords: cs.DM, cs.DM, cs.CC, cs.DS, math.CO, 05C75, 05C85, 68Q25, G.2.2; F.2.2
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 15 Mar 2023 09:55
Last Modified: 15 May 2024 14:23
DOI: 10.2139/ssrn.4184782
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3169046