arxiv: 2605.13917 · v1 · submitted 2026-05-13 · 💻 cs.DS · cs.CC

Recognition: no theorem link

Clustering with Locally Bounded Ignorance

Jaroslav Garvardt , Christian Komusiewicz

Authors on Pith no claims yet

Pith reviewed 2026-05-15 03:01 UTC · model grok-4.3

classification 💻 cs.DS cs.CC

keywords correlation clusteringkernelizationdegeneracyclosurefuzzy edge graphparameterized complexityedge multicut

0 comments

The pith

Correlation Clustering admits polynomial kernels when the fuzzy edge graph has bounded degeneracy or closure, for parameters combining solution cost with that bound.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies Correlation Clustering, the task of partitioning vertices to minimize total disagreement cost with a given weighted graph. Without extra structure the problem is fixed-parameter tractable in the optimum cost k yet believed to lack a polynomial kernel. The authors isolate the fuzzy edge graph formed by all zero-weight pairs and prove that a polynomial kernel exists whenever this graph has degeneracy d bounded, for the combined parameter k+d, and likewise for the closure parameter k+c. These results identify a structural restriction on the ignored (zero-weight) relations that turns an otherwise hard problem into one with small, efficiently computable reduced instances.

Core claim

Correlation Clustering admits a polynomial problem kernel when parameterized by k+d, where d is the degeneracy of the fuzzy edge graph, and when parameterized by k+c, where c is the closure of the fuzzy edge graph. The fuzzy edge graph is the graph induced by the weight-0 edges. These results complement the known FPT algorithm for parameter k alone by providing polynomial-size reduced instances under these structural restrictions on the zero-weight edges.

What carries the argument

The fuzzy edge graph induced by weight-0 edges, whose degeneracy or closure bounds the size of the kernel produced by the reduction rules.

If this is right

A polynomial kernel exists for the combined parameter k plus degeneracy of the fuzzy edge graph.
A polynomial kernel exists for the combined parameter k plus closure of the fuzzy edge graph.
Hardness results hold for Correlation Clustering on instances where the combined edge and non-edge graph has restricted structure but the fuzzy subgraph does not.
The same structural restrictions yield polynomial kernels for the closely related Edge Multicut problem.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Instances whose zero-weight relations form sparse graphs can be preprocessed to small size before solving.
The kernelization techniques may extend to other clustering problems whose disagreement graphs contain large sparse subgraphs.
Practical implementations could first compute degeneracy or closure of the zero-weight part and fall back to exact methods only when those numbers are small.

Load-bearing premise

The fuzzy edge graph induced by the zero-weight edges has bounded degeneracy or bounded closure.

What would settle it

A sequence of Correlation Clustering instances whose fuzzy edge graphs have degeneracy growing with n, for which every kernel must retain superpolynomial size in k.

read the original abstract

In Correlation Clustering, the input is a graph $G=(V,E)$ with weight function $\omega: {V \choose 2}\to Z$ and the task is to partition the vertex set into clusters such that the total weight of edges between clusters and missing edges inside clusters is minimized. Due to close connections between Correlation Clustering and Edge Multicut, deciding whether there is a partition with total cost at most $k$ is FPT with respect to $k$ but a polynomial kernel is presumably impossible. We study the influence of the structure of the fuzzy edge graph, that is, the graph induced by the weight-0 edges, on the problem complexity. We show in particular that Correlation Clustering admits a polynomial problem kernel when parameterized by $k+d$, where $d$ is the degeneracy of the fuzzy edge graph, and when parameterized by $k+c$, where $c$ is the closure of the fuzzy edge graph. We complement these positive results by showing hardness for several settings where the graph induced by the edges and nonedges has very restricted structure.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Correlation Clustering has new polynomial kernels when you parameterize by k plus degeneracy or closure on the zero-weight edges.

read the letter

Correlation Clustering admits polynomial kernels when parameterized by k plus the degeneracy of the fuzzy edge graph, and also by k plus the closure of that graph. That's the main thing to know about this paper. The authors take the standard observation that Correlation Clustering is FPT in k but unlikely to have a polynomial kernel, and they add structural parameters on the zero-weight edges to get around that. They define the fuzzy edge graph as the one induced by weight-0 edges and use its degeneracy d or closure c. The positive results are polynomial kernels for k+d and k+c. They also show hardness results when the graph induced by edges and non-edges has very restricted structure. This is solid work in the sense that it applies known kernelization ideas to a new combination of parameters and gives matching hardness in some cases. The definitions are standard graph theory, and the approach avoids any circular reasoning. The results seem reproducible in principle since they are algorithmic. The soft spots are that the structural restrictions on the fuzzy graph may not hold in many practical instances, so the kernels are more theoretical than immediately applicable. The hardness results are for specific restricted settings, which is fine but not surprising given the positive side. If the proofs have any gaps, they would likely be in the details of how the reduction rules bound the size by a polynomial in the parameters, but nothing in the abstract suggests a problem. This paper is aimed at researchers in parameterized complexity who work on clustering or cut problems. Someone looking for new ways to parameterize these problems to get kernels would find it useful. It deserves a serious referee because the claims are clear, the parameters are natural, and the results fill in part of the complexity map. I would recommend sending it to peer review.

