Pith Number

pith:G634POW4

pith:2026:G634POW47PZEOK63M2BGPYJN2Q

not attested not anchored not stored refs resolved

The Gallai Vertex Problem is $\Theta_2^p$-Complete

Amir Nikabadi, Eva Rotenberg, Lasse Wulf

Deciding whether a graph has a vertex on all its longest paths is complete for the class Θ₂^p.

arxiv:2605.13488 v1 · 2026-05-13 · cs.DM

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

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{G634POW47PZEOK63M2BGPYJN2Q}

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 the Gallai Vertex Problem is complete for the complexity class Θ₂^p = P^{NP[log n]}.

C2weakest assumption

The polynomial-time reduction from a known Θ₂^p-complete problem to the Gallai vertex problem correctly preserves yes/no instances and runs in polynomial time.

C3one line summary

The Gallai vertex problem is Θ₂^p-complete.

References

55 extracted · 55 resolved · 0 Pith anchors

[1] Finding large 2021

[2] Finding large

[3] 2020 , issn = 2020 · doi:10.1016/j.dam.2019.03.022

[4] 2020 , doi = 2020

[5] 2022 , issn = 2022 · doi:10.1016/j.disc.2022.112985

Receipt and verification

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

Canonical hash

37b7c7badcfbf2472bdb668267e12dd43aff8edf668c08422b925836cf44aa27

Aliases

arxiv: 2605.13488 · arxiv_version: 2605.13488v1 · doi: 10.48550/arxiv.2605.13488 · pith_short_12: G634POW47PZE · pith_short_16: G634POW47PZEOK63 · pith_short_8: G634POW4

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/G634POW47PZEOK63M2BGPYJN2Q \
  | 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: 37b7c7badcfbf2472bdb668267e12dd43aff8edf668c08422b925836cf44aa27

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "6c7688fb922c890e740a42b5e873edbaf6d243bec4d8ff1c4383de0d0afc755a",
    "cross_cats_sorted": [],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "cs.DM",
    "submitted_at": "2026-05-13T13:14:10Z",
    "title_canon_sha256": "868a63ad156e82ae830183dd9b060f330076229d67d09759cc8de9bc1d642b1b"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.13488",
    "kind": "arxiv",
    "version": 1
  }
}