# On the Complexity of the Bipartite Polarization Problem:
## 3 Worst-Case Complexity of the Bipartite Polarization Problem  
Proposition 1: _The \(\text{UDebG}\) bipartite polarization problem is NP-hard._  
Proof: We prove that the simple maxcut problem, which it is NP-hard even for graphs with bounded degree \(\leq 3\)[28], can be reduced to the \(\text{UDebG}\) bipartite polarization problem in polynomial time. Consider an undirected graph instance \(G=(V,E)\) of the simple maxcut problem. Then, we build an instance \(\mathcal{G}=\langle\mathcal{C},\mathcal{E},\mathcal{S},\mathcal{W}\rangle\) of the bipartite polarization problem, such that:  
1. The set of vertices \(\mathcal{C}\) is equal to \(V\cup\{u^{-},u^{+}\}\). 2. For \(\mathcal{S}\), we have that \(\forall v\in V,\mathcal{S}(v)=0\) and \(\mathcal{S}(u^{-})=-1,\mathcal{S}(u^{+})=+1\). 3. The set of edges \(\mathcal{E}\) is defined only for those vertices that have an edge in the input graph: \[\mathcal{E}=\{(v_{1},v_{2}),(v_{2},v_{1})\mid\{v_{1},v_{2}\}\in E\}.\]
4. For any \(e\in\mathcal{E}\), we have that \(\mathcal{W}(e)=-1/2\). Then, assume \(G=(V,E)\) has a bipartition \((L,R)\) with total weight (number of edges between \(L\) and \(R\)) equal to \(W\). Consider the bipartition \((L\cup\{u^{-}\},R\cup\{u^{+}\})\) for the instance \(\mathcal{G}\) obtained by the reduction. Clearly,  
\[\text{BipPol}(L\cup\{u^{-}\},R\cup\{u^{+}\},\mathcal{G}))=\frac{-(-1)}{| \mathcal{C}|}\frac{1}{|\mathcal{C}|}\bigg{(}\frac{W}{|E|}+2\bigg{)}.\]  
Next, assume \(\mathcal{G}=\langle\mathcal{C},\mathcal{E},\mathcal{S},\mathcal{W}\rangle\) has a bipartition \((L^{\prime},R^{\prime})\) with a bipartite polarization value equal to \(BPol\). Then, as all the nodes have \(\mathcal{S}(v)=0\), except for \(\mathcal{S}(u^{-})=-1\), \(\mathcal{S}(u^{+})=+1\), we have that if \(\text{BipPol}>0\), then \(u^{-}\) will be in \(L^{\prime}\) and \(u^{+}\) will be in \(R^{\prime}\), so the \(\text{BipPol}\) value will be of the same form as before:  
\[\text{BipPol}(L^{\prime},R^{\prime},\mathcal{G}))=\frac{-(-1)}{|\mathcal{C}|} \frac{1}{|\mathcal{C}|}\bigg{(}\frac{W}{|E|}+2\bigg{)},\]  
where \(W\) will be equal to half the number of edges between \(L^{\prime}\) and \(R^{\prime}\) in \(\mathcal{G}\), as for any undirected edge in the input graph \(G\), we have two directed edges in \(\mathcal{G}\), each one with \(W(e)=-1/2\). But this implies that \((L^{\prime}\setminus\{u^{-}\},R^{\prime}\setminus\{u^{+}\})\) is a bipartition for the input graph \(G\) with value \(W\). For the case \(BPol=0\), this could only happen because the vertices \(u^{-}\) or \(u^{+}\) are in the wrong side. But we can always transform any bipartition \((L^{\prime},R^{\prime})\) to one in which \(u^{-}\) and \(u^{+}\) are in the right side, and so derive the value of \(W\) from the value of \(BPol\). As a consequence, \((L,R)\) is a simple maximum cut for \(G=(V,E)\) if and only if \((L\cup\{u^{-}\},R\cup\{u^{+}\})\) is a bipartition for \(\mathcal{G}=\langle\mathcal{C},\mathcal{E},\mathcal{S},\mathcal{W}\rangle\) with maximum _BipPol_ value. This reduction shows two interesting facts about our problem. First, we can have instances that are as hard to solve as the Maxcut problem when almost all the users have \(\mathcal{S}(v)=0\). But at the same time, observe that we need to have at least one user with a negative value and another one with a positive value. This is because if strictly all the users have \(\mathcal{S}(v)=0\), then the \(\textit{BipPol}(L,R,\mathcal{G})\) value is equal to zero for any bipartition \((L,R)\), and then it becomes trivial to solve the problem. These facts, together with the experimental results in [25] with real instances from Reddit discussions, where instances with polarization values away from neutral, were very easy to solve on average, which makes us present the following hypothesis. **Hypothesis 1**.