Cluster editing: Kernelization based on edge cuts

Yixin Cao, Jianer Chen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

26 Citations (Scopus)

Abstract

Kernelization algorithms for the cluster editing problem have been a popular topic in the recent research in parameterized computation. Most kernelization algorithms for the problem are based on the concept of critical cliques. In this paper, we present new observations and new techniques for the study of kernelization algorithms for the cluster editing problem. Our techniques are based on the study of the relationship between cluster editing and graph edge-cuts. As an application, we present a simple algorithm that constructs a 2k-vertex kernel for the integral-weighted version of the cluster editing problem. Our result matches the best kernel bound for the unweighted version of the cluster editing problem, and significantly improves the previous best kernel bound for the weighted version of the problem. For the more general real-weighted version of the problem, our techniques lead to a simple kernelization algorithm that constructs a kernel of at most 4k vertices.
Original languageEnglish
Pages (from-to)152-169
Number of pages18
JournalAlgorithmica
Volume64
Issue number1
DOIs
Publication statusPublished - 1 Sep 2012
Externally publishedYes

Keywords

  • Bioinformatics
  • Cluster editing
  • Edge-cut
  • Kernelization
  • Parameterized computation

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this