# On the Complexity of the Bipartite Polarization Problem:
## 2 Problem Definition  
Polarization corresponds to the social process whereby a group of persons is divided into two opposing subgroups having conflicting and contrasting positions, goals, and viewpoints, with few individuals remaining neutral or holding an intermediate position [26]. The model we consider in this work is inspired by the model defined in [27] to identify supporting or opposing opinions in online debates, based on finding a maximum cut in a graph that models the interactions between users. Moreover, as we are interested in quantifying polarization, we consider a model that is based on a weighted graph and with labeled edges, where node weights represent the side of the user in the debate, and edge labels represent the overall sentiment between two users. Then, given a bipartition of this graph, the polarization degree of the bipartition is based on how homogeneous each partition is, and how negative the interactions are between both partitions. Finally, the measure of debate polarization is based on the maximum polarization obtained in all the possible bipartitions of the graph. Adapting from [24], an online debate \(\Gamma\) on a root comment \(r\) is a non-empty set of comments that were originated as successive answers to a root comment \(r\). An online debate is modeled as a two-sided debate tree, where nodes are labeled with a binary value that denotes whether the comment is in agreement (1) or in disagreement (\(-1\)) with the root comment. Notice that in [24], we introduced this model specifically for Reddit debates. However, it is clearly a model suitable for other, similar social networks. **Definition 1** (Two-Sided Debate Tree). : _Let \(\Gamma\) be an online debate on a root comment \(r\). A Two-Sided Debate Tree (SDebT) for \(\Gamma\) is a tuple \(\mathcal{T}_{S}=\langle C,r,E,W,S\rangle\), defined as follows:_  
* _For every comment_ \(c_{i}\) _in_ \(\Gamma\)_, there is a node_ \(c_{i}\) _in_ \(C\)_._
* _Node_ \(r\in C\) _is the root node of_ \(\mathcal{T}\)_._
* _If a comment_ \(c_{1}\in C\) _answ another comment_ \(c_{2}\in C\)_, there is a directed edge_ \((c_{1},c_{2})\) _in_ \(E\)_._
* \(W\) _is a labeling function of answers (edges)_ \(W:E\rightarrow[-2,2]\)_, where the value assigned to an edge_ \((c_{1},c_{2})\in E\) _denotes the sentiment of the answer_ \(c_{1}\) _with respect to_ \(c_{2}\)_, from highly negative (_\(-2\)_) to highly positive (_\(2\)_)._  
- \(For\) _all nodes_ \(c_{1}\
eq r\) _in_ \(C\)_,_ \(S(c_{1})=1\) _if, for some node_ \(c_{2}\in C\)_,_ \((c_{1},c_{2})\in E\) _and either_ \(S(c_{2})=1\) _and_ \(W(c_{1},c_{2})>0\)_, or_ \(S(c_{2})=-1\) _and_ \(W(c_{1},c_{2})\leq 0\)_; otherwise,_ \(S(c_{1})=-1\)_._  
_Only the nodes and edges obtained by applying this process belong to \(C\) and \(E\), respectively._  
Next, we present the formalization of a User Debate Graph based on a Two-Sided Debate Tree, where now all the comments of the same user are aggregated into a single node that represents the user's opinion. **Definition 2** (User Debate Graph). : _Let \(\Gamma\) be a online debate on a root comment \(r\) with users' identifiers \(U=\{u_{1},\ldots,u_{m}\}\), and let \(\mathcal{T}_{S}=\langle C,r,E,W,S\rangle\) be a \(\mathsf{SDeDT}\) for \(\Gamma\).