Seeded search for minimum-atom MIS → KingsSubgraph mapping

[isPANN]

Context

#1061 fixed non-determinism in pred reduce for MIS → KingsSubgraph by seeding the greedy path-decomposition RNG (DEFAULT_PATHWIDTH_SEED = 0). The mapping is now reproducible but not minimum-atom-count.

What the data shows

Sweep of 30 seeds on a 64-vertex, 146-edge MIS instance (same shape as the #1061 reporter's case), release build:

Smallest 5 mappings (by atoms):
  seed=16  pathwidth=14  atoms=5855
  seed= 6  pathwidth=14  atoms=5869
  seed=14  pathwidth=14  atoms=5892
  ...
Default (seed=0):         atoms=6236
Largest (seed=20):        atoms=6956

Spread: max/min = 1.188 (~19% variance)

Two observations:

1. Default seed=0 sits mid-pack — roughly 6% larger than the best of 30 seeds.
2. Mappings with identical pathwidth=14 span 5855..6956 atoms. Inside pathwidth, the 10 restarts already pick minimum vsep — but minimum vsep ≠ minimum atoms because crossing-gadget counts depend on the specific vertex ordering, not just pathwidth.

So finding the minimum mapping requires sampling at the full-mapping level, not just at pathwidth.

Cost of the sweep is cheap: 30 seeds ran in ~1.8s for this instance in --release.

Proposed direction

Add an opt-in library function:

// src/rules/unitdiskmapping/ksg/mapping.rs
pub fn map_unweighted_min_atoms(
    num_vertices: usize,
    edges: &[(usize, usize)],
    num_seeds: u32,
) -> MappingResult<KsgTapeEntry>;

// (and analogous map_weighted_min_atoms, triangular variants)

Internally: loop 0..num_seeds, pass each as seed to pathwidth_with_seed, run the full mapping, pick the result with smallest positions.len().

Explicit non-goals

• Do not touch reduce_to — it should remain a pure deterministic function. Embedding a "try K seeds" policy inside reduce_to (e.g. via an env var or thread-local) couples reduction semantics to invisible global state and makes tests fragile.
• No CLI flag on pred reduce in this issue — adding --num-seeds would require plumbing an optimization hyperparameter through ReduceTo::reduce_to(&self), which has no room for it today. That's a larger architectural discussion best handled separately.

Who needs this

• Benchmark workflows (miso-bench, neutral-atom platforms) where 6–19% fewer atoms translates into meaningful wall-clock savings downstream.
• Research workflows that compare solvers on "the best mapping we can find" rather than "a specific mapping".

Consumers that only need reproducibility are already served by #1061's fix.

Open questions

• Default value for num_seeds if we ever wire a higher-level entry point (10? 30? configurable?).
• Whether the ranking key should be strictly num_atoms, or a tuple (num_atoms, num_edges) to also minimize edge count as a tiebreak.
• Whether to expose similar helpers for triangular::map_weighted in the same issue or separately.

Related: #1061.