# On the Complexity of the Bipartite Polarization Problem:
## 7 Experimental Results
The right plot shows the median bipartite polarization of the instances, and we can see that its behavior is very similar to the one of the previous experiment. So, these results confirm that even increasing the vertex degree, the typical complexity of solving the instances seems to be tightly correlated with the value of \(\alpha\), such that the exponential time increase seems more clear for low values of \(\alpha\) (\(\alpha\leq 0.4\)), but not for higher values that show a much slow increase in the typical complexity. Finally, we were also interested in comparing the quality of the approximation provided by the local search approach, presented in Section 4, with the one of the exact algorithm. Table 1 shows, for each combination of number of nodes and value of \(\alpha\), the minimum, median and maximum value for the polarization obtained in each set of instances with the exact algorithm (columns labeled with _SCIP BigPol_). Observe that for higher values of \(\alpha\), we observe more variations in the polarization of the instances (difference between the min and the max values). Then, in the next three columns we show for the same three instances of the previous columns (instance with minimum polarization, with median one, and with maximum one) the ratio of the approximate polarization computed by the local search solver to the exact polarization of the instance (LS ratio). As we observe, the quality of the solutions computed by the local search algorithm is perfect for instances with \(\alpha\geq 0.4\) (that are precisely the ones that are easily solved by the exact algorithm) and for lower  
Figure 2: Number of nodes of the SCIP search tree needed to solve the instances as we increase the alpha value for instances with nodes ranging from 25 to 40.  
values of \(\alpha\) we observe only a tiny relative error. Overall, we can say that the quality of the solution provided by the local search algorithm is always satisfactory with the advantage that its computational complexity is always linear with respect to the number of nodes, so there is no hard region for the local search approach. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline  & & & \multicolumn{2}{c}{**SCIP BigPol**} & & \multicolumn{2}{c}{**LS Ratio**} \\ \(m\) & \(\alpha\) & **Min.** & **Median** & **Max.** & **Min.** & **Median** & **Max.** \\ \hline  & 0.05 & 0.0001 & 0.0003 & 0.0005 & 1 & 0.998 & 1 \\  & 0.08 & 0.0004 & 0.0008 & 0.0013 & 1 & 0.9995 & 0.9999 \\  & 0.11 & 0.0007 & 0.0015 & 0.0025 & 1 & 0.9998 & 1 \\
25 & 0.14 & 0.0013 & 0.0025 & 0.0042 & 1 & 1 & 0.9999 \\  & 0.4 & 0.0359 & 0.0497 & 0.0611 & 1 & 1 & 1 \\  & 0.7 & 0.1907 & 0.2487 & 0.2786 & 1 & 1 & 1 \\  & 1.0 & 0.4834 & 0.6631 & 0.7446 & 1 & 1 & 1 \\ \hline  & 0.05 & 0.0002 & 0.0003 & 0.0005 & 0.9963 & 0.9985 & 0.9989 \\  & 0.08 & 0.0005 & 0.0008 & 0.0012 & 0.9989 & 0.9995 & 0.9992 \\  & 0.11 & 0.0010 & 0.0015 & 0.0023 & 0.9997 & 0.9997 & 1 \\
30 & 0.14 & 0.0017 & 0.0025 & 0.0038 & 0.9998 & 0.9999 & 0.9999 \\  & 0.4 & 0.0424 & 0.0505 & 0.0597 & 1 & 1 & 1 \\  & 0.7 & 0.2046 & 0.2492 & 0.2724 & 1 & 1 & 1 \\  & 1.0 & 0.5289 & 0.6657 & 0.7459 & 1 & 1 & 1 \\ \hline  & 0.05 & 0.0002 & 0.0003 & 0.0005 & 1 & 0.9991 & 1 \\  & 0.08 & 0.0006 & 0.0008 & 0.0012 & 1 & 0.9996 & 1 \\  & 0.11 & 0.0011 & 0.0015 & 0.0022 & 0.9996 & 0.9999 & 1 \\
35 & 0.14 & 0.0018 & 0.0025 & 0.0037 & 0.9998 & 1 & 1 \\  & 0.4 & 0.0432 & 0.0503 & 0.0588 & 1 & 1 & 1 \\  & 0.7 & 0.2150 & 0.2482 & 0.2697 & 1 & 1 & 1 \\  & 1.0 & 0.5530 & 0.6590 & 0.7490 & 1 & 1 & 1 \\ \hline  & 0.05 & 0.0002 & 0.0003 & 0.0004 & 1 & 1 & 0.9983 \\  & 0.08 & 0.0006 & 0.0008 & 0.0011 & 0.9994 & 1 & 0.9989 \\  & 0.11 & 0.0011 & 0.0015 & 0.0021 & 0.9996 & 0.9995 & 0.9995 \\
40 & 0.14 & 0.0018 & 0.0025 & 0.0035 & 0.9995 & 0.9999 & 0.9999 \\  & 0.4 & 0.0423 & 0.0507 & 0.0574 & 1 & 1 & 1 \\  & 0.7 & 0.2113 & 0.2481 & 0.2679 & 1 & 1 & 1 \\  & 1.0 & 0.5491 & 0.6553 & 0.7400 & 1 & 1 & 1 \\ \hline \hline \end{tabular}
\end{table}