Un algoritmo de aproximación de tiempo casi lineal para el agrupamiento de grafos más allá del peor caso

Consideramos el modelo de grafos semi-aleatorios de Makarychev, Makarychev y Vijayaraghavan, STOC'12, donde, dado un grafo bipartito aleatorio con aristas y una bipartición desconocida (A, B) del conjunto de vértices, un adversario puede agregar aristas arbitrarias dentro de cada comunidad y eliminar aristas arbitrarias del corte (A, B) (es decir, todos los cambios adversariales son monótonos con respecto a la bipartición). Para este modelo, se conoce un algoritmo de tiempo polinómico que aproxima el problema del Corte Balanceado hasta un valor O () MMV'12 siempre que el corte (A, B) tenga tamaño (). Sin embargo, consiste en subrutinas lentas que requieren soluciones óptimas para una cantidad logarítmica de programas semidefinidos. Estudiamos la complejidad de grano fino del problema y presentamos el primer algoritmo de tiempo casi lineal que logra rendimientos similares a los de MMV'12. Nuestro algoritmo se ejecuta en tiempo O (|V (G) |^1+o (1) + |E (G) |^1+o (1) ) y encuentra un corte balanceado de valor O (). Nuestro enfoque parece fácilmente extensible a problemas relacionados, como Corte más Ralo, y también proporciona una aproximación de tiempo casi lineal O (1) al objetivo de la función de Dagupta para la agrupación jerárquica Dasgupta, STOC'16 para las entradas del modelo de bloques estocásticos jerárquicos semi-aleatorios de Cohen-Addad, Kanade, Mallmann-Trenn, Mathieu, JACM'19.