Improve Branching algorithm for path decomposition

[GiggleLiu]

The run tests faster.

[GiggleLiu]

Current Test Time Analysis

Total unitdiskmapping test time: ~12s (454 tests, multi-threaded).

Time breakdown by module

Module	Tests	Time
weighted	29	9.47s
map_graph	37	8.90s
triangular	21	5.18s
mapping_result	39	0.45s
gadgets (all)	182	0.16s
gadgets_ground_truth	112	0.06s
julia_comparison	12	0.04s
copyline	24	0.03s

The 3 slow modules each have a single mega-test (test_*_map_config_back_standard_graphs) that loops over 20 standard graphs — these dominate the runtime.

Bottleneck 1: Branch-and-bound pathdecomposition

map_graph() calls pathwidth(Auto) → branch_and_bound() for graphs ≤30 vertices.

Measured map_graph time per graph:

Graph	Vertices	Edges	Grid Vertices	Map Time
pappus	18	27	521	2.55s
dodecahedral	20	30	523	616ms
desargues	20	30	650	529ms
moebiuskantor	16	24	398	261ms
heawood	14	21	344	187ms
truncatedcube	24	36	565	186ms
chvatal	12	24	355	82ms
others (≤12v)	—	—	—	<40ms

Pappus (18v) alone takes 2.5s — more than truncatedcube (24v, 186ms). The pathwidth depends on graph structure, not just size.

Bottleneck 2: ILP solving (secondary)

Each test_*_standard_graphs test also calls solve_mis / solve_mis_config on both the original graph and the mapped grid (up to 650 vertices). The same original graph MIS is solved redundantly across the 3 test functions.

Algorithmic issues in pathdecomposition.rs

1. Adjacency list rebuilt on every function call — vsep_updated, vsep_updated_neighbors, extend, greedy_exact all rebuild adj: Vec<HashSet<usize>> from the edge list. In recursive branch-and-bound, this happens thousands of times.

2. Vertex sets rebuilt from Vec on every call — vertices_set: HashSet<usize> and neighbors_set: HashSet<usize> are reconstructed from Layout.neighbors: Vec<usize> on every invocation.

3. vsep_updated computed twice — In branch_and_bound_internal, line 363 computes it for sorting, then line 370 recomputes it in the loop filter.

4. vsep_and_neighbors is O(n²) — Rebuilds set S from scratch at every step instead of incremental maintenance.

5. Layout stores Vec instead of HashSet — neighbors and disconnected are Vec<usize> requiring O(n) contains/position, when HashSet gives O(1).

Potential improvements

Algorithmic (branch-and-bound):

1. Build adjacency list once, pass as parameter — eliminates thousands of redundant O(|E|) constructions. Biggest single win.
2. Use u64 bitmask for vertex sets — for graphs ≤64 vertices, all set operations (contains, insert, remove, union, intersection) become single CPU instructions. HashSet<usize> for 18-vertex graphs is heavy overhead.
3. Store vertices_set in Layout — avoid rebuilding from Vec on every access.
4. Cache vsep_updated results — avoid double computation in branch_and_bound_internal.

Threshold tuning:

5. Lower the Auto threshold from 30 — pappus (18v) takes 2.5s with exact branch-and-bound. Greedy with restarts may be good enough for graphs ≥14v, cutting the worst case from seconds to milliseconds.

Test structure:

6. Split mega-tests into per-graph tests — the test runner can parallelize them instead of running 20 graphs sequentially in one test.
7. Pre-compute expected MIS sizes as ground truth JSON — eliminates redundant ILP solving across the 3 test modules. Each test currently re-solves solve_mis(n, &edges) for the same 20 graphs.

Estimated impact

• Options 1+2 (adjacency once + bitmask): likely reduces pappus from 2.5s → <50ms
• Option 5 (lower threshold to 14): immediate relief, pappus drops to ~10ms (greedy), small quality loss
• Options 6+7 (test restructuring): better parallelism + eliminates redundant ILP calls