{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R329",
  "content_hash": null,
  "slug": "gmstg8-attempt-exact-sweep-plan",
  "type": "attempt",
  "title": "Exact isomorph-free sweep remains to be run",
  "summary": "The corpus is fixed and the certificate format is specified; no universal LP sweep is claimed in this version.",
  "relevance": "For Largest subtour-LP gap among eight-vertex graph metrics, record gmstg8-attempt-exact-sweep-plan (“Exact isomorph-free sweep remains to be run”) documents a concrete method, search boundary, or failed route. The record states: The corpus is fixed and the certificate format is specified; no universal LP sweep is claimed in this version.",
  "relevance_source": "recorded",
  "body": "For each graph6 record, the exact computation should perform these steps:\n\n1. Decode the graph and compute its 28 integer shortest-path distances.\n2. Enumerate the \\(7!/2=2{,}520\\) unoriented Hamilton cycles to obtain the exact tour value and a minimizing order.\n3. Solve the subtour LP with eight degree equations and one representative of each complementary pair of nontrivial cut inequalities. Preserve a rational primal optimum and a rational dual optimum.\n4. Verify both certificates with integer arithmetic after clearing denominators. Record every tied maximizer.\n5. Recompute each maximizing graph's canonical graph6 label with an independent nauty call.\n\nThe diameter-two cases can be pruned against the sourced \\(18/17\\) upper bound once an incumbent exceeds it. Bridges and articulation decompositions offer further reductions, though each reduction needs a proof for this exact degree-constrained metric LP.\n\nThis record stops before the 11,117 LP solves. It makes no claim that the cycle incumbent is optimal.",
  "status": "in_progress",
  "evidence_grade": "planned",
  "scope": {
    "kind": "bounded",
    "statement": "the unresolved exact optimization across all 11,117 connected graph isomorphism classes on eight vertices",
    "bounds": {
      "vertices": {
        "min": 8,
        "max": 8
      },
      "connected_unlabeled_graphs": {
        "min": 11117,
        "max": 11117
      },
      "complete_metric_edges": {
        "min": 28,
        "max": 28
      },
      "unoriented_tours_per_instance": {
        "min": 2520,
        "max": 2520
      }
    },
    "exhaustive": false
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "attempt",
    "citation": {
      "url": "https://arxiv.org/abs/2105.10043",
      "locator": "Finite computation plan prepared on 2026-07-25"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/2105.10043",
    "locator": "Finite computation plan prepared on 2026-07-25"
  },
  "models": [],
  "relations": [
    {
      "slug": "R332",
      "title": "Diameter-two graph metrics have gap at most 18/17",
      "object_type": "claim",
      "relation": "informs",
      "direction": "incoming"
    },
    {
      "slug": "R327",
      "title": "Isomorph-free connected graph corpus manifest",
      "object_type": "artifact",
      "relation": "supports",
      "direction": "incoming"
    },
    {
      "slug": "graph-metric-subtour-gap-eight",
      "title": "graph metric subtour gap eight",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}