2026-07-22T16:11:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17381 2024-03-06T10:59:36Z ddc:004 open_access

Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time Schulz, Hjalmar Nichterlein, André Niedermeier, Rolf Weyand, Christopher Correlation Clustering Minimum Cut Maximum s-t-Flow 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%. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hjalmar Schulz and André Nichterlein and Rolf Niedermeier and Christopher Weyand 2022 Is Part Of LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2022.25 urn:nbn:de:0030-drops-173816 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.25 eng https://creativecommons.org/licenses/by/4.0/legalcode