License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.25
URN: urn:nbn:de:0030-drops-173816
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17381/
Schulz, Hjalmar ;
Nichterlein, André ;
Niedermeier, Rolf ;
Weyand, Christopher
Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time
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%.
BibTeX - Entry
@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/opus/volltexte/2022/17381},
URN = {urn:nbn:de:0030-drops-173816},
doi = {10.4230/LIPIcs.IPEC.2022.25},
annote = {Keywords: Correlation Clustering, Minimum Cut, Maximum s-t-Flow}
}
