# Scale Reduction Techniques for Computing Maximum Induced Bicliques
## 4 Computational Experiments
This was also the case with two other instances, \"oregon2-010526\" and \"as-22 july06\" for the MEB problem. All other instances of both MB and MEB problems were solved to optimality, and in all but four cases the MB problem was solved faster than the MEB problem. This is not surprising, since the residual graph is always at least as large for MEB as it is for MB, and the IP formulation for MEB has more variables and constraints. The CPU times taken by the scale reduction and IP steps of the exact approaches are illustrated in Figure 3 for 16 instances for which at least one of the four times (scale reduction for MB (MB-SR), \begin{table}
\begin{tabular}{c c c c c c c c c} \hline
**Graph** & \(|\boldsymbol{V}|\) & \(|E|\) & **LB** & \(|\boldsymbol{V^{\prime}}|\) & \(|\boldsymbol{E^{\prime}}|\) & **SR-CPU(s)** & **Opt. Obj.** & **CPU (s)** \\ \hline jazz & 198 & 2742 & 17 & 85 & 704 & 0.67 & 19 & 2.67 \\ email & 1133 & 5451 & 33 & 35 & 35 & 1.42 & 33 & 1.45 \\ netscience & 1589 & 2742 & 15 & 26 & 42 & 0.01 & 15 & 0.03 \\ add20 & 2395 & 7462 & 29 & 68 & 186 & 306.95 & 29 & 307.45 \\ data & 2851 & 15,093 & 7 & 1944 & 11,290 & 0.78 & - & \(>\)11,000 \\ as19971108 & 3015 & 5347 & 539 & 583 & 740 & 1430.57 & 539 & 1462.28 \\ add32 & 4960 & 9462 & 15 & 66 & 108 & 0.17 & 15 & 0.89 \\ CA-GrQC & 5242 & 14,490 & 28 & 35 & 41 & 0.47 & 28 & 0.51 \\ as19991204 & 6296 & 12,830 & 1293 & 1407 & 2234 & 2081.83 & 1293 & 9542.64 \\ p2p-Gnutella08 & 6301 & 20,777 & 87 & 448 & 3194 & 9.19 & 87 & 8177.89 \\ as20000102 & 6474 & 13,233 & 1337 & 1454 & 2430 & 1201.03 & 1339 & 10,044.40 \\ p2p-Gnutella09 & 8114 & 26,013 & 97 & 98 & 97 & 12.37 & 97 & 12.51 \\ hep-th & 8361 & 15,751 & 21 & 81 & 151 & 0.50 & 22 & 1.26 \\ p2p-Gnutella06 & 8717 & 31,525 & 103 & 305 & 1283 & 2.53 & 138 & 654.47 \\ p2p-Gnutella05 & 8846 & 31,839 & 86 & 136 & 203 & 5.74 & 92 & 8.38 \\ CA-HepTH & 9877 & 25,973 & 31 & 43 & 59 & 6.19 & 31 & 6.51 \\ GPPgiantcompo & 10,680 & 24,316 & 104 & 114 & 122 & 3899.91 & 104 & 3900.27 \\ p2p-Gnutella04 & 10,876 & 39,994 & 96 & 100 & 102 & 0.56 & 96 & 0.78 \\ oregon1-010519 & 11,051 & 22,724 & 2202 & 2384 & 4289 & 1262.38 & 2206 & 10,494.20 \\ oregon1-010526 & 11,174 & 23,409 & 2198 & 2385 & 4308 & 1415.75 & 2202 & 10,750.50 \\ oregon2-010526 & 11,460 & 16,365 & 2229 & 4228 & 4676 & 1579.16 & - & \(>\)11,000 \\ cond-mat & 16,726 & 47,594 & 40 & 55 & 72 & 7703.95 & 40 & 7704.02 \\ p2p-Gnutella25 & 22,687 & 54,705 & 63 & 66 & 67 & 0.31 & 63 & 0.44 \\ as-22 july06 & 22,963 & 48,436 & 2242 & 2387 & 4125 & 3735.30 & - & \(>\)11,000 \\ p2p-Gnutella24 & 26,518 & 65,369 & 303 & 356 & 426 & 220.50 & 303 & 225.52 \\ p2p-Gnutella30 & 36,682 & 88,328 & 53 & 54 & 53 & 2.06 & 53 & 2.12 \\ p2p-Gnutella31 & 62,586 & 147,892 & 89 & 95 & 100 & 0.98 & 89 & 1.30 \\ delaunay-n14 & 16,384 & 49,122 & 8 & 26 & 39 & 5.57 & 8 & 5.70 \\ delaunay-n16 & 65,536 & 196,575 & 8 & 18 & 34 & 80.41 & 8 & 80.54 \\ delaunay-n17 & 131,072 & 393,176 & 8 & 67 & 123 & 315.68 & 9 & 316.55 \\ delaunay-n18 & 262,144 & 786,396 & 10 & 65 & 123 & 373.68 & 11 & 374.53 \\ delaunay-n19 & 524,288 & 1,572,823 & 10 & 54 & 92 & 1478.44 & 10 & 1479.16 \\ delaunay-n20 & 1,048,576 & 3,145,686 & 11 & 24 & 45 & 3044.67 & 12 & 3045.02 \\ \hline \end{tabular}
\end{table} 
Table 2: Computational results for the MEB problem on instances from DIMACS Clustering challenge and SNAP dataset. IP solution for MB (MB-IP), scale reduction for MEB (MEB-SR), or IP solution for MB (MEB-IP)) exceeded 500 s. It can be seen that for 7 of these instances MEB-IP takes the longest, while MB-IP is the most time-consuming step for 2 more instances. The scale reduction techniques dominate the CPU time taken for the remaining 7 instances. Not surprisingly, the construction heuristic yielded optimal solutions for both the MB and MEB problems for 5 of these 7 instances, and was just short of optimum by 1 unit in the remaining two cases. For all these cases, the scale reduction procedure outputs a small residual graph that is easily handled by CPLEX.