Pith Number

pith:MLJM6BMX

pith:2026:MLJM6BMX43ZRUG73UH4F5N46FF

not attested not anchored not stored refs resolved

On the Complexity of the Minimum-($k,\rho$)-Shortcut Problem

Alexander Leonhardt, Conrad Schecker, Julian Christoph Brinkmann, Tatiana Rocha Avila

The minimum (k,ρ)-shortcut problem is NP-hard for k≥2 and ρ≥k+2 in both directed and undirected graphs.

arxiv:2605.13474 v1 · 2026-05-13 · 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{MLJM6BMX43ZRUG73UH4F5N46FF}

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 present a simpler and more direct reduction from the Hitting Set problem which establishes that min(k,ρ)-Shortcut is NP-hard for k≥2 and ρ≥k+2 in both directed and undirected graphs.

C2weakest assumption

The constructed reduction from Hitting Set instances to shortcut instances is polynomial-time computable and correctly preserves yes/no answers.

C3one line summary

The Minimum-(k,ρ)-Shortcut problem is NP-hard for k≥2 and ρ≥k+2 in directed and undirected graphs, while undirected graphs with ρ=k+1 are solvable in polynomial time.

References

19 extracted · 19 resolved · 0 Pith anchors

[1] 2003 , url = 2003

[2] 2024 , doi = 2024

[3] The Monadic Second-Order Logic of Graphs 1990 · doi:10.1016/0890-5401(90)90043-h

[4] 2003 , doi = 2003

[5] Berndt and Sun Kim and Alexandru Zaharescu , title = 2018

Receipt and verification

First computed	2026-05-18T02:44:41.508100Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

62d2cf0597e6f31a1bfba1f85eb79e296a718c9677abb9e81672ee70155bc37f

Aliases

arxiv: 2605.13474 · arxiv_version: 2605.13474v1 · doi: 10.48550/arxiv.2605.13474 · pith_short_12: MLJM6BMX43ZR · pith_short_16: MLJM6BMX43ZRUG73 · pith_short_8: MLJM6BMX

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/MLJM6BMX43ZRUG73UH4F5N46FF \
  | 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: 62d2cf0597e6f31a1bfba1f85eb79e296a718c9677abb9e81672ee70155bc37f

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "a8e7a092ec68f566e8856adc387f1be5034d7b184814c38db08151c6834f17fe",
    "cross_cats_sorted": [],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.CC",
    "submitted_at": "2026-05-13T12:59:40Z",
    "title_canon_sha256": "84f2e7a7c55a91845073b1320c0cd1f244d593cb5aae052bfcff9cf5bd4157c4"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.13474",
    "kind": "arxiv",
    "version": 1
  }
}