Pith Number

pith:DFDH3HQY

pith:2026:DFDH3HQYQWCKGLNS3QKXUEFHQ6

not attested not anchored not stored refs resolved

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs

Florent Foucaud, Lucas Lorieau, Morteza Mohammad-Noori, Narges Ghareghani, Prafullkumar Tale, Rasa Parvini Oskuei

Geodetic Set can be solved in polynomial time on ditrees.

arxiv:2603.23193 v3 · 2026-03-24 · cs.DS · 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{DFDH3HQYQWCKGLNS3QKXUEFHQ6}

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

GEODETIC SET admits a polynomial-time algorithm on ditrees, that is, digraphs with possible 2-cycles when the underlying undirected graph is a tree (after deleting possible parallel edges).

C2weakest assumption

The input digraphs satisfy the structural properties like being ditrees or having bounded feedback edge set, and the algorithms correctly compute shortest paths in these structures without hidden exponential factors.

C3one line summary

Geodetic Set can be solved in polynomial time on ditrees and in FPT time parameterized by feedback edge set on 2-cycle-free digraphs, but is NP-hard on DAGs with constant feedback vertex set and pathwidth.

References

30 extracted · 30 resolved · 0 Pith anchors

[1] Discrete Mathematics345(10), 112985 (2022) 2022

[2] Discrete Applied Mathematics323, 14–27 (2022) 2022

[3] Bergougnoux, B., Defrain, O., Mc Inerney, F.: Enumerating minimal solution sets for metric graph problems. In: Proc. of the 50th Inter- national Workshop on Graph-Theoretic Concepts in Computer Scienc 2024

[4] In: 31st International Symposium on Algorithms and Compu- tation (ISAAC 2020) 2020

[5] In: Proceedings of the 6th International Conference on Algo- rithms and Discrete Applied Mathematics (CALDAM 2020) 2020

Receipt and verification

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

Canonical hash

19467d9e188584a32db2dc157a10a787b5f545f37a1b389a94848e3932e88aa2

Aliases

arxiv: 2603.23193 · arxiv_version: 2603.23193v3 · doi: 10.48550/arxiv.2603.23193 · pith_short_12: DFDH3HQYQWCK · pith_short_16: DFDH3HQYQWCKGLNS · pith_short_8: DFDH3HQY

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/DFDH3HQYQWCKGLNS3QKXUEFHQ6 \
  | 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: 19467d9e188584a32db2dc157a10a787b5f545f37a1b389a94848e3932e88aa2

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "ab5c1e2e6bc99cb4381e893c438d9c0f7bb7acb297a1d45bf250987bfa93566d",
    "cross_cats_sorted": [
      "cs.DM"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.DS",
    "submitted_at": "2026-03-24T13:41:12Z",
    "title_canon_sha256": "b3b77f6c3fcb69c7a27b2be5ca96099fa47725fdbdfc8356995ebcb1bbe416fc"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2603.23193",
    "kind": "arxiv",
    "version": 3
  }
}