Pith Number

pith:ET4T66X6

pith:2025:ET4T66X6RLQRX3IAACMPGAJN3O

not attested not anchored not stored refs pending

Families of tractable problems with respect to vertex-interval-membership width and its generalisations

Jessica Enright, Kitty Meeks, Laura Larios-Jones, Samuel D. Hand

Meta-algorithms for vertex-interval-membership and tree-interval-membership widths prove fixed-parameter tractability for large families of temporal graph problems.

arxiv:2505.15699 v5 · 2025-05-21 · cs.DM · math.CO

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

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{ET4T66X6RLQRX3IAACMPGAJN3O}

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 provide meta-algorithms for both VIM and TIM width which can be used to prove fixed-parameter-tractability for large families of problems, bypassing the need to give involved dynamic programming arguments for every problem. We provide a characterisation of problems in FPT with respect to both parameters.

C2weakest assumption

That the temporal problems under consideration admit dynamic programming solutions whose state at each time step depends only on a bounded number of vertices or substructures whose size is controlled by the VIM or TIM width (as defined in the paper).

C3one line summary

Introduces TIM width generalizing VIM width and gives meta-algorithms that characterize FPT problems including temporal Hamiltonian path and dominating set.

Receipt and verification

First computed	2026-06-19T16:09:49.303880Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

24f93f7afe8ae11bed000098f3012ddbbb4948a1a8017aa66faa3b33c691fd43

Aliases

arxiv: 2505.15699 · arxiv_version: 2505.15699v5 · doi: 10.48550/arxiv.2505.15699 · pith_short_12: ET4T66X6RLQR · pith_short_16: ET4T66X6RLQRX3IA · pith_short_8: ET4T66X6

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/ET4T66X6RLQRX3IAACMPGAJN3O \
  | 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: 24f93f7afe8ae11bed000098f3012ddbbb4948a1a8017aa66faa3b33c691fd43

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "c6c7b90a4f2f68c3364c7dcdf20739ec5c87ac9593757bf42732e01d9717ebe9",
    "cross_cats_sorted": [
      "math.CO"
    ],
    "license": "http://creativecommons.org/licenses/by/4.0/",
    "primary_cat": "cs.DM",
    "submitted_at": "2025-05-21T16:12:39Z",
    "title_canon_sha256": "5fc0467f08dfa819b65791daa97f5ec5a4d15d6474303339c249e01b2cfcb424"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2505.15699",
    "kind": "arxiv",
    "version": 5
  }
}