# On the Complexity of the Bipartite Polarization Problem:
## 7 Experimental Results  
The results of the median time to solve instances with  
\[\alpha\in\{0.05,0.08,0.11,0.14,0.4,0.7,1.0\}\]  
and  
\[m\in\{25,30,35,40\}\]  
as well as the bipartite polarization of the instances, are shown in Figure 1. For each combination of \(\alpha\) and \(m\), the median value shown on the figure is obtained from a set of 50 instances obtained with our random generator. We have used close values of \(\alpha\) up to 0.14 because, as one can observe, the median time to solve the instances increases quickly as \(m\) increases for very low values of \(\alpha\), but as we move away from 0 the median time decreases abruptly. At the same time, the median bipartite polarization of the instances increases slowly for low values of \(\alpha\), but then it starts to increase more quickly as \(\alpha\) increases. So, these results are consistent with our hypothesis about the relation between polarization and complexity to solve the instances. If we compare these results with the ones with real instances from Reddit in [25], which have a median number of nodes of around 50, we observe that they are also consistent, in the sense that in the Reddit discussions used in that paper, the median polarization of the instances was around 0.5, and the median time was around 2 s, using the same hardware used here. To make a more complete comparison of the complexity, we have also computed the median number of nodes performed by the exact algorithm based on the SCIP solver (the same one used in that previous paper), given that in our previous paper, we also showed the median number of nodes of the SCIP search tree. Figure 2 shows the median number of nodes for the same instances of Figure 1. As we can observe, the number of nodes of the SCIP search tree follows the same qualitative behavior as the time, and for instances with median polarization around 0.5 (which have \(\alpha>0.7\)), the median number of nodes would be around 1 (by interpolating between our cases \(\alpha=0.7\) and \(\alpha=1.0\)), as happens in the results of our previous paper with the Reddit instances. Figure 1: CPU time needed to solve the instances (**left plot**) and polarization of the solution (**right plot**) as we increase the alpha value for instances with nodes ranging from 25 to 40. Although our choice of the value \(\lceil log_{10}(m)\rceil\) as the value for the maximum number of out edges for each node in our random generator is consistent with the characteristics of the Reddit instances solved in [25], we wanted to check if the complexity patterns we have observed in the previous experiments were not a result of a too low value for the number of out edges. This is something relevant, as the NP-hardness results for maxcut in [28], and the problem we have used to show NP-hardness of our problem, are valid for graphs with bounded degree 3, but the average degree of the graphs generated for the experiments in Figures 1 and 2 have an average degree around 1, given the maximum value used for \(m\) (40). So, in order to eliminate the possibility of easy instances due to low degree graphs, we have generated a second set of instances of larger size, with \(m\) ranging from 40 to 90, and where the maximum out degree of the instances is now equal to \(3\lceil log_{10}(m)\rceil\), now giving the value 6 as the maximum out degree for vertices, and 3.5 being the average degree. Figure 3 shows the same plots as Figure 1, but obtained with these new instances with higher vertex degrees. Notice that the plots now start at \(\alpha=0.4\), since the complexity of solving these instances for lower values of \(\alpha\) is expected to be greater than in the previous experiments, given the higher values for \(m\). In the left plot, we can observe that the complexity in CPU time increases as we lower the \(\alpha\) value, but this increase does not seem exponential, at least for \(\alpha\geq 0.5\).