1/* Independent exhaustive zero-forcing search for P(n,k) by FIRST-FORCE2 * NORMALISATION (Stage 5 robustness check; written independently of3 * code/brute_force.c: different reduction principle, different closure4 * algorithm, different enumeration scheme).5 *6 * Principle (Lemma 3.5 argument, results/derivations.md): if S is a7 * zero-forcing set with |S| = s < 2n, some first force x -> y exists, so8 * x in S, y not in S, and the two other neighbours of x are in S. The9 * directed edges of P(n,k) fall into four orbits under the dihedral group10 * D_n (which acts by automorphisms), with representatives11 * u0 -> v0, u0 -> u1, v0 -> u0, v0 -> v_k.12 * Hence a zero-forcing s-set exists iff for one of the four representatives13 * (x,y) some s-set S with {x} u (N(x) \ {y}) subset S, y not in S, forces.14 * We therefore enumerate all (s-3)-subsets T of V \ (N[x]) and test15 * S = {x} u (N(x)\{y}) u T. Total work 4 * C(2n-4, s-3).16 *17 * Closure: counter/worklist algorithm (each black vertex keeps the number18 * of its white neighbours; a black vertex with count 1 is pushed and19 * performs its force), NOT the pass-based bitmask loop of brute_force.c.20 *21 * usage: ff_brute n k s [threads]22 * output: one line per representative and a total line; a witness is23 * printed for the first forcing set found (if any).24 */25#include <stdio.h>26#include <stdlib.h>27#include <string.h>28#include <pthread.h>29#include <stdint.h>3031static int n, k, N, s;32static int nbr[128][3]; /* neighbour lists */33static int rep_x[4], rep_y[4];3435static void build_graph(void) {36 N = 2 * n;37 for (int i = 0; i < n; i++) {38 int u = i, v = n + i;39 nbr[u][0] = (i + n - 1) % n; nbr[u][1] = (i + 1) % n; nbr[u][2] = v;40 nbr[v][0] = n + (i + n - k) % n; nbr[v][1] = n + (i + k) % n; nbr[v][2] = u;41 }42 /* sanity: simple cubic graph, symmetric adjacency */43 for (int w = 0; w < N; w++) {44 for (int a = 0; a < 3; a++) {45 int t = nbr[w][a];46 if (t == w) { fprintf(stderr, "loop at %d\n", w); exit(3); }47 for (int b = 0; b < a; b++) if (nbr[w][b] == t) { fprintf(stderr, "multi-edge at %d\n", w); exit(3); }48 int back = 0; for (int b = 0; b < 3; b++) if (nbr[t][b] == w) back = 1;49 if (!back) { fprintf(stderr, "asymmetric adjacency %d %d\n", w, t); exit(3); }50 }51 }52 rep_x[0] = 0; rep_y[0] = n; /* u0 -> v0 */53 rep_x[1] = 0; rep_y[1] = 1; /* u0 -> u1 */54 rep_x[2] = n; rep_y[2] = 0; /* v0 -> u0 */55 rep_x[3] = n; rep_y[3] = n + k; /* v0 -> v_k */56}5758/* returns 1 iff the closure of the set given by black[] is V */59static int forces_all(unsigned char *black) {60 int cnt[128], queue[128], qh = 0, qt = 0, nblack = 0;61 for (int w = 0; w < N; w++) if (black[w]) nblack++;62 for (int w = 0; w < N; w++) {63 if (!black[w]) continue;64 int c = 0;65 for (int a = 0; a < 3; a++) if (!black[nbr[w][a]]) c++;66 cnt[w] = c;67 if (c == 1) queue[qt++] = w;68 }69 while (qh < qt) {70 int b = queue[qh++];71 if (cnt[b] != 1) continue; /* stale entry */72 int y = -1;73 for (int a = 0; a < 3; a++) if (!black[nbr[b][a]]) { y = nbr[b][a]; break; }74 if (y < 0) continue;75 black[y] = 1; nblack++;76 if (nblack == N) return 1;77 /* y became black: update counters of y's black neighbours, and y's own counter */78 int cy = 0;79 for (int a = 0; a < 3; a++) {80 int t = nbr[y][a];81 if (black[t]) { cnt[t]--; if (cnt[t] == 1) queue[qt++] = t; }82 else cy++;83 }84 cnt[y] = cy;85 if (cy == 1) queue[qt++] = y;86 }87 return nblack == N;88}8990/* work items: (representative r, first element index) */91static int nthreads = 1;92static volatile long next_item = 0;93static pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;94static unsigned long long tot_enum[4], tot_forcing[4];95static int witness_found = 0; static unsigned char witness[128];9697typedef struct { int id; } targ;9899static void *worker(void *arg) {100 (void)arg;101 int free_list[128], nfree;102 int idx[128];103 unsigned char base[128], black[128];104 unsigned long long enumerated = 0, forcing = 0;105 for (;;) {106 pthread_mutex_lock(&mu); long item = next_item++; pthread_mutex_unlock(&mu);107 int r = (int)(item / N), first = (int)(item % N);108 if (r >= 4) break;109 int x = rep_x[r], y = rep_y[r];110 memset(base, 0, N);111 base[x] = 1; for (int a = 0; a < 3; a++) if (nbr[x][a] != y) base[nbr[x][a]] = 1;112 nfree = 0;113 for (int w = 0; w < N; w++) if (!base[w] && w != y) free_list[nfree++] = w;114 int t = s - 3;115 if (t < 0) continue;116 /* enumerate t-subsets of free_list whose smallest index is `first` */117 if (first >= nfree) continue;118 if (t == 0) { if (first != 0) continue; memcpy(black, base, N); enumerated++; if (forces_all(black)) { forcing++; pthread_mutex_lock(&mu); if (!witness_found) { witness_found = 1; memcpy(witness, base, N); } pthread_mutex_unlock(&mu); } continue; }119 if (nfree - first < t) continue;120 idx[0] = first; for (int i = 1; i < t; i++) idx[i] = first + i;121 for (;;) {122 memcpy(black, base, N);123 for (int i = 0; i < t; i++) black[free_list[idx[i]]] = 1;124 enumerated++;125 if (forces_all(black)) {126 forcing++;127 pthread_mutex_lock(&mu);128 if (!witness_found) { witness_found = 1; memcpy(witness, base, N); for (int i = 0; i < t; i++) witness[free_list[idx[i]]] = 1; }129 pthread_mutex_unlock(&mu);130 }131 /* next combination with idx[0] fixed */132 int i = t - 1;133 while (i >= 1 && idx[i] == nfree - t + i) i--;134 if (i < 1) break;135 idx[i]++;136 for (int j = i + 1; j < t; j++) idx[j] = idx[j - 1] + 1;137 }138 pthread_mutex_lock(&mu); tot_enum[r] += enumerated; tot_forcing[r] += forcing; pthread_mutex_unlock(&mu);139 enumerated = forcing = 0;140 }141 return NULL;142}143144int main(int argc, char **argv) {145 if (argc < 4) { fprintf(stderr, "usage: ff_brute n k s [threads]\n"); return 2; }146 n = atoi(argv[1]); k = atoi(argv[2]); s = atoi(argv[3]);147 nthreads = argc > 4 ? atoi(argv[4]) : 1;148 if (n > 64 || n < 2 * k + 1) { fprintf(stderr, "need 2k+1 <= n <= 64\n"); return 2; }149 build_graph();150 pthread_t th[64];151 for (int i = 0; i < nthreads; i++) pthread_create(&th[i], NULL, worker, NULL);152 for (int i = 0; i < nthreads; i++) pthread_join(th[i], NULL);153 const char *names[4] = {"u0->v0", "u0->u1", "v0->u0", "v0->vk"};154 unsigned long long E = 0, F = 0;155 for (int r = 0; r < 4; r++) { printf("n=%d k=%d s=%d rep=%s enumerated=%llu forcing=%llu\n", n, k, s, names[r], tot_enum[r], tot_forcing[r]); E += tot_enum[r]; F += tot_forcing[r]; }156 printf("n=%d k=%d s=%d TOTAL enumerated=%llu forcing=%llu", n, k, s, E, F);157 if (witness_found) { printf(" witness="); int first = 1; for (int w = 0; w < N; w++) if (witness[w]) { printf("%s%c%d", first ? "" : ",", w < n ? 'u' : 'v', w < n ? w : w - n); first = 0; } }158 printf("\n");159 return 0;160}161