Referee Report

0 major / 3 minor

Summary. The paper studies Correlation Clustering on graphs with integer edge weights, where the goal is to partition vertices to minimize the total cost of disagreements (inter-cluster edges and intra-cluster non-edges). It introduces the fuzzy edge graph induced by weight-0 edges and shows that the problem admits a polynomial kernel when parameterized by k+d (k the solution cost, d the degeneracy of the fuzzy graph) and by k+c (c the closure of the fuzzy graph). These kernelization results are complemented by hardness results for several restricted cases on the structure of edges and non-edges.

Significance. If the kernelization theorems hold, the work meaningfully extends FPT techniques for Correlation Clustering by leveraging degeneracy and closure parameters on the zero-weight subgraph. This is valuable because the problem is FPT in k alone but presumed to lack a polynomial kernel; the structural restrictions yield concrete polynomial bounds and are paired with matching hardness statements, strengthening the contribution in parameterized complexity.

minor comments (3)

§3 (Kernelization for k+d): the reduction rules for bounded-degeneracy fuzzy graphs are stated clearly, but the size bound derivation in the proof of Theorem 3.4 would benefit from an explicit polynomial degree (e.g., O((k+d)^c) for concrete c) rather than the current existential statement.
§4 (Closure parameterization): the definition of closure c is used in the kernel for k+c, yet the interaction between closure and the weight function ω is only sketched; a short example illustrating how a high-closure fuzzy graph forces many vertices into the kernel would improve readability.
§5 (Hardness results): the reductions for the restricted-structure cases are standard, but the paper should explicitly state whether the hardness holds for the optimization version or only the decision version with cost exactly k.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and the recommendation for minor revision. We are pleased that the report recognizes the value of our kernelization results for Correlation Clustering, which extend FPT techniques by incorporating degeneracy and closure parameters on the fuzzy edge graph induced by zero-weight edges, while providing matching hardness results.

Circularity Check

0 steps flagged

No significant circularity; derivation uses independent structural parameters and standard kernelization

full rationale

The paper defines the fuzzy edge graph directly from the input weight-0 edges and introduces parameters d (degeneracy) and c (closure) as standard graph-theoretic measures on that graph. The kernelization claims for parameterization by k+d and k+c are established via reduction rules that produce a polynomial-size instance bounded by a function of these parameters, without any equations that redefine the target quantity in terms of itself or rename fitted inputs as predictions. Hardness results for other structural restrictions are shown separately, confirming that the positive results do not collapse to self-referential definitions or self-citation chains. The derivation chain is self-contained against external graph theory benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard graph-theoretic definitions of degeneracy and closure together with known FPT techniques for Correlation Clustering and Edge Multicut; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)

standard math Degeneracy and closure are well-defined graph parameters that can be computed in polynomial time
Invoked when defining the additional parameters d and c for kernelization

pith-pipeline@v0.9.0 · 5506 in / 1181 out tokens · 45501 ms · 2026-05-15T03:01:26.258429+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Correlation clustering.Mach

1 Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering.Mach. Learn., 56(1-3):89–113, 2004.doi:10.1023/B:MACH.0000033116.57574.95. 2 Sebastian Böcker. A golden ratio parameterized algorithm for cluster editing.J. Discrete Algorithms, 16:79–89,

work page doi:10.1023/b:mach.0000033116.57574.95 2004
[2]

1016/J.JDA.2012.04.005

URL:https://doi.org/10.1016/j.jda.2012.04.005, doi:10. 1016/J.JDA.2012.04.005. 3 Sebastian Böcker and Jan Baumbach. Cluster editing. In Paola Bonizzoni, Vasco Brattka, and Benedikt Löwe, editors,The Nature of Computation. Logic, Algorithms, Applications - 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5,

work page doi:10.1016/j.jda.2012.04.005 2012
[3]

URL:https://doi.org/10.1016/j.tcs.2009.05.006, doi:10.1016/J.TCS.2009. 05.006. 5 Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini, Charis Pa- padopoulos, and Frances A. Rosamond. Clustering with partial information.Theor. Comput. Sci., 411(7-9):1202–1211,

work page doi:10.1016/j.tcs.2009.05.006 2009
[4]

Multicut is FPT

6 Nicolas Bousquet, Jean Daligault, and Stéphan Thomassé. Multicut is FPT. In Lance Fortnow and Salil P. Vadhan, editors,Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 459–468. ACM,

work page 2011
[5]

8 Alain Cournier and Michel Habib

