Formal Computer Science / Computation

Kenton Labs / Computation

Graph algorithms

A path is a feasible witness; the minimum-distance claim must also exclude shorter paths.

The vocabulary.

These definitions state the objects and properties used by the dataset. The complete instance specification remains the authority for each result.

Directed edge
An ordered pair of vertices with a nonnegative weight.
Simple path
A path visiting no vertex twice.
Distance
The sum of the weights along a path.

How the dataset works.

Three deterministic instances define this family. Each includes its input model, a checked result, evidence, and an acceptance procedure. Download the complete dataset JSON ↘ or the area’s readable source ↘.

Acceptance procedure

  1. Enumerate every simple source-to-target path in the small graph.
  2. Compute the total weight of each path.
  3. Find the minimum and accept any witness attaining it.
  4. Check the witness edge sequence and objective.

Cost and scope

Simple-path enumeration can be exponential; nonnegative weights ensure a shortest path can be chosen simple.

A common failure

A locally cheapest outgoing edge need not belong to a globally shortest path.

Explore the mechanics.

Change a local input or follow the steps. The stored result and its scope remain attached to the downloadable record.

Worked records.

Three instances expose concrete claims and the artifacts that establish or refute them. Expand a record for the problem, checker reasoning, formal payload, and verification metadata.

KL-FCS-028
Graph algorithmsA shortest path through an intermediate nodeComplete simple-path enumeration

The problem

Find the minimum weighted directed path from vertex 0 to vertex 3.

The checked result

Minimum distance: 5.

The supplied sequence is a valid path. Every alternative simple path is scored, so equal-cost optima are accepted and longer alternatives are ruled out.

Why the checker accepts it

  1. Enumerate every simple source-to-target path in the small graph.
  2. Compute the total weight of each path.
  3. Find the minimum and accept any witness attaining it.
  4. Check the witness edge sequence and objective.

Formal specification

{
  "vertices": 4,
  "edges": [
    [
      0,
      1,
      2
    ],
    [
      0,
      2,
      5
    ],
    [
      1,
      2,
      1
    ],
    [
      1,
      3,
      6
    ],
    [
      2,
      3,
      2
    ]
  ],
  "start": 0,
  "target": 3
}

Claim and evidence

{
  "claim": {
    "minimum_distance": 5
  },
  "witness": {
    "path": [
      0,
      1,
      2,
      3
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 3 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

Simple-path enumeration can be exponential; nonnegative weights ensure a shortest path can be chosen simple.

Weights are nonnegative. Negative cycles and unreachable targets require distinct result types.

A boundary to investigate

A locally cheapest outgoing edge need not belong to a globally shortest path. Replace enumeration with distance-label certificates and add max-flow/min-cut records.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-029 ↘Related KL-FCS-030 ↘
KL-FCS-029
Graph algorithmsTwo equally short pathsComplete simple-path enumeration

The problem

Find the minimum weighted directed path from vertex 0 to vertex 3.

The checked result

Minimum distance: 3.

The supplied sequence is a valid path. Every alternative simple path is scored, so equal-cost optima are accepted and longer alternatives are ruled out.

Why the checker accepts it

  1. Enumerate every simple source-to-target path in the small graph.
  2. Compute the total weight of each path.
  3. Find the minimum and accept any witness attaining it.
  4. Check the witness edge sequence and objective.

Formal specification

{
  "vertices": 4,
  "edges": [
    [
      0,
      1,
      1
    ],
    [
      0,
      2,
      1
    ],
    [
      1,
      3,
      2
    ],
    [
      2,
      3,
      2
    ]
  ],
  "start": 0,
  "target": 3
}

Claim and evidence

{
  "claim": {
    "minimum_distance": 3
  },
  "witness": {
    "path": [
      0,
      2,
      3
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 2 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

Simple-path enumeration can be exponential; nonnegative weights ensure a shortest path can be chosen simple.

Weights are nonnegative. Negative cycles and unreachable targets require distinct result types.

A boundary to investigate

A locally cheapest outgoing edge need not belong to a globally shortest path. Replace enumeration with distance-label certificates and add max-flow/min-cut records.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-028 ↘Related KL-FCS-030 ↘
KL-FCS-030
Graph algorithmsZero-weight edges without negative cyclesComplete simple-path enumeration

The problem

Find the minimum weighted directed path from vertex 0 to vertex 3.

The checked result

Minimum distance: 1.

The supplied sequence is a valid path. Every alternative simple path is scored, so equal-cost optima are accepted and longer alternatives are ruled out.

Why the checker accepts it

  1. Enumerate every simple source-to-target path in the small graph.
  2. Compute the total weight of each path.
  3. Find the minimum and accept any witness attaining it.
  4. Check the witness edge sequence and objective.

Formal specification

{
  "vertices": 4,
  "edges": [
    [
      0,
      1,
      0
    ],
    [
      1,
      2,
      0
    ],
    [
      0,
      2,
      4
    ],
    [
      2,
      3,
      1
    ],
    [
      1,
      3,
      3
    ]
  ],
  "start": 0,
  "target": 3
}

Claim and evidence

{
  "claim": {
    "minimum_distance": 1
  },
  "witness": {
    "path": [
      0,
      1,
      2,
      3
    ]
  }
}

Dataset construction

Deterministic finite fixture; full enumeration or witness replay as stated. Structured JSON; field meanings are stated in the specification. Acceptance covers 3 checker units for this record; the unit type is stated in its verification scope.

Complexity and limits

Simple-path enumeration can be exponential; nonnegative weights ensure a shortest path can be chosen simple.

Weights are nonnegative. Negative cycles and unreachable targets require distinct result types.

A boundary to investigate

A locally cheapest outgoing edge need not belong to a globally shortest path. Replace enumeration with distance-label certificates and add max-flow/min-cut records.

Verification and provenance metadata

Mechanical status: checked. Human review: not yet recorded. Checker version 1.0.0, Python 3.9.6. The report contains source hashes. The trust boundary includes Python and the custom checker implementations; no proof-assistant validation is claimed.

Original Kenton Labs reference instance, authored with Codex assistance on 2026-10-11. No external dataset import or model-generation evaluation. Reuse-license selection remains pending.

Replay from the source bundle: python3 tools/verify.py.

Readable source ↘Record JSON ↘Full area ↗Related KL-FCS-028 ↘Related KL-FCS-029 ↘

Go further.

Replace enumeration with distance-label certificates and add max-flow/min-cut records.

Questions to investigate

  1. A locally cheapest outgoing edge need not belong to a globally shortest path.
  2. Which assumption in the specification can be changed to make the current evidence insufficient?
  3. Replace enumeration with distance-label certificates and add max-flow/min-cut records.

Conceptual references

These sources explain the surrounding theory. The linked material was not imported as a dataset, and these records do not claim checking by the source’s software.

Primary conceptual reference ↗

Related areas

AlgorithmsGame theoryRelational algebra