# On the Complexity of the Bipartite Polarization Problem:
## 2 Problem Definition
A User Debate Graph (\(\mathsf{UDeB}\)) for \(\mathcal{T}_{S}\) is a tuple \(\mathcal{G}=\langle\mathcal{C},\mathcal{E},\mathcal{S},\mathcal{W}\rangle\), where:_  
* \(\mathcal{C}\) _is the set of nodes of_ \(\mathcal{G}\)_, defined as the set of users' opinions_ \(\{C_{1},\ldots,C_{m}\}\)_, i.e.,_ \(\mathcal{C}=\{C_{1},\ldots,C_{m}\}\) _with_ \(C_{i}=\{c\in\Gamma\mid c\
eq r\text{ and user}(c)=u_{i}\}\)_, for all users_ \(u_{i}\in U\)_._
* \(\mathcal{E}\subseteq\mathcal{C}\times\mathcal{C}\) _is the set of edges of_ \(\mathcal{G}\)_, defined as the set of interactions between different users in the debate, i.e., there is an edge_ \((C_{i},C_{j})\in\mathcal{E}\)_, with_ \(C_{i},C_{j}\in\mathcal{C}\) _and_ \(i\
eq j\)_, if and only if, for some_ \((c_{1},c_{2})\in E\)_, we have that_ \(c_{1}\in C_{i}\) _and_ \(c_{2}\in C_{j}\)_._
* \(\mathcal{S}\) _is an opinion weighting scheme for_ \(\mathcal{C}\) _that expresses the side of users in the debate based on the side of their comments. We define_ \(\mathcal{S}\) _as the mapping_ \(\mathcal{S}:\mathcal{C}\rightarrow[-1,1]\) _that assigns to every node_ \(C_{i}\in\mathcal{C}\) _the value_ \[\mathcal{S}(C_{i})=\frac{\sum_{c\in C_{i}}S(c_{i})}{|C_{i}|}\] _in the real interval_ \([-1,1]\)_, which expresses the side of the user_ \(u_{i}\) _with respect to the root comment, from strictly disagreement_ \((-1)\) _to strictly agreement_ \((1)\)_, going through undecided opinions_ \((0)\)_._
* \(\mathcal{W}\) _is an interaction weighting scheme for_ \(\mathcal{E}\) _that expresses the overall sentiment between users by combining the individual sentiment values assigned to the responses between their comments._ _We define_ \(\mathcal{W}\) _as the mapping_ \(\mathcal{W}:\mathcal{E}\rightarrow[-2,2]\) _that assigns to every edge_ \((C_{i},C_{j})\in\mathcal{E}\) _a value_ \(w\in[-2,2]\)_, defined as follows:_ \[w=\sum_{\{(c_{1},c_{2})\in E\cap(C_{i}\times C_{j})\}}W(c_{1},c_{2})/|\{(c_{1 },c_{2})\in E\cap(C_{i}\times C_{j})\}|\] _where_ \(w\) _expresses the overall sentiment of the user_ \(u_{i}\) _regarding the comments of the user_ \(u_{j}\)_, from highly negative_ \((-2)\) _to highly positive_ \((2)\)_._ _Only the nodes and edges obtained by applying this process belong to_ \(\mathcal{C}\) _and_ \(\mathcal{E}\)_, respectively._  
Given a User Debate Graph \(\mathcal{G}=\langle\mathcal{C},\mathcal{E},\mathcal{S},\mathcal{W}\rangle\), a model to measure the level of polarization in the debate between its users was also introduced in [24]. It is based on two characteristics that a polarization measure should capture. First, a polarized debate should contain a bipartition of \(\mathcal{C}\) into two sets \((L,R)\), such that the set \(L\) contains mainly users in disagreement, the set \(R\) contains mainly users in agreement, and both sets should be similar in size. The second ingredient is the sentiment between users of \(L\) and \(R\). A polarized discussion should contain most of the negative interactions between users of \(L\) and users of \(R\), whereas the positive interactions, if any, should be mainly within the users of \(L\) and within the users of \(R\). To capture these two characteristics with a single value, two different measures are combined in a final one, referred to as _the bipartite polarization_. **Definition 3** (Bipartite polarization). : _Given a User Debate Graph \(\mathcal{G}=\langle\mathcal{C},\mathcal{E},\mathcal{S},\mathcal{W}\rangle\) and a bipartition \((L,R)\) of \(\mathcal{C}\), we define:_  
* _The level of consistency and balance of_ \((L,R)\) _is a real value in_ \([0,0.25]\)_, defined as follows:_ \[\mathrm{SC}(L,R,\mathcal{G})=\mathrm{LC}(L,\mathcal{G})\cdot\mathrm{RC}(R, \mathcal{G})\] _with_ \[\mathrm{LC}(L,\mathcal{G})=\frac{\sum_{ \begin{subarray}{c}C_{i}\in L_{i}\\ \mathcal{S}(C_{i})\leq 0\end{subarray} }-\mathcal{S}(C_{i})}{|\mathcal{C}|}\] _and_ \[\mathrm{RC}(R,\mathcal{G})=\frac{\sum_{ \begin{subarray}{c}C_{i}\in R_{i}\\ \mathcal{S}(C_{i})>0\end{subarray}