URL:https://doi.org/10.1007/s00453-011-9595-1, doi:10.1007/ S00453-011-9595-1. 8 Alain Cournier and Michel Habib. A new linear algorithm for modular decomposition. In Sophie Tison, editor,Trees in Algebra and Programming - CAAP’94, 19th International Colloquium, Edinburgh, UK, April 11-13, 1994, Proceedings, volume 787 ofLecture Notes in Computer Science,...

work page doi:10.1007/s00453-011-9595-1 1994
[6]

Garvardt and C

J. Garvardt and C. Komusiewicz 21 19 Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, and Saket Saurabh. Further exploitingc-closure for FPT algorithms and kernels for domination problems.SIAM J. Disc. Math., 37(4):2626–2669, 2023.arXiv:https://doi.org/10.1137/22M1491721, doi: 10.1137/22M1491721. 20 Tomohiro Koana, Christian Komusiewic...

work page doi:10.1137/22m1491721 2023
[7]

URL:https: //drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.42, doi:10.4230/ LIPIcs.STACS.2022.42

Schloss Dagstuhl – Leibniz-Zentrum für Informatik. URL:https: //drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.42, doi:10.4230/ LIPIcs.STACS.2022.42. 21 Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Exploitingc-closure in kernel- ization algorithms for graph problems.SIAM J. Discret. Math., 36(4):2798–2821,

work page doi:10.4230/lipics.stacs.2022.42 2022
[8]

22 Tomohiro Koana, Christian Komusiewicz, and Frank Sommer

URL: https://doi.org/10.1137/21m1449476,doi:10.1137/21M1449476. 22 Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Computing dense and sparse subgraphs of weakly closed graphs.Algorithmica, 85(7):2156–2187,

work page doi:10.1137/21m1449476
[9]

23 Tomohiro Koana, Christian Komusiewicz, and Frank Sommer

URL: https: //doi.org/10.1007/s00453-022-01090-z,doi:10.1007/S00453-022-01090-Z. 23 Tomohiro Koana, Christian Komusiewicz, and Frank Sommer. Essentially tight kernels for (weakly) closed graphs.Algorithmica, 85(6):1706–1735,

work page doi:10.1007/s00453-022-01090-z
[10]

1007/s00453-022-01088-7,doi:10.1007/S00453-022-01088-7

URL: https://doi.org/10. 1007/s00453-022-01088-7,doi:10.1007/S00453-022-01088-7. 24 Tomohiro Koana and André Nichterlein. Detecting and enumerating small induced subgraphs in c-closed graphs.Disc. Appl. Math., 302:198–207,

work page doi:10.1007/s00453-022-01088-7
[11]

com/science/article/pii/S0166218X21002572,doi:10.1016/j.dam.2021.06.019

URL:https://www.sciencedirect. com/science/article/pii/S0166218X21002572,doi:10.1016/j.dam.2021.06.019. 25 Christian Komusiewicz and Johannes Uhlmann. Alternative parameterizations for cluster editing. In Ivana Cerná, Tibor Gyimóthy, Juraj Hromkovic, Keith G. Jeffery, Rastislav Královic, Marko Vukolic, and Stefan Wolf, editors,SOFSEM 2011: Theory and Prac...

work page doi:10.1016/j.dam.2021.06.019 2021
[12]

Springer, 2011.doi:10.1007/978-3-642-18381-2\_29

Proceedings, volume 6543 ofLecture Notes in Computer Science, pages 344–355. Springer, 2011.doi:10.1007/978-3-642-18381-2\_29. 26 Christian Komusiewicz and Johannes Uhlmann. Cluster editing with locally bounded modifi- cations.Discret. Appl. Math., 160(15):2259–2270,

work page doi:10.1007/978-3-642-18381-2 2011
[13]

Fixed-parameter tractability of multicut parameterized by the size of the cutset

28 Dániel Marx and Igor Razgon. Fixed-parameter tractability of multicut parameterized by the size of the cutset. In Lance Fortnow and Salil P. Vadhan, editors,Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 469–478. ACM,

work page 2011
[14]

McConnell and Jeremy P

29 Ross M. McConnell and Jeremy P. Spinrad. Linear-time modular decomposition and efficient transitive orientation of comparability graphs. In Daniel Dominic Sleator, editor,Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia, USA, pages 536–545. ACM/SIAM,

work page 1994
[15]

URL: https://www.sciencedirect.com/science/article/pii/S0166218X04001957, doi:10.1016/j.dam.2004.01.007

Discrete Mathematics and Data Min- ing. URL: https://www.sciencedirect.com/science/article/pii/S0166218X04001957, doi:10.1016/j.dam.2004.01.007. 31 René van Bevern, Vincent Froese, and Christian Komusiewicz. Parameterizing edge modifica- tion problems above lower bounds.Theory Comput. Syst., 62(3):739–770, 2018

work page doi:10.1016/j.dam.2004.01.007 2004