DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2022.25

Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time

Authors: Hjalmar Schulz, André Nichterlein, Rolf Niedermeier, and Christopher Weyand

Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

Abstract

Given an undirected graph, the task in Cluster Editing is to insert and delete a minimum number of edges to obtain a cluster graph, that is, a disjoint union of cliques. In the weighted variant each vertex pair comes with a weight and the edge modifications have to be of minimum overall weight. In this work, we provide the first polynomial-time algorithm to apply the following data reduction rule of Böcker et al. [Algorithmica, 2011] for Weighted Cluster Editing: For a graph G = (V,E), merge a vertex set S ⊆ V into a single vertex if the minimum cut of G[S] is at least the combined cost of inserting all missing edges within G[S] plus the cost of cutting all edges from S to the rest of the graph. Complementing our theoretical findings, we experimentally demonstrate the effectiveness of the data reduction rule, shrinking real-world test instances from the PACE Challenge 2021 by around 24% while previous heuristic implementations of the data reduction rule only achieve 8%.

Cite as

Hjalmar Schulz, André Nichterlein, Rolf Niedermeier, and Christopher Weyand. Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{schulz_et_al:LIPIcs.IPEC.2022.25,
  author =	{Schulz, Hjalmar and Nichterlein, Andr\'{e} and Niedermeier, Rolf and Weyand, Christopher},
  title =	{{Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.25},
  URN =		{urn:nbn:de:0030-drops-173816},
  doi =		{10.4230/LIPIcs.IPEC.2022.25},
  annote =	{Keywords: Correlation Clustering, Minimum Cut, Maximum s-t-Flow}
}

Search Results

Documents authored by Schulz, Hjalmar

Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time

Abstract

Cite as

Thanks for your feedback!

Could not send message