As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
In a recent work we introduced a problem about finding the highest polarized bipartition on a weighted and labeled graph that represents a debate developed trough some social network, where nodes represent user’s opinions and edges agreement or disagreement between users. Finding this target bipartition is an optimization problem that can be seen as a generalization of the maxcut problem, so we first introduced a basic local search algorithm to find approximate solutions of the problem. In this paper we go one step further, and we present an exact algorithm for finding the optimal solution, based on an integer programming formulation, and compare the performance of a new variant of our local search algorithm with the exact algorithm. Our results show that at least on real instances of the problem, obtained from Reddit debates, the approximate solutions obtained are almost always identical to the optimal solutions.