{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R548",
  "content_hash": null,
  "slug": "nngm10-artifact-incumbent-exact-verifier",
  "type": "artifact",
  "title": "Exact verifier for the 18/11 graph",
  "summary": "Standard-library Python computes the graph metric, follows the label tie rule, and checks all 181,440 unoriented tours.",
  "relevance": "For Worst nearest-neighbor tour on a ten-vertex graph metric, record nngm10-artifact-incumbent-exact-verifier (“Exact verifier for the 18/11 graph”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python computes the graph metric, follows the label tie rule, and checks all 181,440 unoriented tours.",
  "relevance_source": "recorded",
  "body": "The program builds the graph directly from its fourteen edges and computes all-pairs distances by breadth-first search. It then applies the stated nearest-neighbor rule, including the smaller-label tie break.\n\nFor the optimum it fixes vertex 0, identifies a tour with its reversal, and checks the remaining \\(9!/2=181{,}440\\) orders. The nearest-neighbor length is 18 and the optimum is 11. There are four optimal unoriented tours. The canonical report has SHA-256 digest `a1d0820ab4475898cee1a7eea91a8e73cd82003b4031aea2dd1c8f2e84f93801`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "the displayed connected graph on vertices {0,...,9}, its deterministic nearest-neighbor tour, and all unoriented Hamiltonian tours in its shortest-path metric",
    "bounds": {
      "vertices": {
        "min": 10,
        "max": 10
      },
      "graph_edges": {
        "min": 14,
        "max": 14
      },
      "unoriented_tours_checked": {
        "min": 181440,
        "max": 181440
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "partial",
    "kind": "inline_python_computation",
    "entrypoint": "Join source_lines with newline characters and run with python3",
    "runtime": "CPython 3, standard library only",
    "citation": {
      "url": "https://doi.org/10.1137/0206041",
      "locator": "Self-contained Python 3 certificate executed on 2026-07-25"
    },
    "inline_source": [
      "from collections import deque",
      "from hashlib import sha256",
      "from itertools import permutations",
      "from json import dumps",
      "n=10",
      "edges=[(0,2),(0,3),(1,7),(1,8),(1,9),(2,3),(2,5),(2,6),(2,7),(4,5),(4,8),(5,6),(7,8),(8,9)]",
      "adj=[set() for _ in range(n)]",
      "for u,v in edges:",
      "    adj[u].add(v); adj[v].add(u)",
      "d=[]",
      "for s in range(n):",
      "    row=[n]*n; row[s]=0; q=deque([s])",
      "    while q:",
      "        u=q.popleft()",
      "        for v in adj[u]:",
      "            if row[v]==n:",
      "                row[v]=row[u]+1; q.append(v)",
      "    d.append(row)",
      "order=[0]",
      "unseen=set(range(1,n))",
      "while unseen:",
      "    u=order[-1]",
      "    v=min(unseen,key=lambda x:(d[u][x],x))",
      "    order.append(v); unseen.remove(v)",
      "nn=sum(d[order[i]][order[(i+1)%n]] for i in range(n))",
      "best=10**9; best_order=None; best_count=0",
      "for tail in permutations(range(1,n)):",
      "    if tail[0]>tail[-1]:",
      "        continue",
      "    tour=(0,)+tail",
      "    cost=sum(d[tour[i]][tour[(i+1)%n]] for i in range(n))",
      "    if cost<best:",
      "        best=cost; best_order=tour; best_count=1",
      "    elif cost==best:",
      "        best_count+=1",
      "assert order==[0,2,3,5,4,8,1,7,6,9]",
      "assert nn==18 and best==11",
      "edge_text=','.join(f'{u}{v}' for u,v in edges)",
      "metric_text='\\n'.join(','.join(map(str,row)) for row in d)+'\\n'",
      "report={'vertices':n,'edges':edge_text,'connected':all(x<n for row in d for x in row),'distance_matrix_sha256':sha256(metric_text.encode()).hexdigest(),'nearest_neighbor_order':order,'nearest_neighbor_leg_lengths':[d[order[i]][order[(i+1)%n]] for i in range(n)],'nearest_neighbor_length':nn,'unoriented_tours_checked':181440,'optimal_tour_length':best,'canonical_optimal_tour':best_order,'optimal_unoriented_tours':best_count,'ratio':'18/11'}",
      "payload=dumps(report,sort_keys=True,separators=(',',':'))",
      "assert sha256(payload.encode()).hexdigest()=='a1d0820ab4475898cee1a7eea91a8e73cd82003b4031aea2dd1c8f2e84f93801'",
      "print(payload)"
    ],
    "missing": [
      "command",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://doi.org/10.1137/0206041",
    "locator": "Self-contained Python 3 certificate executed on 2026-07-25"
  },
  "models": [],
  "relations": [
    {
      "slug": "R550",
      "title": "The certified ratio lies between 18/11 and 11/5",
      "object_type": "claim",
      "relation": "verifies",
      "direction": "outgoing"
    },
    {
      "slug": "nearest-neighbor-graph-metric-ten",
      "title": "nearest neighbor graph metric ten",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}