Cluster editing with vertex splitting

Faisal N. Abu-Khzam, Judith Egan, Serge Gaspers, Alexis Shaw, Peter Shaw

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedingspeer-review


In the Cluster Editing problem, a given graph is to be transformed into a disjoint union of cliques via a minimum number of edge editing operations. In this paper we introduce a new variant of Cluster Editing whereby a vertex can be divided, or split, into two or more vertices thus allowing a single vertex to belong to multiple clusters. This new problem, Cluster Editing with Vertex Splitting, has applications in finding correlation clusters in discrete data, including graphs obtained from Biological Network analysis. We initiate the study of this new problem and show that it is fixed-parameter tractable when parameterized by the total number of vertex splitting and edge editing operations. In particular we obtain a 4k(k+1) vertex kernel for the problem.

Original languageEnglish
Title of host publicationCombinatorial Optimization
Subtitle of host publication5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, revised selected papers
EditorsJon Lee, Giovanni Rinaldi, A. Ridha Mahjoub
Place of PublicationCham, Switzerland
PublisherSpringer-Verlag London Ltd.
Number of pages13
ISBN (Electronic)9783319961514
ISBN (Print)9783319961507
Publication statusPublished - 18 Jul 2018
Event5th International Symposium on Combinatorial Optimization, ISCO 2018 - Marrakesh, Morocco
Duration: 11 Apr 201813 Apr 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10856 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference5th International Symposium on Combinatorial Optimization, ISCO 2018


Dive into the research topics of 'Cluster editing with vertex splitting'. Together they form a unique fingerprint.

Cite this