Cluster Editing with Vertex Splitting

Publisher:
Springer
Publication Type:
Chapter
Citation:
Combinatorial Optimization 5th International Symposium, ISCO 2018, Marrakesh, Morocco, April 11–13, 2018, Revised Selected Papers, 2018, 10856 pp. 1 - 13 (13)
Issue Date:
2018-07-18
Metrics:
Full metadata record
Files in This Item:
Filename Description Size
Cluster_Editing_with_Vertex_Splitting.pdfAccepted Manuscript version256.36 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: