# Scale Reduction Techniques for Computing Maximum Induced Bicliques
## 4 Computational Experiments
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**Graph** & \(|V|\) & \(|E|\) & **LB** & \(|V^{\prime}|\) & \(|E^{\prime}|\) & **SR-CPU(s)** & **Opt. Obj.** & **CPU (s)** \\ \hline jazz & 198 & 2742 & 18 & 85 & 704 & 0.44 & 20 & 0.67 \\ email & 1133 & 5451 & 34 & 35 & 35 & 0.61 & 34 & 0.64 \\ netscience & 1589 & 2742 & 16 & 26 & 42 & 0.02 & 16 & 0.03 \\ add20 & 2395 & 7462 & 30 & 68 & 186 & 464.66 & 30 & 464.73 \\ data & 2851 & 15,093 & 8 & 41 & 99 & 1.09 & 8 & 1.36 \\ as19971108 & 3015 & 5347 & 540 & 583 & 740 & 1531.77 & 540 & 1602.59 \\ add32 & 4960 & 9462 & 16 & 66 & 108 & 0.17 & 16 & 0.42 \\ CA-GrQC & 5242 & 14,490 & 29 & 35 & 41 & 0.39 & 29 & 0.42 \\ as19991204 & 6296 & 12,830 & 1294 & 1407 & 2234 & 3461.69 & 1294 & 3582.89 \\ p2p-Gnutella08 & 6301 & 20,777 & 88 & 88 & 87 & 1.36 & 88 & 1.48 \\ as20000102 & 6474 & 13,233 & 1338 & 1454 & 2430 & 1440.82 & 1340 & 19,645.00 \\ p2p-Gnutella09 & 8114 & 26,013 & 98 & 98 & 97 & 1.09 & 98 & 1.47 \\ hep-th & 8361 & 15,751 & 22 & 81 & 151 & 0.40 & 23 & 0.66 \\ p2p-Gnutella06 & 8717 & 31,525 & 104 & 113 & 121 & 0.21 & 104 & 0.44 \\ p2p-Gnutella05 & 8846 & 31,839 & 87 & 88 & 88 & 0.76 & 87 & 1.11 \\ CA-HepTH & 9877 & 25,973 & 32 & 43 & 59 & 4.18 & 32 & 4.42 \\ PGPgiantcompo & 10,680 & 24,316 & 105 & 114 & 122 & 3223.57 & 105 & 3223.85 \\ p2p-Gnutella04 & 10,876 & 39,994 & 97 & 100 & 102 & 0.12 & 97 & 0.42 \\ oregon1-010519 & 11,051 & 22,724 & 2203 & 2384 & 4289 & 1466.45 & 2207 & 2085.01 \\ oregon1-010526 & 11,173 & 23,409 & 2199 & 2385 & 4308 & 1619.41 & 2203 & 3852.24 \\ oregon2-010526 & 11,460 & 16,365 & 2230 & 2428 & 4676 & 1652.65 & 2234 & 4762.25 \\ cond-mat & 16,726 & 47,594 & 41 & 55 & 72 & 5257.99 & 41 & 5258.05 \\ p2p-Gnutella25 & 22,687 & 54,705 & 64 & 66 & 67 & 0.22 & 64 & 0.33 \\ as-22 july06 & 22,963 & 48,436 & 2243 & 2387 & 4125 & 1678.23 & 2245 & 10,722.34 \\ p2p-Gnutella24 & 26,518 & 65,369 & 304 & 356 & 426 & 1040.93 & 304 & 1043.72 \\ p2p-Gnutella30 & 36,682 & 88,328 & 54 & 54 & 53 & 0.59 & 54 & 0.70 \\ p2p-Gnutella31 & 62,586 & 147,892 & 90 & 95 & 100 & 0.41 & 90 & 0.70 \\ delaunay-n14 & 16,384 & 49,122 & 9 & 26 & 39 & 4.15 & 9 & 4.23 \\ delaunay-n16 & 65,536 & 196,575 & 9 & 18 & 34 & 61.05 & 9 & 61.13 \\ delaunay-n17 & 131,072 & 393,176 & 9 & 67 & 123 & 243.29 & 10 & 244.00 \\ delaunay-n18 & 262,144 & 786,396 & 11 & 65 & 123 & 541.73 & 12 & 542.29 \\ delaunay-n19 & 524,288 & 1,572,823 & 11 & 54 & 92 & 2205.50 & 11 & 2206.09 \\ delaunay-n20 & 1,048,576 & 3,145,686 & 12 & 24 & 45 & 5086.75 & 13 & 5087.06 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Computational results for the MB problem on instances from DIMACS Clustering challenge and Stanford Large Network Dataset Collection (SNAP) dataset. Note that since the greedy induced star construction heuristic was used to find an initial solution for both the MB and MEB problems, the lower bound values always differ by 1 (for a star on \(k\) vertices, the corresponding lower bounds for MB and MEB objective values are \(k\) and \((k-1)\times 1=k-1\), respectively). Comparing the size of the original and residual graphs in each of the test cases shows that scale reduction technique is successful in shrinking the instance size, which is essential for applicability of the IP-based approach. Also, in all but four instances (\"data\", \"p2p-Gnutella08\", \"p2p-Gnutella06\", and \"p2p-Gnutella05\") the scale reduction process yielded the same residual graph for both problems. The most dramatic difference in effectiveness of the scale reduction process was observed for the \"data\" graph. In this case, the MB residual graph had only 41 vertices and 99 edges, while the MEB residual graph had 1944 vertices and 11,290 edges. As a result, we were not able to solve the MEB problem for this instance within the 11,000-s time limit (The 11,000-s time limit for the MEB problem was chosen based on the results obtained for the MB problem, for which all but one instances were solved in under 11,000 s, while one instance took over 19,000 s).