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 Proceedings

Abstract

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
PublisherSpringer-Verlag London Ltd.
Chapter1
Pages1-13
Number of pages13
ISBN (Electronic)9783319961514
ISBN (Print)9783319961507
DOIs
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

Conference

Conference5th International Symposium on Combinatorial Optimization, ISCO 2018
CountryMorocco
CityMarrakesh
Period11/04/1813/04/18

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

  • Cite this

    Abu-Khzam, F. N., Egan, J., Gaspers, S., Shaw, A., & Shaw, P. (2018). Cluster editing with vertex splitting. In Combinatorial Optimization: 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, revised selected papers (pp. 1-13). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10856 LNCS). Springer-Verlag London Ltd.. https://doi.org/10.1007/978-3-319-96151-4_1