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.

Bocci, C., Capresi, C., Meeks, K., Sylvester, J. (2022). A New Temporal Interpretation of Cluster Editing. In Combinatorial Algorithms. IWOCA 2022 (pp.214-227). Cham : Springer [10.1007/978-3-031-06678-8_16].

A New Temporal Interpretation of Cluster Editing

Cristiano Bocci;
2022-01-01

Abstract

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.
978-3-031-06677-1
978-3-031-06678-8
Bocci, C., Capresi, C., Meeks, K., Sylvester, J. (2022). A New Temporal Interpretation of Cluster Editing. In Combinatorial Algorithms. IWOCA 2022 (pp.214-227). Cham : Springer [10.1007/978-3-031-06678-8_16].
File in questo prodotto:
File Dimensione Formato  
IWOCA_Cluster.pdf

non disponibili

Tipologia: Post-print
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 548.72 kB
Formato Adobe PDF
548.72 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1218519