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