Pith Number

pith:2EFDMUXI

pith:2026:2EFDMUXIR3PCO67VJLALR6XG6G

not attested not anchored not stored refs pending

Maximum Matching and Related Problems in Catalytic Logspace

Amit Sinhababu, Aryan Kusre, Partha Mukhopadhyay, Samir Datta, Srijan Chakraborty

The size of a maximum matching in general graphs can be determined in catalytic logspace, and the matching itself can be constructed in CLP.

arxiv:2604.24275 v2 · 2026-04-27 · 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{2EFDMUXIR3PCO67VJLALR6XG6G}

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 that we can construct a maximum matching in general graphs in CL, and, in fact, in CLP. We first show that the size of a maximum matching in general graphs can be determined in CL.

C2weakest assumption

The linear-algebraic algorithm for maximum matching by Geelen (2000) and the PTAS for rank approximation can be implemented or simulated inside catalytic logspace without exceeding the space or catalytic restoration constraints.

C3one line summary

Maximum matching in general graphs and several related matroid problems are placed in catalytic logspace or CLP.

Receipt and verification

First computed	2026-06-02T02:04:18.041062Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

d10a3652e88ede277bf54ac0b8fae6f1b85e8b5980683783121f7ced57c5388f

Aliases

arxiv: 2604.24275 · arxiv_version: 2604.24275v2 · doi: 10.48550/arxiv.2604.24275 · pith_short_12: 2EFDMUXIR3PC · pith_short_16: 2EFDMUXIR3PCO67V · pith_short_8: 2EFDMUXI

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/2EFDMUXIR3PCO67VJLALR6XG6G \
  | 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: d10a3652e88ede277bf54ac0b8fae6f1b85e8b5980683783121f7ced57c5388f

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "11adfbe4b3c4beda3029f663c606e049962a73b9e5739d9d10488c0525adf56b",
    "cross_cats_sorted": [],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.CC",
    "submitted_at": "2026-04-27T10:09:42Z",
    "title_canon_sha256": "737b5a5eab12c85f6e7d1c0cecf88007f5e844f61e1a1eb0c1a097d98405a0ef"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2604.24275",
    "kind": "arxiv",
    "version": 2
  }
}