A PTAS for the Cluster Editing Problem on Planar Graphs

Andre Berger, Alexander Grigoriev*, Andrej Winokurow

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterAcademic

Abstract

The goal of the cluster editing problem is to add or delete a minimum number of edges from a given graph, so that the resulting graph becomes a union of disjoint cliques. The cluster editing problem is closely related to correlation clustering and has applications, e.g. In image segmentation. For general graphs this problem is apx apx{\mathbb {apx}}-hard. In this paper we present an efficient polynomial time approximation scheme for the cluster editing problem on graphs embeddable in the plane with a few edge crossings. The running time of the algorithm is 2 o(? -1 log(? -1 )) n 2o(?-1log?(?-1))n{2^{o\left( \epsilon ^{-1} \log (\epsilon ^{-1})\right) }n} for planar graphs and 2 o(k 2 ? -1 log(k 2 ? -1 )) n 2o(k2?-1log?(k2?-1))n2^{o\left( k^2\epsilon ^{-1}\log \left( k^2\epsilon ^{-1}\right) \right) }n for planar graphs with at most k crossings.
Original languageEnglish
Title of host publicationApproximation and Online Algorithms
PublisherSpringer
Pages27-39
Volume10138
EditionLecture Notes in Computer Science
ISBN (Electronic)978-3-319-51741-4
ISBN (Print)978-3-319-51740-7
DOIs
Publication statusPublished - 7 Jan 2017

Publication series

SeriesLecture Notes in Computer Science
Volume10138

Keywords

  • Graph approximation
  • Correlation clustering
  • Cluster editing
  • PTAS
  • k-planarity
  • Microscopy cell segmentation

Cite this