El problema de polarización bipartita es un problema de optimización donde el objetivo es encontrar la bipartición más polarizada en un grafo ponderado y etiquetado que representa un debate desarrollado a través de alguna red social, donde los nodos representan las opiniones de los usuarios y las aristas representan el acuerdo o desacuerdo entre los usuarios. Este problema puede ser visto como una generalización del problema de corte máximo, y en trabajos anteriores se han obtenido soluciones aproximadas y soluciones exactas para instancias reales obtenidas de discusiones en Reddit, mostrando que tales instancias reales parecen ser muy fáciles de resolver. En este artículo, investigamos aún más la complejidad de este problema al introducir un modelo de generación de instancias donde un solo parámetro controla la polarización de las instancias de tal manera que esto se correlaciona con la complejidad promedio para resolver esas instancias. Los resultados de complejidad promedio que obtenemos son consistentes con nuestra hipótesis: cuanto mayor es la polarización de la instancia, más fácil es encontrar la bipartición polarizada correspondiente. A la luz de los resultados experimentales, es factible implementar mecanismos transparentes para monitorear la polarización en discusiones en línea e informar sobre soluciones para crear entornos de redes sociales más saludables.