A Note on the Inapproximability of Correlation Clustering

incorrectly) classified with respect to the labels is maximized (resp.

Entity Class

Research

Jurisdiction

Global

Characters Indexed

21K

Minted

2026-06-29

Source

https://arxiv.org/abs/0704.2092…

Pipeline

BST-PIPELINE-1.0.0

◈ Canonical Citation — Copy These URLs ROOT-LD · MANIFEST · INDEX

Canonical URL

https://boisestandard.org/ai/research/0704.2092/

Root-LD JSON

https://boisestandard.org/ai/research/0704.2092/root-ld.json

Manifest JSON

https://boisestandard.org/ai/research/0704.2092/manifest.json

Index JSON

https://boisestandard.org/ai/research/0704.2092/index.json

◈ Document Body — Full Text · 21K CharactersFTS5 INDEXED

9002 raM 32 ]GL.sc[ 2v2902.4070:viXra A Note on the Inapproximability of Correlation Clustering ∗ Jinsong Tan Abstract We consider inapproximability of the correlation clustering problem defined as follows: Given a graph G = (V,E) where each edge is labeled either ”+” (similar) or ”−” (dissimilar), correla- tion clustering seeks to partition the vertices into clusters so that the number of pairs correctly (resp. incorrectly) classified with respect to the labels is maximized (resp. minimized). The two complementary problems are called MaxAgree and MinDisagree, respectively, and have been studied on complete graphs, where every edge is labeled, and general graphs, where some edge might not have been labeled. Natural edge-weighted versions of both problems have been studied as well. Let S-MaxAgree denote the weighted problem where all weights are taken from set S, we show that S-MaxAgree with weights bounded by O(|V |1/2−δ) essentially belongs to the same hardness class in the following sense: if there is a polynomial time algorithm that approximates S-MaxAgree within a factor of λ = O(log|V |) with high probability, then for any choice of S′, S′-MaxAgree can be approximated in polynomial time within a factor of (λ + ǫ), where ǫ > 0 can be arbitrarily small, with high probability. A similar statement also holds for S-MinDisagree. This result implies it is hard (assuming NP 6= RP) to approximate unweighted MaxAgree within a factor of 80/79−ǫ, improving upon a previous known factor of 116/115−ǫ by Charikar et. al. [4].1 Keywords: Correlation Clustering, Inapproximability, Randomized Rounding, Graph Algorithm 1 Introduction Motivated by applications of document clustering, Bansal, Blum and Chawla [2] introduced the correlation clustering problem where for a corpus of documents, we represent each document by a node, and an edge (u,v) is labeled ”+” or ”−” depending on whether the two documents are similar or dissimilar, respectively. The goal of correlation clustering is thus to find a partition of the nodes into clusters that agree as much as possible with the edge labels. Specifically, there are two complementary problems. MaxAgree aims to maximize the number of agreements: the number of + edges inside clusters plus the number of − edges across clusters; on the other hand, MinDisagree aims to minimize the number of disagreements: the number of + edges across different clusters plus the number of − edges inside clusters. Correlation clustering is also viewed as a kind of agnostic learning problem [9] and seems to have been first studied by Ben- Dor et al. [3] with applications in computational biology; Shamir et al. [10] were the first to formalize it as a graph-theoretic problem, which they called Cluster Editing. Since Bansal et al.s independent introduction of this problem [2], it has been studied quite extensively in recent years [1, 4, 5, 6, 7, 11]. ∗ Department of Computer & Information Sciences, University of Pennsylvania, Philadelphia, PA 1910

◈ Root-LD — Three-Layer Provenance Record HELIX POSITION 1

LAYER 1 — ANCHOR · IMMUTABLE · PROVENANCE CORE · FEDERATION ID · 2026-06-29

{
  "@type": "rld:Anchor",
  "rld:uuid": "9aeda165-0cb5-4206-bbad-c265c19b5a6f",
  "rld:federationId": "bs-9225ec04",
  "rld:contentHash": "19151a55d248290024302d5b49c79722df302cbc371afc209d599bdc1b78bf22",
  "rld:primarySource": "https://arxiv.org/abs/0704.2092",
  "rld:sourceDomain": "",
  "rld:sourceVerified": false,
  "rld:collectionMethod": "fetch",
  "rld:collectionDate": "2026-06-29T22:01:19.292466+00:00",
  "rld:generationMethod": "automated",
  "rld:humanVerified": false,
  "rld:specVersion": "1.0",
  "rld:mintedAt": "2026-06-29T22:03:25.711837+00:00",
  "rld:pipeline": "BST-PIPELINE-1.0.0",
  "rld:pipelineRunId": "BST-PIPELINE-1.0.0-2026-06-29T22:01:19Z",
  "rld:entityClass": "research",
  "rld:mintTier": "research",
  "rld:schemaType": "ScholarlyArticle",
  "rld:immutable": true,
  "rld:immutableNote": "This anchor is immutable after mint. Amendment or re-mint produces a new helix position. The prior record is preserved in rld:crawlRecord. Constitutional Law II: the timestamp is the record.",
  "rld:manifest": {
    "bs:entityClass": "research",
    "bs:mintTier": "research",
    "bs:schemaType": "ScholarlyArticle",
    "bs:hasBody": true,
    "bs:hasRegulatory": false,
    "bs:hasResearch": true,
    "bs:hasDomain": false,
    "bs:hasSupplyChain": false,
    "bs:hasEnforcementDate": false,
    "bs:hasPenaltyProvision": false,
    "bs:hasAuthors": false,
    "bs:hasDoi": false,
    "bs:jurisdiction": "global",
    "bs:corpusSlug": "research",
    "bs:charCount": 20813,
    "bs:pageCount": 7,
    "rld:toc": {
      "rootLd": "https://boisestandard.org/ai/research/0704.2092/root-ld.json",
      "manifest": "https://boisestandard.org/ai/research/0704.2092/manifest.json",
      "indexRecord": "https://boisestandard.org/ai/research/0704.2092/index.json",
      "body": "https://boisestandard.org/ai/research/0704.2092/#root-ld-body",
      "anchor": "https://boisestandard.org/ai/research/0704.2092/#root-ld-anchor",
      "recursive": "https://boisestandard.org/ai/research/0704.2092/#root-ld-recursive",
      "regulatory": null,
      "research": "https://boisestandard.org/ai/research/0704.2092/#root-ld-body/research",
      "domain": null,
      "supplyChain": null
    }
  },
  "rld:linkPod": {
    "bsCanonicalUrl": "https://boisestandard.org/ai/research/0704.2092/",
    "rootLdUrl": "https://boisestandard.org/ai/research/0704.2092/root-ld.json",
    "manifestUrl": "https://boisestandard.org/ai/research/0704.2092/manifest.json",
    "indexJsonUrl": "https://boisestandard.org/ai/research/0704.2092/index.json",
    "sourceUrl": "https://arxiv.org/abs/0704.2092",
    "corpusUrl": "https://boisestandard.org/corpus/research/",
    "vocabUrl": "https://boisestandard.org/vocab#"
  }
}

LAYER 2 — BODY · FROZEN AT MINT · COMPLETE MEASUREMENT SNAPSHOT · 21K CHARS

{
  "@type": "rld:Body",
  "@id": "https://boisestandard.org/ai/research/0704.2092/#root-ld-body",
  "rld:frozenAt": "2026-06-29T22:03:25.711837+00:00",
  "rld:bodyType": "research_corpus",
  "bs:identity": {
    "@id": "https://boisestandard.org/ai/research/0704.2092/#root-ld-body/identity",
    "title": "A Note on the Inapproximability of Correlation Clustering",
    "slug": "",
    "entityClass": "research",
    "corpusSlug": "research",
    "bsCanonicalUrl": "https://boisestandard.org/ai/research/0704.2092/",
    "sourceUrl": "https://arxiv.org/abs/0704.2092"
  },
  "bs:research": {
    "@id": "https://boisestandard.org/ai/research/0704.2092/#root-ld-body/research",
    "doi": "",
    "arxivId": "0704.2092",
    "authors": [],
    "venue": "",
    "publicationDate": "",
    "researchCategories": [],
    "abstract": "",
    "citationCount": 0,
    "openAccess": false,
    "license": "",
    "note": "Research corpus record. Every field traces to the source. arXiv API or Semantic Scholar as primary source. Constitutional Law I."
  },
  "bs:provenance": {
    "@id": "https://boisestandard.org/ai/research/0704.2092/#root-ld-body/provenance",
    "sourceUrl": "https://arxiv.org/abs/0704.2092",
    "collectionMethod": "api",
    "collectionDate": "2026-06-29T22:01:19.292466+00:00",
    "contentHash": "19151a55d248290024302d5b49c79722df302cbc371afc209d599bdc1b78bf22",
    "pipelineVersion": "BST-PIPELINE-1.0.0",
    "mintedAt": "2026-06-29T22:03:25.711837+00:00"
  },
  "bs:textSummary": {
    "charCount": 20813,
    "fullBodyUrl": null,
    "excerpt": "##PAGE:1##\n9002\nraM\n32\n]GL.sc[\n2v2902.4070:viXra\nA Note on the Inapproximability of Correlation Clustering\n∗\nJinsong Tan\nAbstract\nWe consider inapproximability of the correlation clustering problem defined as follows: Given\na graph G = (V,E) where each edge is labeled either ”+” (similar) or ”−” (dissimilar), correla-\ntion clustering seeks to partition the vertices into clusters so that the number of pairs correctly\n(resp. incorrectly) classified with respect to the labels is maximized (resp. mi…"
  }
}

LAYER 3 — RECURSIVE · EMPTY AT MINT · GROWS THROUGH CORPUS PASSES · LAW VII TORUS

{
  "@type": "rld:Recursive",
  "@id": "https://boisestandard.org/ai/research/0704.2092/#root-ld-recursive",
  "rld:edgeCount": 0,
  "rld:edges": [],
  "rld:appendedAt": [],
  "rld:pendingSlots": [
    {
      "rld:slot": "related_entities",
      "rld:status": "pending",
      "rld:pass": "Bidirectional Corpus Pass",
      "rld:note": "BS entities with semantic connections to this record"
    },
    {
      "rld:slot": "law_corpus",
      "rld:status": "pending",
      "rld:pass": "Bidirectional Corpus Pass",
      "rld:note": "USC titles, CFR sections, EU AI Act, Idaho law governing this entity"
    },
    {
      "rld:slot": "research_corpus",
      "rld:status": "pending",
      "rld:pass": "Research Corpus Pass",
      "rld:note": "arXiv papers, Semantic Scholar records referencing this entity"
    },
    {
      "rld:slot": "supply_chain",
      "rld:status": "pending",
      "rld:pass": "Supply Chain Corpus Pass",
      "rld:note": "Supplier, manufacturer, distributor, retailer edges — the full chain"
    },
    {
      "rld:slot": "domain_entities",
      "rld:status": "pending",
      "rld:pass": "Domain Corpus Pass",
      "rld:note": "Web entities semantically connected to this record"
    }
  ],
  "rld:mintNote": "Recursive layer initialized at mint. Empty by design. Edges form through accumulated corpus passes. Law corpus, research corpus, domain graph, supply chain — every connection this entity has in the world accumulates here. The graph builds itself. Constitutional Law VII — Torus.",
  "rld:recursiveSpecUrl": "https://root-ld.org/spec/1.0/recursive",
  "rld:initializedAt": "2026-06-29T22:03:25.711837+00:00"
}