{
  "schema": "theoremdb-agent-record-v1",
  "ref": "R353",
  "content_hash": null,
  "slug": "gtc-claim-search-heuristics",
  "type": "claim",
  "title": "Which search heuristic carries the exhaustive sweep",
  "summary": "A two-by-two ablation through n=13. Taking the largest free edge label first costs 120 times more search when removed. Sibling ordering pays only when that heuristic is absent.",
  "relevance": "For Graceful tree conjecture, record gtc-claim-search-heuristics (“Which search heuristic carries the exhaustive sweep”) records a bound, answer, status fact, or structural consequence. The record states: A two-by-two ablation through n=13.",
  "relevance_source": "recorded",
  "body": "Two heuristics, ablated in all four combinations over the same 2,288 trees through n=13, with a 2,000,000-node budget per tree.\n\nlargest edge label first + sibling ordering: 725,194 nodes (1.00x); largest edge label first only: 705,257 nodes (0.97x); sibling ordering only: 87,120,506 nodes (120.13x); neither: 138,479,279 nodes (190.95x).\n\nLargest free edge label first. Each step extends the labeling to one new vertex, which fixes one edge label. Ascending numeric order spends the small edge labels early and leaves the large ones, which only a few vertex pairs can produce, to be forced at the end. Removing this heuristic multiplies the search by 120.\n\nIsomorphic sibling ordering. A vertex with \\(k\\) leaf children has \\(k!\\) relabelings of one labeling. Forcing isomorphic siblings into increasing root-label order removes them, and is sound because swapping isomorphic siblings is an automorphism. Under the naive label order it is worth 1.6x, and it is what settles the one tree the bottom cell leaves inside its budget. Alongside the edge-label ordering it is worth 1.03x, which is inside the noise: pruning duplicate labelings also reorders the traversal, and a search that stops at the first solution can lose as much as it gains.\n\nThe practical reading: implement the value ordering first. Keep the sibling constraint for exhaustive enumeration, where the duplicate branches are all walked and the pruning is unambiguous.\n\nReproduce with --no-edge-order, --no-symmetry, or both.",
  "status": "reproduced",
  "evidence_grade": "reproduced",
  "scope": {
    "kind": "bounded",
    "statement": "every tree on at most 13 vertices",
    "bounds": {
      "n": {
        "max": 13
      }
    },
    "exhaustive": true
  },
  "reproduction": {
    "schema": "theoremdb-reproduction-v1",
    "readiness": "source_only",
    "kind": "claim",
    "citation": {
      "url": "https://arxiv.org/abs/1403.1564",
      "locator": "research/graceful-trees/checks.py --max-n 13 --skip-alpha [--no-edge-order] [--no-symmetry]"
    },
    "missing": [
      "source",
      "command",
      "runtime",
      "expected_output"
    ]
  },
  "formal_statement": null,
  "source": {
    "url": "https://arxiv.org/abs/1403.1564",
    "locator": "research/graceful-trees/checks.py --max-n 13 --skip-alpha [--no-edge-order] [--no-symmetry]"
  },
  "models": [],
  "continuation": null,
  "relations": [
    {
      "slug": "R339",
      "title": "Exhaustive graceful and alpha-labeling checker",
      "object_type": "artifact",
      "relation": "informs",
      "direction": "outgoing"
    },
    {
      "slug": "graceful-tree-conjecture",
      "title": "graceful tree conjecture",
      "object_type": "problem",
      "relation": "recorded_for",
      "direction": "outgoing"
    }
  ]
}