Pith Number

pith:YQREIOVR

pith:2026:YQREIOVR42NV5ZAIBGIENC5XML

not attested not anchored not stored refs resolved

Clustering with Locally Bounded Ignorance

Christian Komusiewicz, Jaroslav Garvardt

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

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

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{YQREIOVR42NV5ZAIBGIENC5XML}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

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.

C2weakest assumption

The fuzzy edge graph (induced by weight-0 edges) has bounded degeneracy or closure; the kernelization algorithms rely on this structural restriction to produce a polynomial-size reduced instance.

C3one line summary

Correlation Clustering admits polynomial kernels parameterized by k plus degeneracy or closure of the fuzzy edge graph.

References

15 extracted · 15 resolved · 0 Pith anchors

[1] Correlation clustering.Mach 2004 · doi:10.1023/b:mach.0000033116.57574.95

[2] 1016/J.JDA.2012.04.005 2012 · doi:10.1016/j.jda.2012.04.005

[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. Rosamo 2009 · doi:10.1016/j.tcs.2009.05.006

[4] Multicut is FPT 2011

[5] 8 Alain Cournier and Michel Habib 1994 · doi:10.1007/s00453-011-9595-1

Receipt and verification

First computed	2026-05-17T23:39:18.736178Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

c422443ab1e69b5ee4080990468bb762c854a287882d2c18af841262b7b76f9a

Aliases

arxiv: 2605.13917 · arxiv_version: 2605.13917v1 · doi: 10.48550/arxiv.2605.13917 · pith_short_12: YQREIOVR42NV · pith_short_16: YQREIOVR42NV5ZAI · pith_short_8: YQREIOVR

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/YQREIOVR42NV5ZAIBGIENC5XML \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: c422443ab1e69b5ee4080990468bb762c854a287882d2c18af841262b7b76f9a

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "dd07ae6e0c2ef235db8d0392bd05984a1a89c0df9b558bc7516f3cafee8de6ff",
    "cross_cats_sorted": [
      "cs.CC"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.DS",
    "submitted_at": "2026-05-13T11:03:37Z",
    "title_canon_sha256": "89994982f834d74a855f794c52244ce29abadf5ad44331396eedfc7309ba32a8"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.13917",
    "kind": "arxiv",
    "version": 1
  }
}