{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R328",
  "content_hash": null,
  "slug": "gmstg8-artifact-cycle-eight-certificate",
  "type": "artifact",
  "title": "Exact C8 tour and subtour-LP certificate",
  "summary": "Standard-library Python checks every tour and every cut of the cycle incidence vector; a one-line degree identity proves LP optimality.",
  "relevance": "For Largest subtour-LP gap among eight-vertex graph metrics, record gmstg8-artifact-cycle-eight-certificate (“Exact C8 tour and subtour-LP certificate”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python checks every tour and every cut of the cycle incidence vector; a one-line degree identity proves LP optimality.",
  "relevance_source": "recorded",
  "body": "Every nonzero distance in the \\(C_8\\) metric is at least one. Summing the eight subtour-LP degree equations gives\n\\[\n2\\sum_e x_e=16,\n\\]\nso every feasible LP solution has \\(\\sum_e x_e=8\\) and objective value at least 8. The incidence vector of the cycle is feasible and costs 8. It is therefore an optimal LP solution.\n\nThe program checks all \\(7!/2=2{,}520\\) unoriented tours and finds tour optimum 8. It also checks the degree equations and all 254 proper nonempty cuts for the cycle vector. The canonical report has SHA-256 digest `711b63f56d7591266ddd566d29632e6fd92bf785857c05022f193250b135fbd1`.",
  "status": "available",
  "evidence_grade": "executable",
  "scope": {
    "kind": "bounded",
    "statement": "the shortest-path metric of the eight-cycle C8",
    "bounds": {
      "vertices": {
        "min": 8,
        "max": 8
      },
      "unoriented_tours": {
        "min": 2520,
        "max": 2520
      },
      "proper_nonempty_cuts_checked": {
        "min": 254,
        "max": 254
      }
    },
    "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://arxiv.org/abs/2105.10043",
      "locator": "Self-contained Python 3 certificate executed on 2026-07-25"
    },
    "inline_source": [
      "from hashlib import sha256",
      "from itertools import permutations",
      "from json import dumps",
      "n=8",
      "edges=[(i,j) for i in range(n) for j in range(i+1,n)]",
      "d=[[min((i-j)%n,(j-i)%n) for j in range(n)] for i in range(n)]",
      "best=99",
      "best_tours=[]",
      "for tail in permutations(range(1,n)):",
      "    if tail[0]>tail[-1]:",
      "        continue",
      "    order=(0,)+tail",
      "    cost=sum(d[order[i]][order[(i+1)%n]] for i in range(n))",
      "    if cost<best:",
      "        best=cost; best_tours=[order]",
      "    elif cost==best:",
      "        best_tours.append(order)",
      "x={tuple(sorted((i,(i+1)%n))):1 for i in range(n)}",
      "degrees=[sum(value for edge,value in x.items() if v in edge) for v in range(n)]",
      "cut_values=[]",
      "for mask in range(1,(1<<n)-1):",
      "    cut_values.append(sum(value for (u,v),value in x.items() if ((mask>>u)&1)!=((mask>>v)&1)))",
      "assert best==8 and len(best_tours)==1",
      "assert degrees==[2]*n and min(cut_values)>=2",
      "assert sum(x.values())==8",
      "assert min(d[i][j] for i,j in edges)==1",
      "report={'graph':'C8','vertices':8,'metric_edge_minimum':1,'unoriented_tours_checked':2520,'tour_optimum':best,'optimal_tours':len(best_tours),'lp_degree_sum_identity':8,'cycle_vector_cost':sum(d[u][v]*value for (u,v),value in x.items()),'cycle_vector_minimum_cut':min(cut_values),'ratio':'1'}",
      "payload=dumps(report,sort_keys=True,separators=(',',':'))",
      "assert sha256(payload.encode()).hexdigest()=='711b63f56d7591266ddd566d29632e6fd92bf785857c05022f193250b135fbd1'",
      "print(payload)",
      "print('report_sha256='+sha256(payload.encode()).hexdigest())"
    ],
    "missing": [
      "command",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/2105.10043",
    "locator": "Self-contained Python 3 certificate executed on 2026-07-25"
  },
  "relations": [
    {
      "slug": "R331",
      "title": "The certified interval is 1 to slightly below 3/2",
      "object_type": "claim",
      "relation": "verifies",
      "direction": "outgoing"
    },
    {
      "slug": "graph-metric-subtour-gap-eight",
      "title": "graph metric subtour gap eight",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}