Cluster editing with vertex splitting

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

doi:10.1007/978-3-319-96151-4_1

Cluster editing with vertex splitting

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

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper published in Proceedings › peer-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 language	English
Title of host publication	Combinatorial Optimization
Subtitle of host publication	5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, revised selected papers
Editors	Jon Lee, Giovanni Rinaldi, A. Ridha Mahjoub
Place of Publication	Cham, Switzerland
Publisher	Springer-Verlag London Ltd.
Chapter	1
Pages	1-13
Number of pages	13
Edition	1
ISBN (Electronic)	9783319961514
ISBN (Print)	9783319961507
DOIs	https://doi.org/10.1007/978-3-319-96151-4_1
Publication status	Published - 18 Jul 2018
Event	5th International Symposium on Combinatorial Optimization, ISCO 2018 - Marrakesh, Morocco Duration: 11 Apr 2018 → 13 Apr 2018

Publication series

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

Conference

Conference	5th International Symposium on Combinatorial Optimization, ISCO 2018
Country/Territory	Morocco
City	Marrakesh
Period	11/04/18 → 13/04/18

Access to Document

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

Cite this

Abu-Khzam, F. N., Egan, J., Gaspers, S., Shaw, A., & Shaw, P. (2018). Cluster editing with vertex splitting. In J. Lee, G. Rinaldi, & A. R. Mahjoub (Eds.), Combinatorial Optimization: 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, revised selected papers (1 ed., 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 et al. / Cluster editing with vertex splitting. Combinatorial Optimization: 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, revised selected papers. editor / Jon Lee ; Giovanni Rinaldi ; A. Ridha Mahjoub. 1. ed. Cham, Switzerland : 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 = jul,

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",

editor = "Jon Lee and Giovanni Rinaldi and Mahjoub, {A. Ridha }",

booktitle = "Combinatorial Optimization",

address = "Germany",

edition = "1",

note = "5th International Symposium on Combinatorial Optimization, ISCO 2018 ; Conference date: 11-04-2018 Through 13-04-2018",

}

Abu-Khzam, FN, Egan, J, Gaspers, S, Shaw, A & Shaw, P 2018, Cluster editing with vertex splitting. in J Lee, G Rinaldi & AR Mahjoub (eds), Combinatorial Optimization: 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, revised selected papers. 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10856 LNCS, Springer-Verlag London Ltd., Cham, Switzerland, 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 et al.
Combinatorial Optimization: 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, revised selected papers. ed. / Jon Lee; Giovanni Rinaldi; A. Ridha Mahjoub. 1. ed. Cham, Switzerland: 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 proceeding › Conference Paper published in Proceedings › peer-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

AN - SCOPUS:85050612965

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

A2 - Lee, Jon

A2 - Rinaldi, Giovanni

A2 - Mahjoub, A. Ridha

PB - Springer-Verlag London Ltd.

CY - Cham, Switzerland

T2 - 5th International Symposium on Combinatorial Optimization, ISCO 2018

Y2 - 11 April 2018 through 13 April 2018

ER -

Abu-Khzam FN, Egan J, Gaspers S, Shaw A, Shaw P. Cluster editing with vertex splitting. In Lee J, Rinaldi G, Mahjoub AR, editors, Combinatorial Optimization: 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11-13, 2018, revised selected papers. 1 ed. Cham, Switzerland: 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)). doi: 10.1007/978-3-319-96151-4_1

Cluster editing with vertex splitting

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this