# On the Complexity of the Bipartite Polarization Problem:
## 1 Introduction
From our point of view, the goal to be achieved in this direction is to provide mechanisms that allow us to detect situations where one can deduce that polarization is taking place within an online debate, and to a certain level of severity, because there is some criterion that can be quantified and measured. With this goal in mind, and given that Reddit turned out to be a decisive political debate platform in different elections in the United States, such as those of 2016, in a research work, we introduced a problem [24] of finding the highest polarized bipartition on a weighted and labeled graph that represents a Reddit debate, where nodes represent user's opinions and edges agreement or disagreement between users. To find the highest polarized bipartition of a Reddit debate, our model considers the premise that, in a debate, we can have interactions in two ways: within groups and between groups. Then, an important aspect of our polarization measure is that it allows us to quantify the relevance of the kinds of interactions within the debate, and the polarization degree of the bipartition, which are based on how homogeneous each partition is, and how negative the interactions are between both partitions. Our measure does not try to prove a correlation between the polarization of a particular online debate and the true opinions of their users. That is, the measure takes only into account the specific comments expressed in a particular debate. Also, in [24], we showed that finding this target bipartition is an optimization problem that can be seen as a generalization of the maxcut problem, and we introduced a basic local search algorithm to find approximate solutions of the problem. Later on, in [25], we also studied the complexity of solving real instances from Reddit discussions with both complete and approximate algorithms. These results on real Reddit instances showed that solving those instances could be performed with little computational cost as the size of the instances increased, and that all the instances, obtained from different subreddits, tended to show polarization values away from neutral discussions, although without reaching the case of extreme polarization. Our aim in this paper is to further investigate the complexity of this problem by introducing an instance generation model, where a single parameter controls the polarization of the instances in such a way that this correlates with the average complexity to solve those instances. The average complexity results we obtain are consistent with our hypothesis: the higher the polarization of the instance, the easier is to find the corresponding polarized bipartition. Although one can consider other alternative ways to measure the polarization in online social networks, we believe that our generation model could be used to easily check other measures. The results obtained with our generation model, together with the previous results on real instances from Reddit discussions, seem to indicate that, in practice, it may be feasible to compute the polarization of online discussions, at least with a polarization measure like the one we use here. Therefore, in view of the experimental results, checking polarization with this measure seems to only be difficult in unrealistic cases. Clearly, it is advantageous to offer algorithms for monitoring polarization in online social networks. The structure of the rest of the paper is as follows. In Section 2, we present both the model for weighted and labeled graphs that represents an online debate, and the measure to quantify the polarization in such debate graphs, studied and developed in [24]. In Section 3, we prove that the computation of such a measure is NP-hard. In Section 4, we describe the algorithms that we use to solve the bipartite polarization problem. In Section 5, we introduce our random generation model for user debate graphs based on a main parameter, called \(\alpha\), to control the polarization of the instances.