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 ProceedingsResearchpeer-review

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

Electric network analysis
Vertex of a graph
Discrete Data
Biological Networks
Network Analysis
Graph in graph theory
Clique
Disjoint
Union
kernel

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
Abu-Khzam, Faisal N. ; Egan, Judith ; Gaspers, Serge ; Shaw, Alexis ; Shaw, Peter. / Cluster editing with vertex splitting. Combinatorial Optimization: 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, revised selected papers. Springer-Verlag London Ltd., 2018. pp. 1-13 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{90e89100ee9342c7998763642012e3dd,
title = "Cluster editing with vertex splitting",
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.",
author = "Abu-Khzam, {Faisal N.} and Judith Egan and Serge Gaspers and Alexis Shaw and Peter Shaw",
year = "2018",
month = "7",
day = "18",
doi = "10.1007/978-3-319-96151-4_1",
language = "English",
isbn = "9783319961507",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag London Ltd.",
pages = "1--13",
booktitle = "Combinatorial Optimization",
address = "Germany",

}

Abu-Khzam, FN, 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10856 LNCS, Springer-Verlag London Ltd., pp. 1-13, 5th International Symposium on Combinatorial Optimization, ISCO 2018, Marrakesh, Morocco, 11/04/18. https://doi.org/10.1007/978-3-319-96151-4_1

Cluster editing with vertex splitting. / Abu-Khzam, Faisal N.; Egan, Judith; Gaspers, Serge; Shaw, Alexis; Shaw, Peter.

Combinatorial Optimization: 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, revised selected papers. Springer-Verlag London Ltd., 2018. p. 1-13 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10856 LNCS).

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

TY - GEN

T1 - Cluster editing with vertex splitting

AU - Abu-Khzam, Faisal N.

AU - Egan, Judith

AU - Gaspers, Serge

AU - Shaw, Alexis

AU - Shaw, Peter

PY - 2018/7/18

Y1 - 2018/7/18

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85050612965&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-96151-4_1

DO - 10.1007/978-3-319-96151-4_1

M3 - Conference Paper published in Proceedings

SN - 9783319961507

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 13

BT - Combinatorial Optimization

PB - Springer-Verlag London Ltd.

ER -

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